1. B树
1.1 定义
B树是一种多路平衡查找树，具有以下性质：
-
每个节点最多包含 m 个子节点（m 阶 B树）。
-
根节点至少有两个子节点（除非它是叶子节点）。
-
每个内部节点（非根和非叶子节点）至少有 ⌈m/2⌉ 个子节点。
-
所有叶子节点位于同一层。
-
每个节点包含多个关键字，且关键字按升序排列。
1.2 操作
查找
-
从根节点开始，逐层比较关键字，找到目标值或确定目标值不存在。
插入
-
找到插入位置。
-
如果节点未满，直接插入。
-
如果节点已满，进行节点分裂：
-
将中间关键字提升到父节点。
-
分裂后的两个节点分别包含较小和较大的关键字。
-
删除
-
找到目标关键字。
-
如果关键字在叶子节点，直接删除。
-
如果关键字在内部节点，用后继关键字替换，然后删除后继关键字。
-
如果删除后节点关键字数少于 ⌈m/2⌉−1，需要进行合并或借用操作。
1.3 代码示例（伪代码）
class BTreeNode:def __init__(self, leaf=False):self.leaf = leafself.keys = []self.children = []class BTree:def __init__(self, t):self.root = BTreeNode(True)self.t = t # 最小度数def search(self, k, x=None):if x is not None:i = 0while i < len(x.keys) and k > x.keys[i]:i += 1if i < len(x.keys) and k == x.keys[i]:return (x, i)elif x.leaf:return Noneelse:return self.search(k, x.children[i])else:return self.search(k, self.root)def insert(self, k):root = self.rootif len(root.keys) == (2 * self.t) - 1:temp = BTreeNode()self.root = temptemp.children.insert(0, root)self.split_child(temp, 0)self.insert_non_full(temp, k)else:self.insert_non_full(root, k)def insert_non_full(self, x, k):i = len(x.keys) - 1if x.leaf:x.keys.append(None)while i >= 0 and k < x.keys[i]:x.keys[i + 1] = x.keys[i]i -= 1x.keys[i + 1] = kelse:while i >= 0 and k < x.keys[i]:i -= 1i += 1if len(x.children[i].keys) == (2 * self.t) - 1:self.split_child(x, i)if k > x.keys[i]:i += 1self.insert_non_full(x.children[i], k)def split_child(self, x, i):t = self.ty = x.children[i]z = BTreeNode(y.leaf)x.children.insert(i + 1, z)x.keys.insert(i, y.keys[t - 1])z.keys = y.keys[t: (2 * t) - 1]y.keys = y.keys[0: t - 1]if not y.leaf:z.children = y.children[t: 2 * t]y.children = y.children[0: t - 1]2. B+树
2.1 定义
B+树是 B树的一种变体，具有以下性质：
-
内部节点只存储关键字，不存储数据。
-
所有数据都存储在叶子节点中。
-
叶子节点通过指针连接，形成一个有序链表。
2.2 操作
查找
-
从根节点开始，逐层比较关键字，直到找到目标叶子节点。
插入
-
找到插入位置。
-
如果叶子节点未满，直接插入。
-
如果叶子节点已满，进行节点分裂：
-
将中间关键字提升到父节点。
-
分裂后的两个叶子节点分别包含较小和较大的关键字。
-
删除
-
找到目标关键字。
-
从叶子节点中删除关键字。
-
如果删除后节点关键字数少于 ⌈m/2⌉，需要进行合并或借用操作。
2.3 代码示例（伪代码）
class BPlusTreeNode:def __init__(self, leaf=False):self.leaf = leafself.keys = []self.children = []self.next = None # 指向下一个叶子节点class BPlusTree:def __init__(self, t):self.root = BPlusTreeNode(True)self.t = t # 最小度数def search(self, k, x=None):if x is not None:i = 0while i < len(x.keys) and k > x.keys[i]:i += 1if x.leaf:if i < len(x.keys) and k == x.keys[i]:return xelse:return Noneelse:return self.search(k, x.children[i])else:return self.search(k, self.root)def insert(self, k):root = self.rootif len(root.keys) == (2 * self.t) - 1:temp = BPlusTreeNode()self.root = temptemp.children.insert(0, root)self.split_child(temp, 0)self.insert_non_full(temp, k)else:self.insert_non_full(root, k)def insert_non_full(self, x, k):i = len(x.keys) - 1if x.leaf:x.keys.append(None)while i >= 0 and k < x.keys[i]:x.keys[i + 1] = x.keys[i]i -= 1x.keys[i + 1] = kelse:while i >= 0 and k < x.keys[i]:i -= 1i += 1if len(x.children[i].keys) == (2 * self.t) - 1:self.split_child(x, i)if k > x.keys[i]:i += 1self.insert_non_full(x.children[i], k)def split_child(self, x, i):t = self.ty = x.children[i]z = BPlusTreeNode(y.leaf)x.children.insert(i + 1, z)x.keys.insert(i, y.keys[t - 1])z.keys = y.keys[t: (2 * t) - 1]y.keys = y.keys[0: t - 1]if not y.leaf:z.children = y.children[t: 2 * t]y.children = y.children[0: t - 1]else:z.next = y.nexty.next = z3. B树与 B+树的比较
| 特性 | B树 | B+树 |
|---|---|---|
| 数据存储 | 内部节点和叶子节点都存储数据 | 只有叶子节点存储数据 |
| 叶子节点连接 | 无 | 通过指针连接成有序链表 |
| 查找性能 | 适用于随机查找 | 适用于范围查找 |
| 磁盘 I/O | 较高 | 较低 |
