B树和B+树

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 = leaf self.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 = 0 while i < len(x.keys) and k > x.keys[i]: i += 1 if i < len(x.keys) and k == x.keys[i]: return (x, i) elif x.leaf: return None else: return self.search(k, x.children[i]) else: return self.search(k, self.root) def insert(self, k): root = self.root if len(root.keys) == (2 * self.t) - 1: temp = BTreeNode() self.root = temp temp.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) - 1 if x.leaf: x.keys.append(None) while i >= 0 and k < x.keys[i]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i >= 0 and k < x.keys[i]: i -= 1 i += 1 if len(x.children[i].keys) == (2 * self.t) - 1: self.split_child(x, i) if k > x.keys[i]: i += 1 self.insert_non_full(x.children[i], k) def split_child(self, x, i): t = self.t y = 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 = leaf self.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 = 0 while i < len(x.keys) and k > x.keys[i]: i += 1 if x.leaf: if i < len(x.keys) and k == x.keys[i]: return x else: return None else: return self.search(k, x.children[i]) else: return self.search(k, self.root) def insert(self, k): root = self.root if len(root.keys) == (2 * self.t) - 1: temp = BPlusTreeNode() self.root = temp temp.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) - 1 if x.leaf: x.keys.append(None) while i >= 0 and k < x.keys[i]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i >= 0 and k < x.keys[i]: i -= 1 i += 1 if len(x.children[i].keys) == (2 * self.t) - 1: self.split_child(x, i) if k > x.keys[i]: i += 1 self.insert_non_full(x.children[i], k) def split_child(self, x, i): t = self.t y = 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.next y.next = z

---

3. B树与 B+树的比较 特性B树B+树数据存储内部节点和叶子节点都存储数据只有叶子节点存储数据叶子节点连接无通过指针连接成有序链表查找性能适用于随机查找适用于范围查找磁盘 I/O较高较低