线性索引文件 ■按照关键码的顺序进行排序 文件中的指针指向存储在磁盘上的文件记录起始位置或者主索 引中主码的起始位置 线形索引文件 92 73 37 55 数据库记录 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 线性索引文件 ◼ 按照关键码的顺序进行排序 ◼ 文件中的指针指向存储在磁盘上的文件记录起始位置或者主索 引中主码的起始位置 92 73 37 55 数据库记录 线形索引文件
线性索引的优点 对变长的数据库记录的访问 可以对数据进行高效检索 口二分检索 顺序处理 比较操作 口批处理的操作 节省空间(相对其它索引结构) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 线性索引的优点 ◼ 对变长的数据库记录的访问 ◼ 可以对数据进行高效检索 ❑ 二分检索 ◼ 顺序处理 ❑ 比较操作 ❑ 批处理的操作 ◼ 节省空间 (相对其它索引结构)
线性索引的问题 线性索引太大,存储在磁盘中 口在一次检索过程中可能多次访问磁盘,从而影 响检索的效率 口使用二级线性索引 更新线性索引 口在数据库中插入或者删除记录时 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 线性索引的问题 ◼ 线性索引太大，存储在磁盘中 ❑ 在一次检索过程中可能多次访问磁盘，从而影 响检索的效率 ❑ 使用二级线性索引 ◼ 更新线性索引 ❑ 在数据库中插入或者删除记录时
二级线性索引 ■例如,磁盘块的大小是1024字节,一个(key, point)索引对需要8个字节 a1024/8=128 口每个磁盘块可以存储128条这样的索引对 假设数据文件包含10000条记录 口稠密一级线性索引中包含10000条记录 ■10000/128=78.1 那么一级线性索引占用79个磁盘块 口相应地,二级线性索引文件中有79项索引对 a这个二级线性索引文件可以在一个磁盘块 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二级线性索引 ◼ 例如，磁盘块的大小是1024字节，一个(key， point)索引对需要8个字节 ❑ 1024 / 8 = 128 ❑ 每个磁盘块可以存储128条这样的索引对 ◼ 假设数据文件包含10000条记录 ❑ 稠密一级线性索引中包含10000条记录 ◼ 10000/128 = 78.1 ◼ 那么一级线性索引占用79个磁盘块 ❑ 相应地，二级线性索引文件中有79项索引对 ❑ 这个二级线性索引文件可以在一个磁盘块
二级线性索引的例子 关键码与相应磁盘块中第一条记录的关键码的值 相同 指针指向相应磁盘块的起始位置 二级索引 2003574410723 级索引-1202-054920710mx3133 磁盘块 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二级线性索引的例子 ◼ 关键码与相应磁盘块中第一条记录的关键码的值 相同 ◼ 指针指向相应磁盘块的起始位置 1 2003 5744 10723 1…… 2002 2002 2003 5583 5744 9297 10723 13293 …… …… 磁盘块 一级索引 二级索引