《北邮_数据库系统原理(英文)_12_15》由会员分享，可在线阅读，更多相关《北邮_数据库系统原理(英文)_12_15（39页珍藏版）》请在金锄头文库上搜索。
1、PART4 DATASTORAGEANDQUERY Chapter12IndexingandHashing DatabaseSystemConcepts Chapter12IndexingandHashing 3 ContentsinThisChapter Basicconceptsaboutandclassificationofindexingorderedindices hashindicesProperties typesoforderedindicesprimary clusteringindices secondary non clusteringindicesdenseindice
2、s sparseindicessingle levelindices multi levelindices e g B tree B tree Hashindiceshashfunctionsstatichash dynamichash DatabaseSystemConcepts Chapter12IndexingandHashing 4 目标 学会准确建立 管理索引 提高数据访问速度索引类型select insert update时的索引管理 DatabaseSystemConcepts Chapter12IndexingandHashing 5 12 1BasicConcepts How
3、tolocaterecordsinDBfilequickly Indexing 索引技术 mechanismsusedtospeedupaccesstodesireddatae g forrelationaccount account number branch name balance showninFig 12 1 theindexbranch name physicaladdressofrecord i e tuple inDBfileaccountSearchKeyattributesorasetofattributesusedtolookuptherecordsinafilee g
4、branch name A 217 A 110 A 101 A 215 A 201 A 218 A 102 A 222 A 305 Fig 12 1DBindexedfileaccountanditsindexfile Note thefileaccountislogicallyasequentialfile butitsrecordsmaybestorednon contiguouslyornon orderedonthedisk logicalfileaccount physicalfileaccount indexfile account number branch name balan
5、ce indexedfile DatabaseSystemConcepts Chapter12IndexingandHashing 7 12 1BasicConcepts cont Indexingmappingfromsearch keytostoragelocationsofthefilerecords i e search key storagelocationsoftherecordsindisks 搜索键 searchkey 索引文件 indexfile 数据文件 主文件 被索引文件indexedfile s1s2s3 si sj sn 散列函数H s1s2s3 si sj sn a
6、3 a2 a1 ai aj am an 1 an b3 b2 b1 bi bj bm bn 1 bn s3 s2 s1 si sj sm sn 1 sn d3 d2 d1 di dj dm dn 1 dn r R R A B S D h si h sn h s1 索引项 indexentry 图12 0 1索引技术 indexing 及其分类 orderedindices hashindices 搜索键 searchkey DatabaseSystemConcepts Chapter12IndexingandHashing 9 Twobasickindsofindices orderedind
7、ices theindexfileisusedtostoretheindexentriesinwhichthesearchkeyoftherecordsandtheaddressoftherecordsarestoredinsortedorderhashindices the hashfunction isusedtomapthethesearchkeyoftherecordstotheaddressoftherecordstherecordsarestoredinthe buckets thenumberofthebucketisastheaddressoftherecordsandisde
8、terminedbythehashfunction 12 1BasicConcepts cont DatabaseSystemConcepts Chapter12IndexingandHashing 10 DBSfileswithindexingmechanismincludetwoparts indexedfile inwhichdatarecordsarestoredindexfile inwhichindexentriesareincludede g Fig 12 1Theindexedfilecanbeorganizedassequentialfileheapfilehashfilec
9、lusteringfile 12 2OrderedIndices DatabaseSystemConcepts Chapter12IndexingandHashing 11 12 1BasicConcepts cont IndexfilesetofindexentriesoftheformIndexfilesaretypicallymuchsmallerthantheoriginalfile DatabaseSystemConcepts Chapter12IndexingandHashing 12 Orderedindex inindexfile theindexentriesintheind
10、exfilearestoredinsomesortedorder forinstance inaccordancewiththeorderofthesearchkey 索引项的排列顺序与 被索引文件中 搜索键的排列顺序一致e g inFig 12 1 theindexfileissortedbybranch name 12 2OrderedIndices cont DatabaseSystemConcepts Chapter12IndexingandHashing 13 Primary clusteringindex inindexfile consideringaindexfileandit
11、scorrespondingindexedfile iftheindexedfileisasequentialfile andthesearchkeyinindexfilealsospecifiesthesequentialorderoftheindexedfile 索引文件的搜索键所规定的顺序与被索引的顺序文件中的纪录顺序一致e g inFig 12 1 branch name addressofrecords definesthesameordersoftherecordsasthatinsequentialindexedfileaccountnote alsocalledclusteri
12、ngindex 12 2 IPrimaryandSecondaryIndices DatabaseSystemConcepts Chapter12IndexingandHashing 14 Thesearchkeyofaprimaryindexisusuallybutnotnecessarilytheprimarykeye g inFig 12 1 branch nameisnottheprimarykeyofaccount 12 2 IPrimaryandSecondaryIndices cont DatabaseSystemConcepts Chapter12IndexingandHash
13、ing 15 聚集索引vs主索引在实际数据库系统中 如SQLServer DB2等 聚集索引 指索引文件的搜索键所规定的顺序与被索引的顺序文件中的纪录顺序一致主索引 指建立在主键 主属性上 的索引当一个表定义了主键后 DBMS会自动为该表在主键上建立聚集索引 该索引同时又是主索引 12 2 IPrimaryandSecondaryIndices cont DatabaseSystemConcepts Chapter12IndexingandHashing 16 一个表上只能建立一个聚集索引 也只能有一个主索引 但可以建立多个非聚集索引如果一个表上没有定义主键 则不会有主索引 但可以为该表建立一
14、个聚集索引主索引一定是聚集索引 但聚集索引不一定是主索引 12 2 IPrimaryandSecondaryIndices cont DatabaseSystemConcepts Chapter12IndexingandHashing 17 实验 对比分析在没有定义主键的关系表中插入数据 在关系表所在数据库文件中 各个元组 行 记录顺序一般是无序 取决于数据插入顺序 heap文件在有主键的关系表中插入数据 数据库文件是有序的 按照主键顺序排列 12 2 IPrimaryandSecondaryIndices cont DatabaseSystemConcepts Chapter12Indexi
15、ngandHashing 18 Secondaryindexanindexwhosesearchkeyspecifiesanorderdifferentfromthesequentialorderofthefile alsocallednon clusteringindexe g Fig 12 5 secondaryindexonbalancefieldofaccountSecondaryindiceshavetobedenseindicesIndex sequentialfile 索引顺序文件 orderedsequentialfilewithaprimary clusteringindex
16、onthesearchkeye g Fig 12 1 12 2 IPrimaryandSecondaryIndices cont DatabaseSystemConcepts Chapter12IndexingandHashing 19 Fig 12 5SecondaryIndexonbalancefieldofaccount 12 2 IPrimaryandSecondaryIndices cont DatabaseSystemConcepts Chapter12IndexingandHashing 20 Denseindextheindexrecordintheindexfileappearsforeverysearch keyvalueintheindexedfileeachvalueofsearch keyintheindexedfilecorrespondstoanindexentryintheindexfilee g Fig 12 1Inadenseprimaryindex theindexrecordcontainsthesearch keyvalueandapointe
