数据库系统概念全套配套课件PPT ch11.ppt

《数据库系统概念全套配套课件PPT ch11.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter11:IndexingandHashingChapter11:IndexingandHashingBasicConceptsOrderedIndicesB+-TreeIndexFilesB-TreeIndexFilesStaticHashingDynamicHashingComparisonofOrderedIndexingandHashingIndexDefinitioninSQLMultiple-KeyAccessBasicConceptsIndexingmechanismsused

2、tospeedupaccesstodesireddata.E.g.,authorcataloginlibrarySearchKey-attributetosetofattributesusedtolookuprecordsinafile.Anindexfileconsistsofrecords(calledindexentries)oftheformIndexfilesaretypicallymuchsmallerthantheoriginalfileTwobasickindsofindices:Or

3、deredindices:searchkeysarestoredinsortedorderHashindices:searchkeysaredistributeduniformlyacross“buckets”usinga“hashfunction”.search-keypointerIndexEvaluationMetricsAccesstypessupportedefficiently.E.g.,recordswithaspecifiedvalueintheattributeorrecordswi

4、thanattributevaluefallinginaspecifiedrangeofvalues.AccesstimeInsertiontimeDeletiontimeSpaceoverheadOrderedIndicesInanorderedindex,indexentriesarestoredsortedonthesearchkeyvalue.E.g.,authorcataloginlibrary.Primaryindex:inasequentiallyorderedfile,theindex

5、whosesearchkeyspecifiesthesequentialorderofthefile.AlsocalledclusteringindexThesearchkeyofaprimaryindexisusuallybutnotnecessarilytheprimarykey.Secondaryindex:anindexwhosesearchkeyspecifiesanorderdifferentfromthesequentialorderofthefile.Alsocallednon-clu

6、steringindex.Index-sequentialfile:orderedsequentialfilewithaprimaryindex.DenseIndexFilesDenseindex—Indexrecordappearsforeverysearch-keyvalueinthefile.E.g.indexonIDattributeofinstructorrelationDenseIndexFiles(Cont.)Denseindexondept_name,withinstructorfil

7、esortedondept_nameSparseIndexFilesSparseIndex:containsindexrecordsforonlysomesearch-keyvalues.Applicablewhenrecordsaresequentiallyorderedonsearch-keyTolocatearecordwithsearch-keyvalueKwe:Findindexrecordwithlargestsearch-keyvalue

8、tartingattherecordtowhichtheindexrecordpointsSparseIndexFiles(Cont.)Comparedtodenseindices:Lessspaceandlessmaintenanceoverheadforinsertionsanddeletions.Generallyslowerthandenseindexforlocatingrecords.Goodtradeoff:sparseindexwitha