数据12.6364的二分索引 1022多分树 6次访问紫引块 查找63 1次访问外存数据块 组织索引一般不用二叉树而采用多 分树 大大减少访问外存的次数 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 叉树转换成多分树 2次访问索引块 1次访问外存数据块 “数据基本区” 多分树的叶结点区域 存放数据记录 索引区 多分树的非叶结点区域 存放各子树结点中的最大(或最小的关 张铭帖编写 叔所有,轨圆即 孔写 10.22 ISAM 溢出、溢出区 新记录要插入的结点已满 ISAM是解决需要频繁更新的大型 把溢出的记录存放到另开辟的溢出区 数据库的一个早期尝试 不改变索引的结构 在采用基于B树的WAM技术之 ■记录送入溢出区的两种方式 前,IBM公司曾经广泛地采用 保持顺序,把最后一个记录送往溢出区 ISAM技术 ■不保持顺序,把新插入的记录送入溢出 北京大息学 张铭 政■印究 张帖写 权新有:命些4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 10.2.2 多分树 „ 组织索引一般不用二叉树而采用多 分树 „ 大大减少访问外存的次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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次访问外存数据块 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 二叉树转换成多分树 63 2次访问索引块 1次访问外存数据块 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 „ “数据基本区” „ 多分树的叶结点区域 „ 存放数据记录 „ “索引区” „ 多分树的非叶结点区域 „ 存放各子树结点中的最大(或最小)的关 键码 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 „ 溢出、溢出区 „ 新记录要插入的结点已满 „ 把溢出的记录存放到另开辟的溢出区 „ 不改变索引的结构 „ 记录送入溢出区的两种方式 „ 保持顺序，把最后一个记录送往溢出区 „ 不保持顺序，把新插入的记录送入溢出 区 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 10.2.2 ISAM „ ISAM是解决需要频繁更新的大型 数据库的一个早期尝试 „ 在采用基于B+树的VSAM技术之 前，IBM公司曾经广泛地采用 ISAM技术