数据库系统原理(英文)-12-09.pptVIP免费

PART4DATASTORAGEANDQUERYChapter12IndexingandHashingApril,May2008DatabaseSystemConcepts-Chapter12IndexingandHashing-3ContentsinThisChapterBasicconceptsaboutandclassificationofindexingorderedindices,hashindicesProperties/typesoforderedindicesprimary/clusteringindices,secondary/non-clusteringindicesdenseindices,sparseindicessingle-levelindices,multi-levelindices(e.g.B+-tree,B-tree)Hashindiceshashfunctionsstatichash,dynamichashApril,May2008DatabaseSystemConcepts-Chapter12IndexingandHashing-4§12.1BasicConceptsHowtolocaterecordsinDBfilequickly?Indexing(索引技术)mechanismsusedtospeedupaccesstodesireddatae.g.forrelationaccount(account-number,branch-name,balance)showninFig.12.1,theindexbranch-namephysicaladdressofrecord(i.e.tuple)inDBfileaccountSearchKeyattributesorasetofattributesusedtolookuptherecordsinafilee.g.branch-nameA-217A-110A-101A-215A-201A-218A-102A-222A-305Fig.12.1DBindexedfileaccountanditsindexfileNote:thefileaccountislogicallyasequentialfile,butitsrecordsmaybestorednon-contiguouslyornon-orderedonthedisklogicalfileaccountphysicalfileaccountindexfile(account-number,branch-name,balance)indexedfileApril,May2008DatabaseSystemConcepts-Chapter12IndexingandHashing-6§12.1BasicConcepts(cont.)Indexingmappingfromsearch-keytostoragelocationsofthefilerecords,i.e.search-keystoragelocationsoftherecordsindisks搜索键(searchkey)索引文件(indexfile)数据文件（主文件、被索引文件indexedfile）s1s2s3..si..sj.sn散列函数Hs1s2s3..si..sj.sna3a2a1…ai…aj…am…an-1anb3b2b1…bi…bj…bm…bn-1bns3s2s1…si…sj…sm…sn-1sn………………………………d3d2d1…di…dj…dm…dn-1dnR(A,B,S,….,,D)…………h(si)h(sn)h(s1){索引项}indexentrys1s2s3…si…sm图12.0.1索引技术(indexing)及其分类orderedindiceshashindices搜索键(searchkey)April,May2008DatabaseSystemConcepts-Chapter12IndexingandHashing-8Twobasickindsofindices:orderedindices:theindexfileisusedtostoretheindexentriesinwhichthesearchkeyoftherecordsandtheaddressoftherecordsarestoredinsortedorderhashindices:the...