北京大学：《数据结构与算法》课程教学资源（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静态索引 103倒排索引 104动态索引 105动态、静态索引性能比较 北京大学信息学院 @版权所有,转载或翻印必究 Page 2

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

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

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

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

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

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

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

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

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

索引 ■索引( indexing)是把一个关键码与它对 应的数据记录的位置相关联的过程 索引技术是组织大型数据库的一种重要 技术 数据库组织存储在外存中的大量记录 高效率的检索 插入、更新、删除 北京大学信息学院 @版权所有,转载或翻印必究 Page 7

北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 索引 ◼ 索引( indexing )是把一个关键码与它对 应的数据记录的位置相关联的过程 ◼ 索引技术是组织大型数据库的一种重要 技术 ◼ 数据库组织存储在外存中的大量记录 ◼ 高效率的检索 ◼ 插入、更新、删除

索引文件 索引文件( index file)是用于记录这 种联系(关键码与它对应的数据记 录的位置)的文件组织结构。 索引文件的记录 (关键码,指针)对 将每个关键码和一个指针关联 指针指向主要数据库文件(也称为 “主文件”)中的完整记录 北京大学信息学院 @版权所有,转载或翻印必究 Page 8

北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 索引文件 ◼ 索引文件( index file )是用于记录这 种联系（关键码与它对应的数据记 录的位置）的文件组织结构。 ◼ 索引文件的记录 ◼ （关键码，指针）对 ◼ 将每个关键码和一个指针关联 ◼ 指针指向主要数据库文件（也称为 “主文件”）中的完整记录

索引文件 索引文件并不需要重新排列记录在 磁盘中的顺序(不用重排主文件) 个数据库可能有多个相关的索引文 件 每个索引文件往往支持一个关键码字 段 可以通过该索引文件高效访问记录中 该关键码值 北京大学信息学院 @版权所有,转载或翻印必究 Page 9

北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 索引文件 ◼ 索引文件并不需要重新排列记录在 磁盘中的顺序（不用重排主文件） ◼ 一个数据库可能有多个相关的索引文 件 ◼ 每个索引文件往往支持一个关键码字 段 ◼ 可以通过该索引文件高效访问记录中 该关键码值

稠密索引 对每一个记录建立一个索引项, 这样建立的索引被称为稠密索引 dense index 数据库文件中的记录不按照关键 码的顺序排列时(比如按照加入 的顺序排列) 北京大学信息学院 版权所有,转载或翻印必究 Page 10

北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 稠密索引 ◼ 对每一个记录建立一个索引项， 这样建立的索引被称为稠密索引 ( dense index ) ◼ 数据库文件中的记录不按照关键 码的顺序排列时（比如按照加入 的顺序排列）