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

线性索引文件 按催德的搬法信在 始位置或者主索引中主码的起始位置 55 3 92 线性索引文件 92 7337 55 数据库记录 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 11

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 线性索引文件 „ 按照关键码的顺序进行排序 „ 文件中的指针指向存储在磁盘上的文件记录起 始位置或者主索引中主码的起始位置 37 55 73 92 92 73 37 55 线性索引文件 数据库记录

线性索引的优点 对变长的数据库记录的访问 可以对数据进行高效检索 n二分检索 顶序处理 比较操作 批处理的操作 n节省空间(相对其它索引结构) 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 12

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 线性索引的优点 „ 对变长的数据库记录的访问 „ 可以对数据进行高效检索 „ 二分检索 „ 顺序处理 „ 比较操作 „ 批处理的操作 „ 节省空间 (相对其它索引结构)

线性索引的问题 线性索引太大,存储在磁盘中 在一次检索过程中可能多次访问 磁盘,从而影响检索的效率 使用二级线性索引 更新线性索引 在数据库中插入或者删除记录时 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 13

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 线性索引的问题 „ 线性索引太大，存储在磁盘中 „ 在一次检索过程中可能多次访问 磁盘，从而影响检索的效率 „ 使用二级线性索引 „ 更新线性索引 „ 在数据库中插入或者删除记录时

二级线性索引 例如,磁盘块的大小是1024字节,每对 (关键码,指针)索引对需要8个字节 1024/8=128 每磁盘块可以存储128条这样的索引对 假设数据文件包含10000条记录 稠密一级线性索引中包含10000条记录 10000/128=78.1 n那么一级线性索引占用79个磁盘块 相应地,二级线性索引文件中有79项索引对 这个二级线性索引文件可以在一个磁盘块 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 14

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 二级线性索引 „ 例如，磁盘块的大小是1024字节，每对 (关键码，指针)索引对需要8个字节 „ 1024 / 8 = 128 „ 每磁盘块可以存储128条这样的索引对 „ 假设数据文件包含10000条记录 „ 稠密一级线性索引中包含10000条记录 „ 10000/128 = 78.1 „ 那么一级线性索引占用79个磁盘块 „ 相应地，二级线性索引文件中有79项索引对 „ 这个二级线性索引文件可以在一个磁盘块

二级线性索引的例子 ■关键码与相应磁盘块中第一条记录的关键码的 值相同 ■指针指向相应磁盘块的起始位置 二级索引 2003574410723 1..200220035583574492971072313293 级索引 磁盘块 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 15

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 二级线性索引的例子 „ 关键码与相应磁盘块中第一条记录的关键码的 值相同 „ 指针指向相应磁盘块的起始位置 1 2003 5744 10723 1…… 2002 2003 5583 5744 9297 10723 13293 …… …… 磁盘块 一级索引 二级索引