B-树的定义

B-树是为磁盘或其他直接存取的辅助存储设备而设计的一种多路平衡查找树。

一棵阶的B-树，或为空树，或为满足下列特性的叉树：

• 树中每个结点至多有棵子树。
• 若根结点不是叶子结点，则它至少有两棵子树。
• 除根结点外，所有的非终端结点至少为棵子树。
• 所有的非终端结点中包含下列信息数据，其中为关键字的个数，为个递增的关键字，为个子树的根结点指针。对任意，所指的子树中所有结点的关键字均大于且小于。（所指子树中所有结点的关键字均小于，所指子树中所有结点的关键字均大于）
• 所有叶子节点均在同一层，并且不携带信息。

阶代表一个树节点最多有多少个查找路径。

4阶的B-树的实例如下所示