算法与数据结构(10): B+树

B+树与B-树很像，它常用于数据库与操作系统的文件系统中。

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

• 树中每个结点至多为棵子树。
• 则除了根之外的每个结点都包含最少棵子树。
• 所有非终端结点中包含如下信息，其中为关键字的个数，为第个关键字且递增有序，为第棵子树的根节点指针，关键字为第棵子树根节点中的最大（或最小）关键字（也不一定，有时候可能该关键字在子树中不存在，子树中的关键字可能大于（或小于）该关键字）。
• 所有叶子结点包含所有关键字，叶子结点中每个关键字指针指向改关键字对应的物理记录；全部叶子结点从左向右以单向链表的形式串联，该单链表中各结点的关键字是递增有序的。

3阶B+树的示例如下：

注：不同版本的B+树定义可能略有差异。