位卑未敢忘忧国，事定犹须待阖棺。

# B 树

B 树 (B-tree) 是一种自平衡树，于 1970 年被提出 (论文地址，一个排版较好的版本)。

# 定义和基本性质

关于 B 树的术语在文献中没能实现很好的统一。例如对 B 树阶 (order) 的定义不明确。下面，我们选取两种基本的定义方式，以了解 B 树的设计思想。

# Knuth 的定义

Knuth 关于 B 树的定义如下：

$m$ 阶 B 树是满足如下特性的树：
每个节点最多有 $m$ 个子节点。
每一个非叶子节点（除根节点）最少有 $\lceil \dfrac{m}{2} \rceil$ 个子节点。
非叶子节点至少有 $2$ 个子节点。
有 $k$ 个子节点的非叶子节点拥有 $k-1$ 个键。
所有的叶子节点都在同一层。

# 《算法导论》中的定义

在《算法导论》中也有对 B 树的定义。其定义如下：

一个 B 树 $T$ 是一个根为 T.root 的有根树 (rooted tree). 其有如下性质：
每一个节点 $x$ 满足如下性质：
$x.n$ 是节点 $x$ 当前存储的键 (key) 数目。
$x$ 的 $x.n$ 个键 $x.key_1, x.key_2, \dots, x.key_{x.n}$ 按单调递增顺序存储，即 $x.key_1\leq x.key_2 \leq \dots \leq x.key_{x.n}$ .
$x.leaf$ 是一个布尔值，表明 $x$ 是否是一个叶子节点。
对于每一个内部节点 (internal node, 即非叶子节点), 其拥有 $x.n+1$ 个孩子 $x.c_1, x.c_2, \dots, x.c_{x.n+1}$ .
叶子节点没有孩子，其 $c$ 域未定义
键 $x.key_i$ 将子树中存储的众多键进行了划分。即若 $k_i$ 是存储在根为 $x.c_i$ 子树中的任一节点，那么
$k_1 \leq x.key_1 \leq k_2 \leq \cdots \leq x.key_{x.n} \leq k_{x.n+1}$
所有的叶子节点有相同的深度，均为树高度 $h$ .
节点容纳的键数量存在上界和下界，这通过 B 树的最小度 (minimum degree) $t$ 定义：
每一个非根节点含有至少 $t-1$ 个键。每一个内部节点含有至少 $t$ 个孩子。如果该树非空，那么根节点至少拥有一个键。
每一个节点含有至多 $2t-1$ 个键。因此，每一个内部节点含有至多 $2t$ 个孩子。如果一个节点含有 $2t-1$ 个键，那么称这个节点是满 (full) 的。

最简单的 B 树的最小度 $t=2$ . 这样，每个内部节点的孩子数目为 $2, 3$ 或 $4$ . 因此称其为一个 2-3-4 树。在实际应用中， $t$ 值往往很大。

# 基本操作

# 查找

B-Tree_Search

	BTreeNode *BTreeNode::search(int k) {
	// 找到第一个大于等于待查找键 k 的键
	int i = 0;
	while (i < n && k > keys[i]) i++;

	// 如果找到的第一个键等于 k , 返回节点指针
	if (keys[i] == k) return this;

	// 如果没有找到键 k 且当前节点为叶子节点则返回 NULL
	if (leaf == true) return NULL;

	// 递归
	return C[i]->search(k);
	}

# 遍历

B-Tree_

	void BTreeNode::traverse() {
	// 有 n 个键和 n+1 个孩子
	// 遍历 n 个键和前 n 个孩子
	int i;
	for (i = 0; i < n; i++) {
	// 如果当前节点不是叶子节点，在打印 key [i] 之前，
	// 先遍历以 C [i] 为根的子树.
	if (leaf == false) C[i]->traverse();
	cout << " " << keys[i];
	}

	// 打印以最后一个孩子为根的子树
	if (leaf == false) C[i]->traverse();
	}

# B+ 树

B+ 树 (B $^+$ -tree)

# Reference

Wikipedia: B-tree
OI-wiki: B 树