数据结构是 B 树、B+ 树及 B* 树

本系列博客来源于网络，在此基础上增添了一些个人见解。阅读该系列博客时会有一种似曾相识的感觉。本文旨在供本人今后学习和复习使用，并会在前面或后面列出参考文章的链接。

一、B树

B 树又叫平衡多路查找树。一棵m阶的B 树的特性如下：

在树中每个节点最多容纳m个子节点（其中m \geq 2），空树除外。（注：此处定义了一个关于查找路径的术语：若一个节点有k条搜索路径，则称该节点为k阶；特别地，在二叉树中k=1时称为1阶，在三叉树中k=1时称为1阶）

（2）除了根节点和叶节点之外，其余每个节点至少拥有⌈m/2⌉个子节点；

（3）所有叶子节点均位于同一层次、这些叶节点除了存储关键字信息之外。（参考知乎的相关文章以及July的大作《数据结构与算法》）。值得注意的是，在红黑树结构中，默认情况下最后一层可能无需显式创建叶子节点（其中红色节点通常被用作标记非终端节点）。此外，在附录中我已经附上了相关图表（图1展示了这一概念的具体实现），如果您对相关内容仍有疑问，请访问上述链接中的详细讨论）。

若一个树的根节点并非叶子节点，则该树最少有两个子节点；特别地，在没有子节点的情况下（即该树仅由一个单独的根节点构成），这种情况属于该树为单节点的情形。

（5）每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)