二叉树转换成多分树… 2次访问索引块 1次访问外存数据块 :::::: 9.9.92.Q..Q.2Q99.Q2999a9Q 63 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 21
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 二叉树转换成多分树 63 2次访问索引块 1次访问外存数据块
“数据基本区” 多分树的叶结点区域 存放数据记录 索引区” n多分树的非叶结点区域 存放各子树结点中的最大(或最小)的关 键码 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 22
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 “数据基本区” 多分树的叶结点区域 存放数据记录 “索引区” 多分树的非叶结点区域 存放各子树结点中的最大(或最小)的关 键码
溢出、溢出区 ■新记录要插入的结点已满 把溢出的记录存放到另开辟的溢出区 不改变索引的结构 ■记录送入溢出区的两种方式 保持顺序,把最后一个记录送往溢出区 不保持顺序,把新插入的记录送入溢出 区 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 23
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 溢出、溢出区 新记录要插入的结点已满 把溢出的记录存放到另开辟的溢出区 不改变索引的结构 记录送入溢出区的两种方式 保持顺序，把最后一个记录送往溢出区 不保持顺序，把新插入的记录送入溢出 区
1022 ISAM ■ISAM是解决需要频繁更新的大型 数据库的一个早期尝试 在采用基于B树的VAM技术之 前,IBM公司曾经广泛地采用 ISAM技术 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 24
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 10.2.2 ISAM ISAM是解决需要频繁更新的大型 数据库的一个早期尝试 在采用基于B+树的VSAM技术之 前，IBM公司曾经广泛地采用 ISAM技术
多分树的应用 为磁盘存取而设计 结构采用多级索引 主索引 柱面索引 磁道索引 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 25
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 多分树的应用 为磁盘存取而设计 结构采用多级索引 主索引 柱面索引 磁道索引