B-Tree算法

Riguz Lee · 2018-12-18 · 刨根问底, 算法

B-Tree(区别于二叉树)是一种平衡多叉搜索树。

B-Tree的定义

根据Knuth的定义， $𝑚$ 阶的B-Tree有如下的特性：

节点左边的元素都比它小，节点右边的元素都比它大
每个节点最多有 $𝑚$ 个子节点
除了根节点之外，非叶节点（没有孩子的节点）至少有 $𝑚 / 2$ 个子节点
如果根节点不是叶子节点则其至少有两个子节点
包含 $𝑘$ 个子节点的节点共有 $𝑘 - 1$ 个键
所有的叶子节点的高度相同

一般表示B-Tree有两种表示方法：

B-Tree of order $𝑑$ or $𝑀$
B-Tree of degree or $𝑡$

Kuath: B-Tree of Order $𝑑$

其中 $𝑀 = 5$ 表示每一个节点中至多有5个子节点；则有如下的特性：

\begin{aligned} 𝑀 𝑎 𝑥 (𝑐 ℎ 𝑖 𝑙 𝑑 𝑟 𝑒 𝑛) = 5 \\ 𝑀 𝑖 𝑛 (𝑐 ℎ 𝑖 𝑙 𝑑 𝑟 𝑒 𝑛) = 𝑐 𝑒 𝑖 𝑙 (𝑀 / 2) = 3 \\ 𝑀 𝑎 𝑥 (𝑘 𝑒 𝑦 𝑠) = 𝑀 𝑎 𝑥 (𝑐 ℎ 𝑖 𝑙 𝑑 𝑟 𝑒 𝑛) - 1 = 4 \\ 𝑀 𝑖 𝑛 (𝑘 𝑒 𝑦 𝑠) = 𝑀 𝑖 𝑛 (𝑐 ℎ 𝑖 𝑙 𝑑 𝑟 𝑒 𝑛) - 1 = 2 \end{aligned}

(1)

CLRS: B-Tree of min degree $𝑡$

而 $𝑡 = 5$ 则定义了一个节点中至少有5个子节点

\begin{aligned} 𝑀 𝑎 𝑥 (𝑐 ℎ 𝑖 𝑙 𝑑 𝑟 𝑒 𝑛) = 2 𝑡 = 10 \\ 𝑀 𝑖 𝑛 (𝑐 ℎ 𝑖 𝑙 𝑑 𝑟 𝑒 𝑛) = 𝑡 = 5 \\ 𝑀 𝑎 𝑥 (𝑘 𝑒 𝑦 𝑠) = 2 𝑡 - 1 = 9 \\ 𝑀 𝑖 𝑛 (𝑘 𝑒 𝑦 𝑠) = 𝑡 - 1 = 4 \end{aligned}

(2)

这里degree指的是一个节点中子节点的数目。CLRS中用的最小度，即节点中最少有多少个子节点。例如t=2即表示的是2-3-4 tree，每个子节点中可以有2、3或者4个children。

CS673: B-tree of maximum degree k

而也有使用Max degree的，例如DB Virtualization里面，使用的就是最大度（即最多有k个子节点），则：

所有的interior node最少有k/2个children，最多有k个
2-3树即对应到maximum degree of 3

对应关系

这些表示方法的对应关系如下：

可见Order实际等价于max degree。

算法复杂度

根据B-Tree的定义（Min Degree t)，如果Btree的高度为 $ℎ$ , 考虑最少含有多少个key, 则当：

Root节点包含1个key
其他所有节点有且仅有有 $𝑡 - 1$ 个key

这种场景时，所包含的key最少：

设 $𝑆_{ℎ}$ 为Btree第h层的节点数，容易看出:

当 $𝑑 𝑒 𝑝 𝑡 ℎ = 0$ 时， $𝑆_{0} = 1$
当 $𝑑 𝑒 𝑝 𝑡 ℎ = 1$ 时， $𝑆_{1} = 2$
当 $𝑑 𝑒 𝑝 𝑡 ℎ = 2$ 时， $𝑆_{2} = 2 \cdot 𝑡$
当 $𝑑 𝑒 𝑝 𝑡 ℎ = ℎ$ 时， $𝑆_{ℎ} = 2 \cdot 𝑡^{ℎ - 1}$

从 $ℎ = 1$ 开始，每一层的key数目即 ${𝑆 (𝑘 𝑒 𝑦)}_{ℎ} = 𝑆_{ℎ} \dot{𝑡 - 1}$ ，根据等比数列求和公式即可算出总的key数目为：

\begin{aligned} 𝑀 𝑖 𝑛 (𝑘 𝑒 𝑦 𝑠) & = 1 + \sum_{𝑖 = 1}^{ℎ (𝑡 - 1)} \cdot 2 𝑡^{𝑖 - 1} \\ = 1 + (𝑡 - 1) \sum_{𝑖 = 1}^{ℎ} 2 𝑡^{𝑖 - 1} \\ = 1 + 2 (𝑡 - 1) \sum_{𝑖 = 1}^{ℎ} 𝑡^{𝑖 - 1} \\ = 1 + 2 (𝑡 - 1) \frac{1 - 𝑡^{ℎ}}{1 - 𝑡} \\ = 2 𝑡^{ℎ} - 1 \end{aligned}

(3)

设 $𝑛$ 为B-Tree的所有key数，则有：

\begin{aligned} 𝑛 & \geq 𝑀 𝑖 𝑛 (𝑘 𝑒 𝑦 𝑠) \\ = 2 𝑡^{ℎ} - 1 \end{aligned}

(4)

可以得：

ℎ \leq 𝑙 𝑜 𝑔_{𝑡} \frac{1 + 𝑛}{2}

(5)

其算法时间和空间复杂度如下：

B-tree算法实现

search操作

根据B-tree的定义，左边的key都比其小，右边皆比其大，则不应该存在重复的key。查找算法类似于2叉树的查找，步骤如下：

从根节点开始，依次同节点中 $𝑘_{𝑖}$ 进行比较，如果大于或者等于 $𝑘_{𝑖}$ 则停止
如果找到相等的key，则停止搜索
如果没有找到，则到下一级节点中进行查找；如果已经是叶子节点，则查找结束

通常当 $𝑀$ 较小时，我们在节点中查找的时候只需要进行顺序查找即可；如果较大的情况下，可以进行二分查找提高搜索的效率。

B-TREE-SEARCH(x, k)
  i ← 1
  while i ≤ n[x] and k ≥ key[x, i]
    do i ← i + 1
  if i ≤ n[x] and k = key[x, i]
    then return (x, i)
  if leaf[x]
    then return NIL
    else c = DISK-READ(c[x, i])
      return B-TREE-SEARCH(c, k)

insert操作

节点的分裂

在进行insert之前，需要考虑的就是，btree规定了一个节点中最大的child的数目，当一个节点中子节点的数目超过允许的最大值的时候，需要将节点拆分为两个。例如上面的例子，如果再插入20的话，如果直接插入则子元素已经超出了最大允许的数目：

在上面的例子中，拆分之后，两个子节点的元素个数正好是平均的，但是，如果order为偶数的情况下是不平均的：

值得注意的是，因为每次分裂高度会增加，同时会增加父元素的key个数，那么也可能导致父节点满。所以如果上层节点也满了的话，也是需要递归的分裂的：

节点插入过程

当order为奇数时，插入A~Q的过程如下：

当order为偶数时，插入A-J的过程如下：

在Insert的过程中，一般的做法是先将元素插入到叶节点，这时候如果发现叶节点满了，需要将其Split，并将其中一个key提升到父节点中。同时，需要看父节点是否满，如果满了也需要进行拆分，直到根节点。但是这种做法需要插入后再回溯，比较难以实现。另一种方式则是在插入的过程中，一旦发现节点已经满了，无法再容纳元素，则先将其拆分，然后再继续朝下查找。这样只需要查找一次，再最后插入到叶子节点的时候，能够保证不会溢出。

抢占式分裂（Preemtive Split）

如上所说，在insert操作的时候，是先插入元素，然后再进行拆分的，这样可能插入之后还需要一直递归到上层节点进行拆分。例如下面的一个场景：

而Preemtive Split正是在insert之前即进行拆分，当发现一个节点快要满了的时候，就先split之后再插入，自顶向下，不需要再回溯到上一层的节点。

从上面的例子可以看到，两种方式构造出的Btree在插入I之后其实是不大一样的，而当J插入之后则变成一致了。

创建一个空的B-tree

B-TREE-CREATE(T)
  x ← ALLOCATE-NODE()
  leaf[x] ← TRUE
  n[n] ← 0
  DISK-WRITE(x)
  root[T] ← x

删除操作

B-Tree变种

2-3-4树：Order为4的B-tree又被称之为2-3-4 tree (每个非叶子节点有2个、3个或者4个子节点)
2-3树：Order为3的B-tree又被称之为2-3 tree (每个非叶子节点有2个或者3个子节点)
B+-tree：A B-tree in which keys are stored in the leaves.
B*-tree：A B-tree in which nodes are kept 2/3 full by redistributing keys to fill two child nodes, then splitting them into three nodes.

参考资料: