《索引技术教学》ppt课件

《《索引技术教学》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章索引技术任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所版权所有，转载或翻印必究主要内容10.1线性索引10.2静态索引10.3倒排索引10.4动态索引10.5动态、静态索引性能比较北京大学信息学院版权所有，转载或翻印必究Page基本概念输入顺序文件主码与辅码索引与索引文件稠密索引与稀疏索引北京大学信息学院版权所有，转载或翻印必究Page输入顺序文件输入顺序文件(entry-sequencedfile)按照记录进入系统的顺序存储记录输入顺序文件的结构相当于一个磁盘中未排

2、序的线性表因此不支持高效率的检索北京大学信息学院版权所有，转载或翻印必究Page主码主码(primarykey)是数据库中的每条记录的唯一标识例如，公司职员信息的记录的主码可以是职员的身份证号码如果只有主码，不便于各种灵活检索北京大学信息学院版权所有，转载或翻印必究Page辅码辅码(secondarykey)是数据库中可以出现重复值的码辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来大多数检索都是利用辅码索引来完成的北京大学信息学院版权所有，转载或翻印必究Page索引索引(indexing)是把一个关键码与它对应的数据记录的位置相关联的过程索引技术是组织大型数据库的一种重

3、要技术数据库组织存储在外存中的大量记录高效率的检索插入、更新、删除北京大学信息学院版权所有，转载或翻印必究Page索引文件索引文件(indexfile)是用于记录这种联系（关键码与它对应的数据记录的位置）的文件组织结构。索引文件的记录（关键码，指针）对将每个关键码和一个指针关联指针指向主要数据库文件（也称为“主文件”）中的完整记录北京大学信息学院版权所有，转载或翻印必究Page索引文件索引文件并不需要重新排列记录在磁盘中的顺序（不用重排主文件）一个数据库可能有多个相关的索引文件每个索引文件往往支持一个关键码字段可以通过该索引文件高效访问记录中该关键码值北京大学信息学院版权所有，转载或翻印

4、必究Page稠密索引对每一个记录建立一个索引项，这样建立的索引被称为稠密索引(denseindex)数据库文件中的记录不按照关键码的顺序排列时（比如按照加入的顺序排列）北京大学信息学院版权所有，转载或翻印必究Page稀疏索引对一组记录建立一个索引项，这种索引称之为稀疏索引(spareindex)当记录在磁盘中是按照关键码的顺序存放可以把记录分成多个组（块）稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置北京大学信息学院版权所有，转载或翻印必究Page10.1线性索引基本概念线性索引的优点线性索引的问题二级线性索引北京大学信息学院版权所有，转载或翻印必究Page基本概念线性索引(l

5、inearindex)的索引文件一组简单的关键码(key)/指针(pointer)对的序列北京大学信息学院版权所有，转载或翻印必究Page基本概念（续）线性索引文件按照关键码的顺序进行排序文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置北京大学信息学院版权所有，转载或翻印必究Page基本概念（续）线性索引的索引文件存储在内存中，把索引存储在内存中能大大地提高检索速度存储在磁盘中根据线性索引的文件大小和内存的空间限制北京大学信息学院版权所有，转载或翻印必究Page线性索引的优点对变长的数据库记录的访问可以对数据进行高效检索二分检索顺序处理比较操作批处理的操作节省空间

6、(相对其它索引结构)北京大学信息学院版权所有，转载或翻印必究Page线性索引的问题线性索引太大，存储在磁盘中在一次检索过程中有可能多次访问磁盘，从而影响检索的效率解决办法：使用二级线性索引更新线性索引在数据库中插入或者删除记录时北京大学信息学院版权所有，转载或翻印必究Page二级线性索引每一条二级线性索引记录对应于一个一级线性索引文件的磁盘块关键码的值与对应的线性索引文件的磁盘块中第一条记录(从物理位置上看的第一条)的关键码的值相同记录中的指针则指向相应线性索引文件的磁盘块的起始位置北京大学信息学院版权所有，转载或翻印必究Page二级线性索引例如，磁盘块的大小是1024字节，每个关键码／

7、指针记录需要8个字节，则每磁盘块可以存储128条这样的记录假设线性文件索引中包含10000条记录，那么该线性索引占用79个磁盘块，相应的，二级线性索引文件中有79项记录北京大学信息学院版权所有，转载或翻印必究Page二级线性索引的例子关键码与相应磁盘块中第一条记录的关键码的值相同指针指向相应磁盘块的起始位置北京大学信息学院版权所有，转载或翻印必究Page二级线性索引检索在检索时，线性索引文件并