北邮数据库课程讲义chapter9.ppt

* DataBase System Concepts Chapter 9 Indexing 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 Concepts Indexing mechanisms used to speed up access to desired data. Search Key – An attribute or 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 Index Evaluation Metrics Access types supported efficiently. records with a specified value in the attribute or records with an attribute value falling in a specified range of values. Access time Insertion time Deletion time Space overhead DataBase System Concepts Ordered Indices In an ordered index, index entries are stored sorted on the search key value: Primary index（主索引）: 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. Secondary 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 index — Index record appears for every search-key value in the file. DataBase System Concepts Sparse Indices（稀疏索引） Sparse Index: contains index records for only some search-key values. Applicable when records are sequentially ordered on search-key DataBase System Concepts To locate a record with search-key value K we: Find index record with large