二级线性索引检索 在检索时,线性索引文件并不被读 入内存,被读入内存的是二级线性 索引文件 由于二级索引往往存储内存,通常 只需要访问两次磁盘即可:一次读 入线性索引文件,一次读入数据库 记录 北京大学信息学院 版权所有,转载或翻印必究 Page 21
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 二级线性索引检索 ◼ 在检索时，线性索引文件并不被读 入内存，被读入内存的是二级线性 索引文件 ◼ 由于二级索引往往存储内存，通常 只需要访问两次磁盘即可：一次读 入线性索引文件，一次读入数据库 记录
二级线性索引检索的例子 例如,检索关键码为2555的记录 首先在内存中的二级线性索引文件中找到关键 码的值小于等于2555最大关键码所在的记 录—关键码为2003的记录 ■根据记录中的指针找到其对应的线性索引文件 的磁盘块,并把该块读入内存 ■按照二分法对该块进行检索,找到所需要的记 录在磁盘上的位置 最后把所需记录读入,完成检索操作 北京大学信息学院 版权所有,转载或翻印必究 Page 22
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 二级线性索引检索的例子 例如，检索关键码为2555的记录 ◼ 首先在内存中的二级线性索引文件中找到关键 码的值小于等于2555的最大关键码所在的记 录——关键码为2003的记录 ◼ 根据记录中的指针找到其对应的线性索引文件 的磁盘块，并把该块读入内存 ◼ 按照二分法对该块进行检索，找到所需要的记 录在磁盘上的位置 ◼ 最后把所需记录读入，完成检索操作
102静态索引 1021多分树 10221SAM 北京大学信息学院 版权所有,转载或翻印必究 Page 23
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 10.2 静态索引 ◼ 10.2.1 多分树 ◼ 10.2.2 ISAM
基本概念 静态索引 ■索引结构在文件创建、初始装入记 录时生成 a一生成就固定下来,在系统运行 (例如插入和删除记录过程中索引结 构并不改变 只有当文件再组织时才允许改变索 引结构 北京大学信息学院 版权所有,转载或翻印必究 Page 24
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 基本概念 静态索引 ◼ 索引结构在文件创建、初始装入记 录时生成 ◼ 一旦生成就固定下来，在系统运行 (例如插入和删除记录)过程中索引结 构并不改变 ◼ 只有当文件再组织时才允许改变索 引结构
1021多分树 组织索引一般不用二叉树而采用多 分树 大大减少访问外存的次数 北京大学信息学院 版权所有,转载或翻印必究 Page 25
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 10.2.1 多分树 ◼ 组织索引一般不用二叉树而采用多 分树 ◼ 大大减少访问外存的次数