北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第十章 索引技术

数据结构与算法 第十章索引技术 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds/ zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究

数据结构与算法 第十章 索引技术 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究

主要内容 令基本概念 101线性索引 102静态索引 Q103倒排索引 104动态索引 令105动态、静态索引性能比较 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 基本概念 „ 10.1 线性索引 „ 10.2 静态索引 „ 10.3 倒排索引 „ 10.4 动态索引 „ 10.5 动态、静态索引性能比较

基本概念 ●输入顺序文件 令主码与辅码 索引与索引文件 稠密索引与稀疏索引 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 基本概念 „ 输入顺序文件 „ 主码与辅码 „ 索引与索引文件 „ 稠密索引与稀疏索引

输入顺序文件 输入顺序文件(enry- -sequenced file) 按照记录进入系统的顺序存储记录 般说来,输入顺序文件的结构相当 于一个磁盘中未排序的线性表 因此不支持高效率的检索 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 输入顺序文件 „ 输入顺序文件( entry-sequenced file ) 按照记录进入系统的顺序存储记录 „ 一般说来，输入顺序文件的结构相当 于一个磁盘中未排序的线性表 „ 因此不支持高效率的检索

主码 主码( primary key)是数据库中的每 条记录的唯一标识 例如,公司职员信息的记录的主码可 以是职员的身份证号码 如果只有主码,不便于各种灵活检索 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 主码 „ 主码( primary key )是数据库中的每 条记录的唯一标识 „ 例如，公司职员信息的记录的主码可 以是职员的身份证号码 „ 如果只有主码，不便于各种灵活检索

辅码 辅码( secondary key)是数据库中可以出 现重复值的码 ■辅码索引把一个辅码值与具有这个辅码 值的每一条记录的主码值关联起来 n大多数检索都是利用辅码索引来完成的 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 辅码 „ 辅码( secondary key )是数据库中可以出 现重复值的码 „ 辅码索引把一个辅码值与具有这个辅码 值的每一条记录的主码值关联起来 „ 大多数检索都是利用辅码索引来完成的

索引 索引( indexing)是把一个关键码与它对应的数 据记录的位置相关联的过程 关键码,指针)对,即(key, pointer 指针指向主要数据库文件(也称为“主文件”)中的 完整记录 索引文件( index file)是用于记录这种联系的文 件组织结构 索引技术是组织大型数据库的一种重要技术 高效率的检索 插入、更新、删除 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 7

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 索引 „ 索引( indexing )是把一个关键码与它对应的数 据记录的位置相关联的过程 „ (关键码，指针)对，即(key, pointer) „ 指针指向主要数据库文件（也称为“主文件”）中的 完整记录 „ 索引文件( index file )是用于记录这种联系的文 件组织结构 „ 索引技术是组织大型数据库的一种重要技术 „ 高效率的检索 „ 插入、更新、删除

索引文件 一个主文件可能有多个相关索引 文件 每个索引文件往往支持一个关键 码字段 不需要重新排列重排主文件 ■可以通过该索引文件高效访问记 录中该关键码值 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 索引文件 „ 一个主文件可能有多个相关索引 文件 „ 每个索引文件往往支持一个关键 码字段 „ 不需要重新排列重排主文件 „ 可以通过该索引文件高效访问记 录中该关键码值

稠密索引ⅴs稀疏索引 稠密索引:对每个记录建立一个索引项 主文件不按照关键码的顺序排列 稀疏索引:对一组记录建立一个索引 记录按照关键码的顺序存放 可以把记录分成多个组(块) 索引指针指向的这一组记录在磁盘中的起始位置 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 稠密索引 vs 稀疏索引 „ 稠密索引：对每个记录建立一个索引项 „ 主文件不按照关键码的顺序排列 „ 稀疏索引：对一组记录建立一个索引 „ 记录按照关键码的顺序存放 „ 可以把记录分成多个组（块） „ 索引指针指向的这一组记录在磁盘中的起始位置

101线性索引 基本概念 令线性索引的优点 ◆线性索引的问题 令二级线性索引 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 10

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 10.1 线性索引 „ 基本概念 „ 线性索引的优点 „ 线性索引的问题 „ 二级线性索引