《北邮数据库课程讲义chapter9》由会员分享，可在线阅读，更多相关《北邮数据库课程讲义chapter9（30页珍藏版）》请在金锄头文库上搜索。
1、DataBase System Concepts Chapter 9 Indexing and HashingIndexing and Hashing DataBase System Concepts Basic Concepts Ordered Indices: Primary index, Secondary index B+-Tree Index Hash Indices Index Definition in SQL DataBase System Concepts Basic ConceptsBasic Concepts n Indexing mechanisms used to s
2、peed up access to desired data. n Search Key An attribute or set of attributes used to look up records in a file. n An index file consists of records (called index entries) of the form n Index files are typically much smaller than the original file n Two basic kinds of indices: Ordered indices: sear
3、ch 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 Index Evaluation MetricsIndex Evaluation Metrics n Access types supported efficiently. records with a specified value in the at
4、tribute or records with an attribute value falling in a specified range of values. n Access time n Insertion time n Deletion time n Space overhead DataBase System Concepts Ordered IndicesOrdered Indices In an ordered index, index entries are stored sorted on the search key value: nPrimary index（主索引）
5、: in a sequentially ordered file, the index whose search key specifies the sequential order of the file. Also called clustering index（聚集索引） The search key of a primary index is usually but not necessarily the primary key. Index-sequential file: ordered sequential file with a primary index. nSecondar
6、y index（辅助索引）: an index whose search key specifies an order different from the sequential order of the file. Also called non-clustering index. DataBase System Concepts Dense Indices(Dense Indices(稠密索引）稠密索引） n Dense index Index record appears for every search- key value in the file. DataBase System C
7、oncepts Sparse IndicesSparse Indices（稀疏索引）（稀疏索引） n Sparse Index: contains index records for only some search -key values. Applicable when records are sequentially ordered on search-key DataBase System Concepts n To locate a record with search-key value K we: Find index record with largest search-key
8、 value K Search file sequentially starting at the record to which the index record points n Less space and less maintenance overhead for insertions and deletions. n Generally slower than dense index for locating records. n Good tradeoff: sparse index with an index entry for every block in file, corr
9、esponding to least search-key value in the block. Sparse Indices(2)Sparse Indices(2) DataBase System Concepts Multilevel IndexMultilevel Index n If primary index does not fit in memory, access becomes expensive. n To reduce number of disk accesses to index records, treat primary index kept on disk a
10、s a sequential file and construct a sparse index on it. outer index a sparse index of primary index inner index the primary index file n If even outer index is too large to fit in main memory, yet another level of index can be created, and so on. n Indices at all levels must be updated on insertion
11、or deletion from the file. DataBase System Concepts Example DataBase System Concepts Index Update: DeletionIndex Update: Deletion If deleted record was the only record in the file with its particular search-key value, the search-key is deleted from the index also. Single-level index deletion: Dense
12、indices Delete the pointers(stores pointers to all records); Update the pointer (stores pointers to the first record); Sparse indices Nothing done; replace with next search-key value; updates the pointer; Multilevel deletion algorithms are simple extensions of the single-level algorithms. DataBase S
13、ystem Concepts Index Update: InsertionIndex Update: Insertion Single-level index insertion: Perform a lookup using the search-key value appearing in the record to be inserted. Dense indices insert index/add pointer/update pointer Sparse indices no change / insert index / update pointer Multilevel in
14、sertion algorithms are simple extensions of the single-level algorithms DataBase System Concepts Secondary IndicesSecondary Indices DataBase System Concepts Primary and Secondary IndicesPrimary and Secondary Indices n Secondary indices have to be dense. n Indices offer substantial benefits when sear
15、ching for records. n When a file is modified, every index on the file must be updated, Updating indices imposes overhead on database modification. n Sequential scan using primary index is efficient, but a sequential scan using a secondary index is expensive each record access may fetch a new block f
16、rom disk DataBase System Concepts B B+ + -Tree Index Files-Tree Index Files All paths from root to leaf are of the same length Each node that is not a root or a leaf has between n/2 and n children. A leaf node has between (n1)/2 and n1 values Special cases: If the root is not a leaf, it has at least 2 children. If the root is a leaf (that is, there are no other nodes
