多分树图例 QQ682Q6Q6Q6494929886Q486Q8Q5Q48 叉树转换成多分树 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 多分树图例
上图访问一个叶结点 查找二叉树—访问六次外存 查找多分树—访问两次外存 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 上图访问一个叶结点 ◼ 查找二叉树——访问六次外存 ◼ 查找多分树——访问两次外存
结点更大 以更少的外存访问次数来完成查找 需要较大的缓冲区 n读入一个结点也需较多时间 个结点最好能放在一个磁盘块中 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 ◼ 结点更大 ◼ 以更少的外存访问次数来完成查找 ◼ 需要较大的缓冲区 ◼ 读入一个结点也需较多时间 ◼ 一个结点最好能放在一个磁盘块中
“数据基本区” n多分树的叶结点区域 存放数据记录 索引区” n多分树的非叶结点区域 存放各子树结点中的最大或最小)的关 键码 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 ◼ “数据基本区” ◼ 多分树的叶结点区域 ◼ 存放数据记录 ◼ “索引区” ◼ 多分树的非叶结点区域 ◼ 存放各子树结点中的最大(或最小)的关 键码
溢出、溢出区 ■新记录要插入的结点已满 把溢出的记录存放到另开辟的溢出区 不改变索引的结构 记录送入溢出区的两种方式 保持顺序,把最后一个记录送往溢出 区 不保持顺序,把新插入的记录送入溢 北京大学信息 区 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 ◼ 溢出、溢出区 ◼ 新记录要插入的结点已满 ◼ 把溢出的记录存放到另开辟的溢出区 ◼ 不改变索引的结构 ◼ 记录送入溢出区的两种方式 ◼ 保持顺序，把最后一个记录送往溢出 区 ◼ 不保持顺序，把新插入的记录送入溢 出区