例如:检索关键码为2555的记录 关键字2555的记录指针 二级索引1 2c03 5744 10723 线性索引1 20022003 55831574492971072313293 磁盘块 关键码为2555的记录 1.二级线性索引文件读入内存 2.二分法找关键码的值小于等于2555的最大关键码所在一级索引磁盘块地址 关键码为2003的记录 3根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘 块,并把该块读入内存 4.按照二分法对该块进行检索,找到所需要的记录在磁盘上的位置 5最后把所需记录读入,完成检索操作 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 16
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 例如：检索关键码为2555的记录 1. 二级线性索引文件读入内存 2. 二分法找关键码的值小于等于2555的最大关键码所在一级索引磁盘块地址—— 关键码为2003的记录 3.根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘 块，并把该块读入内存 4. 按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置 5. 最后把所需记录读入，完成检索操作
102静态索引 令基本概念 1021多分树 610.2. ISAM 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 17
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 10.2 静态索引 基本概念 10.2.1 多分树 10.2.2 ISAM
1021基本概念 静态索引 索引结构在文件创建、初始装入记 录时生成 一旦生成就固定下来,在系统运行 例如插入和删除记录过程中索引结 构并不改变 只有当文件再组织时才允许改变索 引结构 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 18
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 10.2.1 基本概念 静态索引 索引结构在文件创建、初始装入记 录时生成 一旦生成就固定下来，在系统运行 (例如插入和删除记录)过程中索引结 构并不改变 只有当文件再组织时才允许改变索 引结构
1022多分树 组织索引一般不用二叉树而采用多 分树 大大减少访问外存的次数 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 19
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 10.2.2 多分树 组织索引一般不用二叉树而采用多 分树 大大减少访问外存的次数
数据12.6364的二分索引 6次访问索引块 查找63 1次访问外存数据块 61 123456789 6364 二叉树 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 20
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 1 1 33 1 49 1 57 1 123 45 67 8 9………. 二叉树 数据1,2…63,64的二分索引 查找63 61 64 6次访问索引块 63 1次访问外存数据块