每周学点大数据 | No.26外存数据结构——B 树

No.26期

外存数据结构——B 树

小可：看来在磁盘上二叉搜索树对新来的数据插入树中支持得不好，那么究竟怎么解决这个问题呢？

Mr. 王：有一个非常经典的解决方案，叫作B 树。

小可：B 树？这个B 树和二叉搜索树有什么区别呢？

Mr. 王：顾名思义，二叉搜索树是二叉的，这个B 树就是B 叉的。BFS 块自然对应于每个节点出度为Q(B) 的一棵树。而且在每一个磁盘块中，不放置来自树的多层的数据项，只放一层中的数据项。这样做的一大好处是，更新都可以通过变化节点的度来实现，此时我们进行树的平衡操作时，不再依赖旋转，而是利用节点的分裂和合并。

小可：太抽象了，这样说还是不太懂。

Mr. 王：好，我们来看一个例子。

这就是一棵B 树。可以注意到，B 树上的每一个节点都有k 个值和k+1 个指针。每一个值两侧的指针，分别表示小于它和大于它的子树。比如13 左侧的指针指向小于13 的子树，13和17 之间的指针指向键值在13 和17 之间的子树，依此类推。

举一个查找的例子吧。

当我们要查找键值17 的时候，首先会和树根进行比较，17>13，所以要继续访问右子树，将其右子树的这个磁盘块读入内存进行处理，在右边的子树中发现17<23，所以在23 的左子树中，再将这一块读入内存中，然后在它的左子树的根节点中找到了键值17。

小可：这样看来，B 树的查找效率很高啊。

Mr. 王：不过这里我们要研究一下，满足什么样性质的B 树才能有这样高的查找效率。这里提出一个概念叫作(a,b) 树。

小可：这个(a,b) 分别表示什么呢？

Mr. 王：a,b 分别表示键值数量的上界和下界。

如果T 是一棵(a,b) 树（a ≥ 2 且b ≥ 2a-1），那么它应该满足下面三个条件：

— 所有的叶子在同一层上并且包括a 到b 个元素。

— 除了根节点，所有的节点的度在a 到b 之间。

— 根节点的度在2 到b 之间。

这里先以(2,4) 树为例。这样的树，在空间上是线性的，即O(N/B)。

小可：这是为什么呢？

Mr. 王：首先，我们要存储的数据项有N 个，将它们都存到叶子节点中。而每个节点的度均在(a,b) 之间，即使在最坏的情况下，每个节点只有两个出度，此时内部节点的数量也是小于叶子节点的。更何况多数节点是在a,b 之间的，内部节点数小于叶子节点数，说明它是线性空间的。

当所有节点的出度都是a 时，树的高度h 刚好是O(logaN)，而节点的度普遍大于a，所以logaN 是树高度的上界。同时我们选取a,b 与B 同阶，即a,b=Q(B)，这样每个节点或者说每个叶子节点都能恰好装在一个磁盘块中。进行查找的时间复杂度就是O(logBN)。

小可：这是因为B 与a 同阶吧？

Mr. 王：是的，我们进行了替换，使其与我们使用的参数相关联。

小可：到现在为止，我们研究的都是关于B 树的性质和对建好的B 树的使用，那么一棵B 树是怎么建立起来的呢？

Mr. 王：好，接下来我们就谈谈B 树的插入和删除。首先看插入，这是建立B 树和新增数据项时维护B 树的过程。

当某个节点容纳的数据项没有超过其限制b 时，这种插入就很朴素了，我们讨论的关键是当节点v 上面有b+1 个元素时，对v 如何处理。

此时我们要拆分节点v，即创建节点v’和v”，让它们分别有

个元素。根据前面的约定，可以保证

，但此时，消除了v 却产生了两个新的节点，所以我们要把元素或指针插入parent(v)。

这里还涉及一个问题，如果在拆分的过程中其父亲节点也填满了，那么还要再去拆分它的父亲节点；如果父亲节点的父亲节点也填满了，那么还要去拆分它的父亲节点的父亲节点。

小可：可是这一路拆分上去，恰好根节点也填满了，拆到了根节点怎么办？

Mr. 王：那就把根节点也拆了，使B 树升高一层就可以了啊。现在想想，一次拆分会涉及多少个节点？

小可：自底向上的拆分和自顶向下的搜索应该是一致的，也是从树叶到达树根，最多再在树根上面加一层，所以都是O(logaN)。

Mr. 王：很好，接下来我们讨论(a,b) 树的删除操作。在正常情况下，我们将需要删除的元素从树中剔除就可以了。那么什么情况下会出现问题呢？

小可：我觉得和插入是同理的，当某个节点出现a-1 个儿子节点时，就不行了。

Mr. 王：所以当v 有a-1 个元素/ 儿子节点时，将v 和兄弟节点v’ 合并，将v’的儿子节点移到v’，再从v 的父亲节点中删除相应的元素和指针。一旦有需要，根节点被删除了也是有可能的，此时B 树的高度会降低一层。

小可：我考虑到这样一种情况，如果合并之后又发现节点中的数据项数目大于b 了，是不是还要拆分啊？

Mr. 王：没错，如果真的出现这种情况，还要按照插入的形式拆分v，最终使得整棵树满足(a,b)树的性质。同样，这个过程也是要递归进行的，(a,b) 树也是涉及O(logaN) 个节点。

接下来我们来总结一下B 树的性质。

B 树：(a,b 树，其中a,b=Q(B)。它满足O(N/B) 空间、O(logB N) 查询、O(logB N) 更新。另外，元素都在叶子节点中的B 树有时被称为B+ 树。

建立一棵B 树需要

次I/O。这个复杂度包括排列元素、创建叶子节点，以及从底向上一层层建树。可以看出，B 树是一种性质非常好的数据结构，其广为做磁盘算法的计算机科学家所热爱。有一位著名的计算机科学家，更是在他的主页中写道：我喜欢B 树。

小可：有空我是不是也应该试着去实现一棵B 树呢？

Mr. 王：如果是要在开发软件系统中使用B 树，不妨参考一些开源关系数据库的源代码，那里面一定有优质的B 树的实现。

内容来源：灯塔大数据