一、B 树是一种多叉平衡查找树
- 提出多叉平衡查找树的思维历程：查询效率要更高 ----> 查询次数要更少 ----> 查找树的高度要更低 ----> 每个结点保存的信息要更多 ----> 多叉
下图是一棵B树的示意图：
二、B 树的定义
《算法导论》中用最小度数 t 来定义 B 树，所谓最小度数，即结点拥有的最小孩子数。
一棵最小度数为 t 的 B 树是满足如下四个条件：
- 每个非根结点至少含有 t - 1 个关键字，根结点至少含有 1 个关键字
- 每个结点至多含有 2t - 1 个关键字，即一个结点至多可有 2t 个孩子（如果一个结点恰好有 2t - 1 个关键字，我们就说这个结点是满的）
- 一个结点 u 中的关键字按非降序排列，如u.key≤ u.key≤ … ≤ u.key
- 每个节点的关键字对其子树的范围分割，设节点 u 有 n + 1 个指针，指向其 n + 1 棵子树，指针为u.p, u.p, u.p, …, u.p，关键字 k 为 u.p 所指的子树中的关键字，有 k≤ u.key≤ k≤ u.key…≤ u.key≤ k 成立
- 所有叶子结点具有相同的深度，即树的高度 h（这表明了 B 树是平衡的）
/* B树结点结构 */
struct BTreeNode {
int keyNum; // 关键字的数目
BTreeNode *parent; // 指向父结点
BTreeNode **ptr; // 子树指针向量：ptr[0]...ptr[keyNum]
KeyType *key; // 关键字向量；key[0]...key[keyNum-1]
};
三、查询操作
例题：一棵已经建立好的B树如下图所示，要求查找关键字为29的文件。
- 结点中的关键字表示磁盘文件的文件名，而小红块表示对应的关键字所代表的文件在硬盘中的存储位置，P是指针
指针、关键字以及关键字所代表的文件地址合起来构成了B树的一个结点，这个结点存储在一个磁盘块上
- 假如每个磁盘块正好可以存放一个B树的结点（正好存放2个文件名）。那么一个B树结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址
搜索过程如下：
从根结点开始，读取根结点信息，根结点有2个关键字：17和35。因为17 < 29 < 35，所以找到指针P2指向的子树，也就是磁盘块3（1次I/0操作）
读取当前结点信息，当前结点有2个关键字：26和30。因为26 < 29 < 30，所以找到指针P2指向的子树，也就是磁盘块8（2次I/0操作）
读取当前结点信息，当前结点有2个关键字：28和29。找到了！（3次I/0操作）
由上面的过程可见，同样的操作，如果使用平衡二叉树，那么需要至少4次 I/O 操作，而且这种优势还会随着结点数的增加而更加明显。另外，因为 B 树结点中的关键字都是排好序的，所以，在结点中的信息被读入内存之后，可以采用二分查找这种快速的查找方式，更进一步减少了读入内存之后的计算时间。由此可见，对于外存数据结构来说，I/O操作的次数是其查找信息中最大的时间消耗，而我们要做的所有努力就是尽量在搜索过程中减少I/O操作的次数。
四、插入/删除操作