1970年，Rudolf Bayer 和 E.Mccreight 提出了 B 树。
B 树
B 树是一种自平衡的多路查找树，名副其实的树状数据结构，基本的查找流程与二叉平衡树很相似（仍属于查找树），它与平衡二叉树明显在于，它的节点可以拥有多个关键字，可以最优化大块数据的读写操作，在文件系统和数据库中很实用。
B 树的标准英文名 B-Tree，“-”是专有名词的连字符，而多数国内书籍僵硬的翻译为 B-树，又因为还有 B+ Tree, 容易让人误以为是 “B减树”，从而导致信息混乱，以为有三种 B 树，因此根本没有“B减树”之说。从标准做起，只说或写作 B 树，不要中间的连字符，防止误解。
一棵 \(m\) 阶的 B 树，或为空树，或为满足下列特性的 \(m\) 叉树（阶数 m 是是指每个节点最多拥有的子树数量）：
(1) 树中每个节点至多有 \(m\) 棵子树（至多有 \(m-1\) 个关键字）；
(2) 若根节点不是叶子节点，则至多有两棵子树；
(3) 除根之外的所有非终端节点至少有 \(⌈\frac{m}{2}⌉\) 棵子树（除根外至少 \(⌈\frac{m}{2}⌉-1\) 个关键字）；
(4) 所有非终端节点中包含如下信息数据
$$(n,A_0,K_1,A_1,K_2,…,K_n,A_n)$$
其中，\(K_i (i = 1,…n)\) 是关键字，且 \(K_i < K_i+1(i = 1,…,n-1)\)；\(A_i (i = 0,1,…n)\) 是指向子树的指针，且指针 \(A_{i-1}\) 所指子树中的所有节点的关键字均小于 \(K_i\)，\(A_i\) 所指子树中的所有节点的关键字均大于 \(K_i\)；\(n\) 是关键字的个数，\(n\) 的取值范围为 \(⌈\frac{m}{2}⌉-1 ≤ n ≤ m-1\)。
容易看到，所有节点中任一关键字 \(K_i\) 和子树指针 \(A_i\) 是对应的；每个节点的子树（指针）数量等于比关键字数量 +1，即每个子树中有 \(n+1\) 棵子树；同理整个 B 树中叶子节点（空指针）的数量等于 B 树关键字数量 +1，即 B 树共中有 \(n+1\) 个叶子（不存信息，不算入高度）。
实际应用中 B 树每个节点中还应包含 n 个指向每个关键字的具体文件数据记录的指针，B 树只是关键字索引，本身不存放数据信息。例如，内存管理中页块置换操作，构造的B 树中不会直接存储页数据，而是保存关联页块副本的链接。
(5) 所有叶子节点都出现在 同一层次（最底） 上（自平衡），并且不带信息（可以看作外部节点或查找失败的节点，实际上这些节点并不存在，指向这些节点的指针为空）。
B 树相当于 m 叉平衡树进一步加强限制 —— 节点平衡因子均为 0，所有叶子节点均在最下面一层。
忽略具体应用中的复杂链接，B 树节点的定义可进行如下描述：
// 一般 3 阶起步，即 2-3 树
#define m 3
// B 树 Node
typedef struct BTNode {
int keynum; // 关键字数量（节点大小）
struct BTNode *parent; // 双亲指针，插入和删除中的拆分合并操作会用到
KeyType key[m+1]; // 关键字向量，0 号空闲
struct *ptr[m+1]; // 子树指针向量（指针数组）
// Record *recptr[m+1]; // 关键字关联的记录指针
}BTNode, *BTree;B 树的查找
B 树上的查找与排序树相似，只不过 B 树种每个节点都是多关键字组成的有序表，往下的走向也不止 2 路，即多路查找，具体走向与关键字相关。
具体地，设待查关键字为 k：
(1) k 与根结点中的关键字比较，若存在 key[i] == k，则查找成功；
(2) 否则，若存在 key[i]、key[i+1]，使 key[i] < k < key[i+1]，则进入 ptr[i] 所指子树继续查找；
(3) 当遇到空指针时，即到达叶子节点，则查找失败（后续可进行新关键字插入）。
实践中，在 B 树查找关键字有两个基本操作：(1)是在树中顺着指针找节点；(2)是在节点内有序表找关键字，B 树的查找过程就是这两个基本操作交叉进行的过程。
一般系统中构造的 B 树存放在磁盘上，因此先在磁盘中寻找节点，将节点信息读入内存，然后利用顺序查找或折半查找得到相关的关键字，要么当前关键字就是待找关键字，要么根据该关键字继续找子树节点，最终找到关键字或查找失败。
显然，在磁盘中进行一次查找要比在内存中查找更耗费时间，因此在磁盘上查找的次数（待查关键字在 B 树上的深度）是决定 B 树查找效率的首要因素。
Result SerachBTree(BTree T, KeyType k)
{
// f 指向双亲，用于查找失败时新关键字的插入位置
BTNode *p = T, *f = NULL;
int i = 0, found = 0;
while(p && found == 0)
{
i = Search(p->key, k);
if (i > 0 && p->key[i] == k)
found = 1; // 找到
else
{ f = p; p = p->ptr[i]; }
}
if (found) return (p, i, 1);
else return (f, i, 0);
// 查找失败，返回插入位置
}B 树的高度
对任意一棵包含 \(n(n≥1)\) 个关键字、高度为 h、阶数为 m 的 B 树：（h 不包括最下层叶子）
(1) 当每个节点的关键字数量为最大值 \({m-1}\) 时（子树的数量为最大值 \(m\)），高度 \(h\) 与关键字数量 \(n\) 之间关系为：
$$n ≤ (m-1)(1 + m + m^2 +…+ m^{h-1}) = m^h-1$$
$$h ≥ log_m (n+1)$$
结论：(Ⅰ) 含 n 个节点的 B 树，其高度至少为 \(log_m (n+1)\)；
(Ⅱ) 高度为 h 的 B 树，其关键字至多为 \((m^h-1)\)。
(2) 当每个非终端节点的关键字数量为最小值 \(⌈\frac{m}{2}⌉-1\) 时（子树的数量为最大值 \(⌈\frac{m}{2}⌉\)），根节点 1 个关键字，根据 B 树的定义可得：第 1 层有 1 个节点，第 2 层有 2 个节点，第 3 层有 \(2⌈\frac{m}{2}⌉\) 个节点，第 4 层有 \(2(⌈\frac{m}{2}⌉)^2\) 个节点，…… 第 h+1 层有 \(2(⌈\frac{m}{2}⌉)^{h-1}\) 个节点，其中第 h+1 层是不含信息的叶子节点。对于含有 n 个关键字的 B 树，叶子节点数量即查找不成功的节点有 \(n+1\) 个。于是，高度 h 与关键字数量 n 之间关系为：
$$n+1 ≥ 2(⌈\frac{m}{2}⌉)^{h-1}$$
$$h ≤ log_{⌈\frac{m}{2}⌉} (\frac{n+1}{2}) + 1$$
结论：
(Ⅰ) 含 n 个节点的 B 树，其高度 h 取值范围为
$$log_m (n+1) ≤ h ≤ log_{⌈\frac{m}{2}⌉} (\frac{n+1}{2}) + 1$$
(Ⅱ) 高度为 h 的 B 树，其关键字数量 n 取值范围为
$$2(⌈\frac{m}{2}⌉)^{h-1}-1 ≤ n ≤ m^h-1$$
B 树的插入
B 树的生成同样从空树开始，逐个插入关键字得到。但是 B 树节点中的关键字个数必须 \(≥⌈\frac{m}{2}⌉-1\)，所以每次插入关键字时不是在树中添加一个叶子节点，而是首先在最底层的某个非终端节点中添加一个关键字，如果该节点的关键字数量没有超过 \(m-1\)，则插入完成，否则要“分裂节点”。
B 树中的新节点不是直接插入得到的，而是节点中的关键字数量超标分裂得到的，树增高发生在根节点。
分裂节点的具体场景是：
假设节点 p 中已经有 \(m-1\) 个关键字，当心插入一个节点后，该节点中的信息为
$$m,A_0,(K_1,A_1),…(K_m,A_m) \ \ 其中\ K_i < K_{i+1}，1≤i<m $$
先将 p 从中间分裂成两个节点 p 和 p*，其中 p 信息为
$$⌈m/2⌉-1,A_0,(K_1,A_1),…,(K_{⌈m/2⌉-1},A_{⌈m/2⌉-1})$$
p* 信息为
$$m-⌈m/2⌉,A_{⌈m/2⌉},(K_{⌈m/2⌉+1},A_{⌈m/2⌉+1}),…,(K_{m},A_{m})$$
而关键字 \(K_{⌈m/2⌉}\) 和指针 p* 作为一对依赖插入到双亲节点合适的位置中。
B 树的删除
关键字数量小于 \(⌈\frac{m}{2}⌉-1\)，合并
未完待续