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

主要内容主要内容„顺序文件上的索引结构„非顺序文件上的辅助索引(SecondaryIndexes)Indexes)„B+树„散列表(HashTables)„位图索引一、顺序文件上的索引一、顺序文件上的索引„顺序文件Searchkey记录按查找键排序2010204030406050608070801009010011、密集索引、密集索引(DenseIndexes)(DenseIndexes)„每个记录都有一个索引项„索引项按查找键排序11、密集索引、密集索引(DenseIndexes)(DenseIndexes)SequentialFileDenseIndex2010102040303040索引项6050506070索引项1080708090查找键指向记录10090100110120地址的指针11、密集索引、密集索引(DenseIndexes)(DenseIndexes)SequentialFileDenseIndex2010102040303040查找：查找索引项，跟踪指针即可6050506070跟踪指针即可807080901009010011012011、密集索引、密集索引(DenseIndexes)(DenseIndexes)„为什么使用密集索引？记录通常比索引项要大索引可以常驻内存索引可以常驻内存要查找键值为K的记录是否存在，不需要访问磁盘数据块„密集索引缺点？索引占用太多空间用稀疏索引改进22、稀疏索引、稀疏索引(SparseIndexes)(SparseIndexes)„仅部分记录有索引项„一般情况：为每个数据块的第一个记录建立索引立索引22、稀疏索引、稀疏索引(SparseIndexes)(SparseIndexes)SequentialFileSparseIndex201010305040305070906050701101301508070901501701901009019021023022、稀疏索引、稀疏索引(SparseIndexes)(SparseIndexes)„有何优点？节省了索引空间对同样的记录稀疏索引可以使用更少的索对同样的记录，稀疏索引可以使用更少的索引项„有何缺点？对于“是否存在键值为K的记录？”需要访对于是否存在键值为K的记录？，需要访问磁盘数据块33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)„索引上再建索引二级索引、三级索引……33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)SequentialFileSparse2ndlevel20101030501090170403050709017025060509011013015033041049080709015017019057010090190210230一级索引块的块地址指针块地址指针33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)„多级索引的好处？一级索引可能还太大而不能常驻内存二级索引更小可以常驻内存二级索引更小，可以常驻内存减少磁盘I/O次数33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)例块4KB级索引10000个块每个块例：一块＝4KB。一级索引10,000个块，每个块可存100个索引项，共40MB。二级稀疏索引100个块共400KB个块，共400KB。按一级索引查找(二分查找)：平均按级索引找(分找)平均lg10000≈13次I/O定位索引块，加一次数据块I/O，共约14次I/O共约次按二级索引查找：定位二级索引块0次I/O，读入级索引块1次I/O读入数据块1次I/O共2入一级索引块1次I/O，读入数据块1次I/O，共2次I/O33、多级索引、多级索引(Multi(Multi--levelIndex)levelIndex)„当一级索引过大而二级索引可常驻内存时有效„二级索引仅可用稀疏索引„二级索引仅可用稀疏索引思考：二级密集索引有用吗？„一般不考虑三级以上索引维护多级索引结构维护多级索引结构有更好的索引结构——B＋树二、辅助索引二、辅助索引(SecondaryIndex)(SecondaryIndex)„主索引（PrimaryIndex）顺序文件上的索引记录按索引属性值有序记录按索引属性值有序根据索引值可以确定记录的位置„辅助索引数据文件不需要按查找键有序数据文件不需要按查找键有序根据索引值不能确定记录在文件中的顺序根据索引值能确定在件中顺序辅助索引是稠密索引，每个一搜索码值均有索引记录对应文件中的数据记录，对应文件中的数据记录。20A1020A40B10102010C202010C2050D50D30E10F203010F50G60GG405060GG20Ff辅助索引的应用：Movie(title,year,length,incolor,studioname,producerC#)Studio(name,address,presc#)SELECTtitle,yearFromMovie,StudiohdididiWherepresC#=“aa”andmovie.studioname=studio.namedisneyAzzld86disney1sz88disney2kibdZzaakistenbdaaalpo96kisten5sdg80kisten3aasdg80kisten3pakesforlaakaw96pakes6frr1997pakes711、辅助索引概念、辅助索引概念上创建了主索引记录按有序MovieStar(namechar(10)PRIMARYKEY,addresschar(20))„Name上创建了主索引，记录按name有序„Address上创建辅助索引„Address上创建辅助索引CreateIndexadIndexOnMovieStar(address)22、辅助索引设计、辅助索引设计密集索引50301020507020203040704080506070401010070...10609022、辅助索引设计、辅助索引设计密集索引3010密集索引二级稀疏索引507020203040105070408050605090...40101006070...10609060„一个典型的辅助索索引。„数据文件中每个„数据文件中每个块存放二个记录记录只显示了。记录只显示了各自的查找键；其值为整型„这里的数据没有„这里的数据没有按查找键排序。22、辅助索引设计、辅助索引设计„需要辅助索引的常见数据结构是聚集文件。假设有关系和中的组和中的组具有多假设有关系R和S，R中的元组和S中的元组具有多对一的对应关系。种组织结构是把关系的每个元组和关系中相关一种组织结构是把关系R的每个元组和关系S中相关的元组存储在一起另一种结构是按照主键来存储关系R。前一种结构在某些情况下更加合理前一种结构在某些情况下更加合理。„举例：考虑movie和studio两个关系Movie(title,year,length,genre,studioName,producerC#)roducerC#)Studio(name,address,presC#)„进一步假定查询的常见形式如下：SELECTtitle,yearFROMMiStdiFROMMovie,StudioWHEREpresC#=zzzandWHEREpresC#zzzandMovie.studioName=Studio.name„zzz可以表示任意制片厂经理的证件号即:„zzz可以表示任意制片厂经理的证件号，即:已知一个制片厂的经理，需要找到由该制片厂制作的所有电影厂制作的所有电影。„如果上面这类查询是典型的查询，则:可不按主键title和year排序而是为Studio和Movie两个关系建立一个聚而是为Studio和Movie两个关系建立一个聚集文件结构,即在每个Studio的元组后面存放关系Movie中该制片厂的所有电影元组。„如果为关系Studio在查找键presC#上建立索引那么不管zzz是什么都可以快速地找到引，那么不管zzz是什么，都可以快速地找到所有符合条件的制片厂的元组。„并且，Movie中所有studioName属性和某个制片厂的name属性匹配的元组，都会在聚制片厂的name属性匹配的元组，都会在聚集文件中紧跟在该制片厂的元组后出现。可以用尽量少的几次I/O就找到该制片厂的所„可以用尽量少的几次I/O就找到该制片厂的所有电影，因为要查找的Movie元组已经以尽可能稠密的方式存储在紧跟着的数据块里。问问题题„重复键值怎么处理？33、辅助索引中的间接桶、辅助索引中的间接桶„重复键值采用密集索引浪费空间采用密集索引浪费空间假如某个索引键值在数据文件中出现n次，那么这个假如某个索引键值在数据文件中出现次，那么这个键值在索引文件中就要写n次只为指向该键值的所有指针存储一次键值比较好只为指向该键值的所有指针存储一次键值，比较好„间接桶介于辅助索引和数据文件之间的间接层每个查找键K有个键指针对指针指向个桶文每个查找键K有一个键-指针对，指针指向一个桶文件，该文件中存放K的桶。从这个位置开始，直到索引指向的下一个位置，其间指针指向索引键值为K的所有记录。33、辅助索引中的间接桶、辅助索引中的间接桶10201020402020304040105060401030...4030bkt使用辅助索引节省buckets使用辅助索节省空间情况„考虑一个关系：Movie(titleyearlengthgenrestudioNaMovie(title,year,length,genre,studioName,producerC#)„假设在studioName和year上都建立了有间接桶的辅助索引间接桶的辅助索引„若我们要执行如下查询：找出Disney在年制作的所有电影2005年制作的所有电影SELECTtitleFROMMovieWHEREstudioName=‘Disney’andyear=2005WHEREstudioName=‘Disney’andyear=2005„通过studioName上的索引------找出所有指向Disney制作的电影的指针向Disney制作的电影的指针„但是，并不把这些记录从磁盘上取到主存中但是并不把这些记录从磁盘取到主存中„而是，通过year上的索引-------再找出所有指向2005年制作的电影的指针指向2005年制作的电影的指针。„然后，求两个指针集的交集------正好得到„然后，求两个指针集的交集正好得到2005年Disney制作的所有电影。„最后，到磁盘上去检索所有包含一部或几部这样的电影的块，这样只需检索尽可能少的这样的电影的块，这样只需检索尽可能少的数据块。一种带有间接桶层的辅助索引结构一种带有间接桶层的辅助索引结构44、倒排索引、倒排索引(InvertedIndex)(InvertedIndex)„应用于文档检索，与辅助索引思想类似„不同之处记录Æ文档记录Æ文档记录查找Æ文档检索查找键Æ文档中的词想„思想为每个检索词建立间接桶为每个检索词建立间接桶桶的指针指向检索词所出现的文档文档文档„一个文档可被看成是关系Doc的元组。这个关系有很多的属性，每个属性对应于文档可能出现的一个词。每个属性都是布尔档可能出现的个词每个属性都是布尔型的—表明该词在该该文档出现还是没有出现。因此，这一关系模式可以被看作：出现。因此，这关系模式可以被看作：Doc(hasCat,hasDog,…)„其中hasCat取值为真当且仅当该文档中至少出现一次“cat”这个词。少出现次cat这个词。44、倒排索引、倒排索引(InvertedIndex)(InvertedIndex)44、倒排索引、倒排索引(InvertedIndex)(InvertedIndex)扩充倒排索引的桶以包含更多信息桶中的插入与删除桶中的插入与删除„可以用这种数据结构来回答关于文档的各种种查询，而且不用仔细