线性索引的问题 二级线性索引 线性索引太大,存储在磁盘中 例如,磁盘块的大小是1024字节,每对 (关键码,指 需要8个字节 在一次检索过程中可能多次访问 1024/8=128 磁盘,从而影响检索的效率 每磁盘块可以存储128条这样的索引对 使用二级线性索引 假设数据文件包含10000条记录 稠密一级线性索引中包含10000条记录 更新线性索引 10000/128=78.1 那么一级绒性索引占用79个微盘块 在数据库中插入或者删除记录时 相应地,二级线性索引文件中有项索引对 这个二级线性索引文件可以在一个磁盘块 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 例如:检索关健码为2555的记录 关键字2555的记录指针 级线性索引的例子 级索弓 10723 关键码与相应磁盘块中第一条记录的关键码的 200220035583574492971072313293 值相同 ■指针指向相应磁盘块的起始位置 级索引□1mkH 键码为2555的记录 1.二量线性索引文件碳入内存 所在一最囊引磁煮块地址一 级索引 3中的地址指针找到其对应的一版敢性引文件的微盘 微块 4.挽属二分抽对该换遊行检囊,找到所需的记录在敬盘上的位置 LF最后把所雷记读入完成检囊燥作 张铭帖编写 102静态索引 1021基本概念 令基本概念 静态索引 令1021多分树 案时馥在文件创建、初始入记 令10.22sAM 例辅哭删高;種到结 构并不改变 导有蒋文件再组织时才允许改变索 北京大息学 张铭 权质有,印究 张帖写 权新有:命些3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 线性索引的问题 „ 线性索引太大，存储在磁盘中 „ 在一次检索过程中可能多次访问 磁盘，从而影响检索的效率 „ 使用二级线性索引 „ 更新线性索引 „ 在数据库中插入或者删除记录时 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 二级线性索引 „ 例如，磁盘块的大小是1024字节，每对 (关键码，指针)索引对需要8个字节 „ 1024 / 8 = 128 „ 每磁盘块可以存储128条这样的索引对 „ 假设数据文件包含10000条记录 „ 稠密一级线性索引中包含10000条记录 „ 10000/128 = 78.1 „ 那么一级线性索引占用79个磁盘块 „ 相应地，二级线性索引文件中有79项索引对 „ 这个二级线性索引文件可以在一个磁盘块 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 二级线性索引的例子 „ 关键码与相应磁盘块中第一条记录的关键码的 值相同 „ 指针指向相应磁盘块的起始位置 1 2003 5744 10723 1…… 2002 2003 5583 5744 9297 10723 13293 …… …… 磁盘块 一级索引 二级索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 例如：检索关键码为2555的记录 1. 二级线性索引文件读入内存 2. 二分法找关键码的值小于等于2555的最大关键码所在一级索引磁盘块地址—— 关键码为2003的记录 3.根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘 块，并把该块读入内存 4. 按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置 5. 最后把所需记录读入，完成检索操作 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 10.2 静态索引 „ 基本概念 „ 10.2.1 多分树 „ 10.2.2 ISAM 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 10.2.1 基本概念 静态索引 „ 索引结构在文件创建、初始装入记 录时生成 „ 一旦生成就固定下来，在系统运行 (例如插入和删除记录)过程中索引结 构并不改变 „ 只有当文件再组织时才允许改变索 引结构