综述
本文主要介绍B树的概念、方法以及实现。本文的完整代码可以在我的github找到。
概念
m阶B树的性质为：
- 树中每个结点最多含有m个孩子
- 除根结点外，每个分支结点至少有$\lfloor{m/2}\rfloor$根子树
- 若根结点不是叶子结点，则其至少有两个孩子
- 所有的叶结点位于同一层
在算法导论中，B树的定义略有不同，一棵B树T是具有以下性质的有根树：
- 每个结点x具有以下属性：
- x.n，当前存储在结点x中的关键字
- x.n个关键字本身$x.key_0, x.key_1, x.key_2, …, x.key_{n-1}$，以非降序存放
- x.leaf，bool值。如果x为叶结点，则为TRUE; 否则为FALSE
- 每个结点x还包含x.n+1个指向其孩子的指针$x.c_0, x.c_1, x.c_2, …, x.c_{n-1}$, 叶结点没有孩子，所以它们的$c_i$属性没有定义。
- 每个结点x以其关键字进行分割，即$x.key_{i-1}<= k <= x.key_i$，则关键字k所在的结点在以$x.c_i$为根的子树上。
- 每个叶结点具有相同的深度，即树的高度h。
- 每个结点所包含的关键字个数有上界和下界。以最小度数$t>=2$来表示这些界。除了根结点以外的每个结点包含的结点个数满足$t-1 <= x.n <= 2t-1$。
这两种定义基本是一致的，接下来，我们将主要按照算法导论上的定义来实现。B树的树高$h<=\log_t\frac{n+1}{2}$。
B树的方法
与二叉搜索树类似，B树主要有查找、插入与删除等算法。其python代码示例如下：1
2
3
4
5
6
7
8
9
10
11class Node:
def __init__(self):
self.parent = None
self.keys = []
self.children = []
class BTree:
def __init__(self, t):
self.t = t
self.root = None
这里定义了如果结点为叶结点，则其children为[]。因此可以用 if node.children判断其是否为叶结点。
查找
与二叉搜索树类似，B树的查找也采用递推的方式，根据B树的性质，第一个不小于k值的$x.key_i$，即为要查找的结点，或者存在于以x.children[i]为根的子树中。易知， 其时间复杂度为O(tlogn)。1
2
3
4
5
6
7
8
9
10
11
12
13
14def search(self, k):
current = self.root
while current:
i, key = 0, current.keys[0]
for i, key in enumerate(current.keys):
if k <= key:
break
if k == key:
return current, i
elif current.children:
current = current.children[i]
else:
return None
插入
新插入的结点总是插入在叶结点中，而插入操作可能会导致插入的叶结点其关键字超过$2t-1$，为了解决这一问题，假设此叶结点为x，我们需要将结点x分裂成两个结点，从而导致x的父节点的关键字超出其最大值$2t-1$。为了避免这种情况的发生，我们需要保证，从根结点到要插入的叶结点的路径上的结点关键字小于最大值$2t-1$。算法的借本思路如下：
- 如果根结点为空，则将新建结点使其成为根结点，并将关键字加入其中。否则执行步骤2。
- 如果根结点$len(root.keys) == 2t-1$，新增一个空结点，使其成为新的根结点，原来的根结点成为其孩子。然后分裂此结点，使其非满，并执行步骤3，否则执行步骤3。
- 此步骤为insert_not_full()子过程。如果当前结点为叶结点，则直接将关键字插入，否则，找到该结点对应的分支i，如果self.children[i]的关键字为2t-1，则将x的第i个结点进行分裂，并递归执行步骤3。
insert_not_full()过程始终保持着一个循环不变式：当前结点关键字为非满。因为我们每次在进入insert_not_full()过程前，都先执行其分裂过程。因此我们将分裂过程定义为对x的第i个孩子进行分裂。这也就使得当根结点关键字满时，需要新增空结点为根结点，再执行分裂过程。对x的第i个孩子进行分裂，需要将x.children[i]的最后一个关键字提至x中，这也是为什么要对路径上的每个结点进行分裂的原因。插入操作的时间复杂度也为O(tlogn)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50def insert(self, k):
if self.root:
if len(self.root.keys) == 2 * self.t - 1:
r = self.root
self.root = Node()
self.root.children.append(r)
r.parent = self.root
self.split_node(self.root, 0)
self.insert_not_full(self.root, k)
else:
self.insert_not_full(self.root, k)
else:
self.root = Node()
self.root.keys.append(k)
def split_node(self, x, i):
z = Node()
y = x.children[i]
for _ in range(0, self.t - 1):
z.keys.append(y.keys[self.t])
y.keys.pop(self.t)
if y.children:
for _ in range(0, self.t):
z.children.append(y.children[self.t])
y.children.pop(self.t)
x.keys.insert(i, y.keys[self.t - 1])
y.keys.pop(self.t - 1)
x.children.insert(i + 1, z)
z.parent = x
def insert_not_full(self, x, k):
if not x.children: # 为叶结点
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
x.keys.insert(i, k)
else:
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
if len(x.children[i].keys) == 2 * self.t - 1:
self.split_node(x, i)
if k > x.keys[i]:
i = i + 1
self.insert_not_full(x.children[i], k)
删除
删除操作可能会导致B树某一结点的关键字小于t-1，与删除操作类似，我们要保持从根结点到要删除的关键字的结点的路径上的结点关键字至少大于t-1。其基本思路如下：
- 情况1：如果此结点为叶结点，则删除关键字k
情况2：如果此结点为内部结点x，若k在x的关键字中，i为其下标，即$x.keys[i] == k$，则有以下情况：
- 2a) 设y为x.children[i]，即前于k的子结点。则在以y为根的子树中找到k的前驱$k^{‘}$，即最大值，然后用$k^{‘}$替换k，然后在x.children[i]中递归地删除$k^{‘}$。
- 2b) 设z为x.children[i + 1], (k存在，则i+1必存在)，即后于k的子结点。则在以z为根的子树中找到k的后继$k^{‘}$，即最小值。然后用$k^{‘}$替换k，然后递归地删除$k^{‘}$。
- 2c) 如果y和z均只有一个关键字，则将y和z合并，并将k值下移到合并的结点的关键字中。这样，新合并的结点就有2t-1个结点，从次结点中递归的删除k。
情况3：如果此结点不在当前内部结点x中，则保证包含k值的子树的根y=x.children[i]至少包含t个关键字，如果不满足，则有以下情况：
- 3a) 如果其相邻的兄弟都至少包含t个关键字，我们记 z为y左右兄弟中关键字最多的结点， index为其下标。将z中的一个关键字升至x中，将x.key[i]降至y中，使得y包含至少包含t个关键字。
- 3b) 如果相邻的兄弟关键字均少于t，即均为t-1。则将y与其相邻的一个兄弟结点合并，x.keys[i]降至合并的结点，从此结点递归的删除k。
1 | def delete(self, k): |
Reference
本文主要参考《算法导论》。