《山东大学数据库系统英语课件11查询处理和查询优化》由会员分享，可在线阅读，更多相关《山东大学数据库系统英语课件11查询处理和查询优化（90页珍藏版）》请在金锄头文库上搜索。
1、Database System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db- for conditions on re-use Chapter 11: Indexing and HashingSilberschatz, Korth and Sudarshan11.2Database System Concepts - 6th EditionChapter 12: Indexing and HashingnBasic ConceptsnOrdered Indices nB+-Tree Index FilesnB-Tre
2、e Index FilesnStatic HashingnDynamic Hashing nComparison of Ordered Indexing and Hashing nIndex Definition in SQLnMultiple-Key AccessSilberschatz, Korth and Sudarshan11.3Database System Concepts - 6th EditionBasic ConceptsnIndexing mechanisms used to speed up access to desired data.lE.g., author cat
3、alog in librarynSearch Key - attribute to set of attributes used to look up records in a file.nAn index file consists of records (called index entries) of the formnIndex files are typically much smaller than the original file nTwo basic kinds of indices:lOrdered indices: search keys are stored in so
4、rted orderlHash indices: search keys are distributed uniformly across “buckets” using a “hash function”. search-keypointerSilberschatz, Korth and Sudarshan11.4Database System Concepts - 6th EditionIndex Evaluation MetricsnAccess types supported efficiently. E.g., lrecords with a specified value in t
5、he attributelor records with an attribute value falling in a specified range of values.nAccess timenInsertion timenDeletion timenSpace overheadSilberschatz, Korth and Sudarshan11.5Database System Concepts - 6th EditionOrdered IndicesnIn an ordered index, index entries are stored sorted on the search
6、 key value. E.g., author catalog in library.nPrimary index: in a sequentially ordered file, the index whose search key specifies the sequential order of the file.lAlso called clustering indexlThe search key of a primary index is usually but not necessarily the primary key.nSecondary index: an index
7、whose search key specifies an order different from the sequential order of the file. Also called non-clustering index.nIndex-sequential file: ordered sequential file with a primary index.Silberschatz, Korth and Sudarshan11.6Database System Concepts - 6th EditionDense Index FilesnDense index Index re
8、cord appears for every search-key value in the file. nE.g. index on ID attribute of instructor relation Silberschatz, Korth and Sudarshan11.7Database System Concepts - 6th EditionDense Index Files (Cont.)nDense index on dept_name, with instructor file sorted on dept_nameSilberschatz, Korth and Sudar
9、shan11.8Database System Concepts - 6th EditionSparse Index FilesnSparse Index: contains index records for only some search-key values.lApplicable when records are sequentially ordered on search-keynTo locate a record with search-key value K we:lFind index record with largest search-key value KlSearc
10、h file sequentially starting at the record to which the index record pointsSilberschatz, Korth and Sudarshan11.9Database System Concepts - 6th EditionSparse Index Files (Cont.)nCompared to dense indices:lLess space and less maintenance overhead for insertions and deletions.lGenerally slower than den
11、se index for locating records.nGood tradeoff: sparse index with an index entry for every block in file, corresponding to least search-key value in the block.Silberschatz, Korth and Sudarshan11.10Database System Concepts - 6th EditionSecondary Indices ExamplenIndex record points to a bucket that cont
12、ains pointers to all the actual records with that particular search-key value.nSecondary indices have to be denseSecondary index on salary field of instructorSilberschatz, Korth and Sudarshan11.11Database System Concepts - 6th EditionPrimary and Secondary IndicesnIndices offer substantial benefits w
13、hen searching for records.nBUT: Updating indices imposes overhead on database modification -when a file is modified, every index on the file must be updated, nSequential scan using primary index is efficient, but a sequential scan using a secondary index is expensive lEach record access may fetch a
14、new block from disklBlock fetch requires about 5 to 10 milliseconds, versus about 100 nanoseconds for memory accessSilberschatz, Korth and Sudarshan11.12Database System Concepts - 6th EditionMultilevel IndexnIf primary index does not fit in memory, access becomes expensive.nSolution: treat primary i
15、ndex kept on disk as a sequential file and construct a sparse index on it.louter index a sparse index of primary indexlinner index the primary index filenIf even outer index is too large to fit in main memory, yet another level of index can be created, and so on.nIndices at all levels must be update
16、d on insertion or deletion from the file.Silberschatz, Korth and Sudarshan11.13Database System Concepts - 6th EditionMultilevel Index (Cont.)Multilevel Index (Cont.)Silberschatz, Korth and Sudarshan11.14Database System Concepts - 6th EditionIndex Update: DeletionnSingle-level index entry deletion:lDense indices deletion of search-key is similar to file record deletion.lSparse indices 4 if an entry for the search key exists in the index, it is deleted by replacing the entry in the index with the
