高级数据库原理第1部分：数据存贮与索引技术

《高级数据库原理第1部分：数据存贮与索引技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容¢顺序文件上的索引结构¢非顺序文件上的辅助索引(SecondaryIndexes)¢B+树¢散列表(HashTables)¢位图索引一、顺序文件上的索引¢顺序文件Searchkey记录按查找键排序10203040506070809010011、密集索引、密集索引(DenseIndexes)(DenseIndexes)¢每个记录都有一个索引项¢索引项按查找键排序11、密集索引、密集索引(DenseIndexes)(DenseIndexes)DenseIndexSequentialFile10102020303040索引项405060501070

2、608070查找键指向记录9080地址的指针1009011010012011、密集索引、密集索引(DenseIndexes)(DenseIndexes)DenseIndexSequentialFile10102020查找：3030查找索引项，4040跟踪指针即可5060507060807090801009011010012011、密集索引、密集索引(DenseIndexes)(DenseIndexes)¢为什么使用密集索引？记录通常比索引项要大索引可以常驻内存要查找键值为K的记录是否存在，不需要访问磁盘数据块¢密集索引缺点？索引占用太多空间用稀疏索引

3、改进22、稀疏索引、稀疏索引(SparseIndexes)(SparseIndexes)¢仅部分记录有索引项¢一般情况：为每个数据块的第一个记录建立索引22、稀疏索引、稀疏索引(SparseIndexes)(SparseIndexes)SparseIndexSequentialFile101030205030704090110501306015070170801909021010023022、稀疏索引、稀疏索引(SparseIndexes)(SparseIndexes)¢有何优点？节省了索引空间对同样的记录，稀疏索引可以使用更少的索引项¢有何缺点？对

4、于“是否存在键值为K的记录？”，需要访问磁盘数据块33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)¢索引上再建索引二级索引、三级索引……33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)Sparse2ndlevelSequentialFile10101090302017050302507040903305011041060130490150570701708019090210100一级索引块的230块地址指针33、多级索引、多级索引(Multi(Multi-

5、-levelIndex)levelIndex)¢多级索引的好处？一级索引可能还太大而不能常驻内存二级索引更小，可以常驻内存减少磁盘I/O次数33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)例：一块＝4KB。一级索引1000010,000个块，每个块可存100个索引项，共40MB。二级稀疏索引100个块，共400KB。按一级索引查找(二分分找查找)：平均lg10000≈13次I/O定位索引块，加一次数据块I/O，共约14次I/O按二级索引查找：定位二级索引块0次I/O，读入一级索引块1次I/O，读入数据块

6、1次I/O，共2次I/O33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)¢当一级索引过大而二级索引可常驻内存时有效¢二级索引仅可用稀疏索引思考：二级密集索引有用吗？¢一般不考虑三级以上索引维护多级索引结构有更好的索引结构——B＋树二、辅助索引二、辅助索引(SecondaryIndex)(SecondaryIndex)¢主索引（PrimaryIndex）顺序文件上的索引记录按索引属性值有序根据索引值可以确定记录的位置¢辅助索引数据文件不需要按查找键有序根据索引值不能确定记录在文件中的顺序辅助索引是稠密索引

7、，每个一搜索码值均有索引记录，对应文件中的数据记录。1020A1040B2010C202050D2030E3010F4050G5060GG20Ff辅助索引的应用：Movie(title,year,length,incolor,studioname,producerC#)Studio(name,address,presc#)SELECTtitle,yearFromMovie,StudioWhdherepresC#=“aa”andmoviie.studidioname=studidio.namedisneyAzzZzld86disney1aasz88di

8、sney2aakistenbdaaalpo96kisten5sdg80kisten3pakesforlaak