程序代写代做 graph C finance database algorithm Chapter 11: Indexing and Hashing

Chapter 11: Indexing and Hashing
■ Basic Concepts
■ Ordered Indices
■ B+-Tree Index Files
■ B-Tree Index Files — skipping
■ Static Hashing
■ Dynamic Hashing — skipping
■ Comparison of Ordered Indexing and Hashing
■ Index Definition in SQL
■ Multiple-Key Access
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.1 ©Silberschatz, Korth and Sudarshan

Basic Concepts
■ Indexing mechanisms used to speed up access to desired data. ● E.g.,authorcataloginlibrary
■ Search Key – attribute to set of attributes used to look up records in a file.
■ An index file consists of records (called index entries) of the form
 

■ Index files are typically much smaller than the original file
■ Two basic kinds of indices:
● Ordered indices: search keys are stored in sorted order
● Hash indices: search keys are distributed uniformly across
“buckets” using a “hash function”.
search-key
pointer
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.2 ©Silberschatz, Korth and Sudarshan

Index Evaluation Metrics
■ Access types supported efficiently. E.g.,
● recordswithaspecifiedvalueintheattribute
● orrecordswithanattributevaluefallinginaspecifiedrangeof values.
■ Access time
■ Insertion time
■ Deletion time
■ Space overhead
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.3
©Silberschatz, Korth and Sudarshan

Ordered Indices
■ In an ordered index, index entries are stored sorted on the search key value. E.g., author catalog in library.
■ Primary index: in a sequentially ordered file, the index whose search key specifies the sequential order of the file.
● Alsocalledclusteringindex
● Thesearchkeyofaprimaryindexisusuallybutnotnecessarilythe
primary key.
■ Secondary index: an index whose search key specifies an order different from the sequential order of the file. Also called 
 non-clustering index.
■ Index-sequential file: ordered sequential file with a primary index.
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.4 ©Silberschatz, Korth and Sudarshan

Dense Index Files
■ Dense index — Index record appears for every search-key value in the file.
■ E.g. index on ID attribute of instructor relation
10101
12121
15151
22222
32343
33456
45565
58583
76543
76766
83821
98345
Srinivasan
10101
12121
15151
22222
32343
33456
45565
58583
76543
76766
83821
98345
Wu
Mozart
Einstein
El Said
Gold
Katz
Califieri
Singh
Crick
Brandt
Kim
Finance
Music
Physics
History
Physics
Comp. Sci.
History
Finance
Biology
Comp. Sci.
Elec. Eng.
40000
95000
60000
87000
75000
62000
80000
72000
92000
80000
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.5 ©Silberschatz, Korth and Sudarshan
Comp. Sci.
65000
90000

Dense Index Files (Cont.)
■ Dense index on dept_name, with instructor file sorted on dept_name
76766
Crick
Biology
72000
10101
Srinivasan
Comp. Sci.
65000
45565
Katz
Comp. Sci.
75000
83821
Brandt
Comp. Sci.
92000
98345
Kim
Elec. Eng.
80000
12121
Wu
Finance
90000
76543
Singh
Finance
80000
32343
El Said
History
60000
58583
Califieri
History
62000
15151
Mozart
Music
40000
22222
Einstein
Physics
95000
33465
Gold
Physics
87000
Biology
Comp. Sci.
Elec. Eng.
Finance
History
Music
Physics
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.6 ©Silberschatz, Korth and Sudarshan

Sparse Index Files
■ Sparse Index: contains index records for only some search-key values.
● Applicablewhenrecordsaresequentiallyorderedonsearch-key ■ To locate a record with search-key value K we:
● Findindexrecordwithlargestsearch-keyvalue on 

() E.g.: create index b-index on branch(branch_name)
■ Use create unique index to indirectly specify and enforce the condition that the search key is a candidate key is a candidate key.
● NotreallyrequiredifSQLuniqueintegrityconstraintissupported
■ To drop an index
drop index
■ Most database systems allow specification of type of index, and
clustering.
Database System Concepts – 6th Edition
Modified for CS6083 at NYU Tandon by T. Suel, Spring 2020 11.50 ©Silberschatz, Korth and Sudarshan