B树 学习笔记2 - B树上的基本操作
接上,算法导论 - 18章-2 B树上的基本操作
本节将给出 B-TREE-SEARCH、B-TREE-CREATE 和 B-TREE-INSERT 操作的细节。在这些过程中,我们采用两个约定:
1. B树的根结点始终在主存中,这样无需对根做 DISK-READ 操作;然而,当根结点被改变后,需要对根结点做一次 DISK-WRITE 操作。
2. 任何被当做参数的结点在被传递之前,都要对它们做一次 DISK-READ 操作。我们给出的过程都是“单程”算法,即它们从树的根开始向下,没有任何返回向上的过程。
搜索B树
根据结点的孩子做多路选择。即做 路选择
B-TREE-SEARCH 是 BST 搜索的直接推广,它的输入是一个某结点的指针,以及要在该子树中搜索的一个关键字 。顶层调用标准为 B-TREE-SEARCH( )。
如果 在 B树中,那么返回的是一个有序对( ),其中 ;否则返回 NIL。
B-TREE-SEARCH( )
说明:
第 1-3 行找出下标 ,使得 ,
第 4-5 行检查是否已经找到关键字。
第 6-7 行检查是叶结点,返回NIL。
第 8-9 行向下递归搜索。
总的CPU时间是
创建一棵空的 B树
先用 B-TREE-CREATE 来创建一个空的结点,然后调用 B-TREE-INSERT 来添加新的关键字。这些过程都要用到一个辅助过程 ALLOCATE-NODE,它在 时间内为一个新结点分配一个磁盘页。
B-TREE-CREATE( )
B-TREE-CREATE( ) 需要 次的磁盘操作和 的CPU时间。
向 B树中插入一个关键字
将新关键字插入到一个已经存在的叶节点上。
若满,则分裂,将中间关键字 提升到其父结点 。
为了避免分裂沿树向上传播,在向下查找新的关键字时,就分裂沿途遇到的每个满结点(包括叶结点本身)。
因此,每当要分裂一个满结点 时,就能确保它的父节点不是满的。
分裂 B树中的结点
过程 B-TREE-SPLIT-CHILD 的输入是一个非满的内部结点 (假定在主存中)和一个使 (也假定在主存中)为 的满子结点的下标 。该过程把这个子结点分裂成两个,并调整 ,使之包含多出来的孩子。
要分裂一个满的根,首先要让根称为一个新的空根结点的孩子,这样才能使用 B-TREE-SPLIT-CHILD 。树的高度因此增加1。
分裂根是树长高的唯一途径。
B-TREE-SPLIT-CHILD( ) 分裂
开始时,结点 有 个孩子( 个关键字),在分裂后减少至 个孩子( 个关键字)。结点 拿走 的 个最大的孩子(后半部分),并且 成为 的新孩子,它在 的孩子列中仅位于 之后。 的中间关键字上升到 中,成为分隔 和 的关键字。
代码说明:
第 1-9 行创建结点 , 并将 的 个关键字以及相应的 的孩子给它。
第 10 行调整 的关键字个数。
第11-17 行将 插入为 的孩子,并提升 的中间关键字到 来分隔 和 ,然后调整 的关键字个数。
第 18-20 行写回所有被修改过的磁盘页面。
B-TREE-SPLIT-CHILD 占用的CPU时间为 ,并执行 次磁盘操作。
以沿树单程向下方式向 B树插入关键字
B-TREE-INSERT( )
以沿树单程下行方式插入一个关键字 。
需要 次磁盘存取。所需CPU时间为
过程 B-TREE-INSERT 利用 B-TREE-SPLIT-CHILD 来保证递归始终不会降至一个满结点上。
第 3-9 行处理了根结点 为满的情况:根结点分裂,一个新的结点 (有两个孩子)成为根。(对根进行分裂是增加 B树高度的唯一途径)。
过程通过调用 B-TREE-INSERT-NONFULL 完成将关键字 插入以非满的根结点为根的树中。
B-TREE-INSERT-NONFULL 在需要时沿树向下递归,在必要时通过调用 B-TREE-SPLIT-CHILD 来保证任何时刻它所递归处理的结点都是非满的。
辅助的递归过程 B-TREE-INSERT-NONFULL 将关键字 插入结点 ,要求假定在调用该过程时 是非满的。操作 B-TREE-INSERT 和 B-TREE-INSERT-NONFULL 保证这个假设成立。
第 2 行判断是否为叶结点。
第 3-8 行处理 是叶结点的情况,将关键字 插入 。
若是叶结点,从右端开始右移,并找到合适位置,并调整 的参数,最后写回磁盘。
若不是叶结点,则判断插入位置
第 9-11 行计算应插入的子结点的位置( 则应插入到 )
第 13 行检查是否为满结点。
若是满结点,第 14 行调用分裂函数。
第 15-16 行判断分裂出来的两个结点选择哪一个。
(注:即使i++,也无需DISK-READ,因为刚刚分裂的两个结点都在主存中)
第 17 行递归地将 插入合适的子树中。
对一棵高度为 的 B树来说,B-TREE-INSERT 要做 次磁盘存取。所占用的CPU总时间为 。因为 B-TREE-INSERT-NONFULL 是尾递归的,所以它也可以用一个 while 循环来实现,从而说明了在任何时刻,需要留在主存中的页面数为 。