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

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

一棵math阶的B+树,或为空树,或为满足下列特性的math叉树:

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

3阶B+树的示例如下:

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

Comments
登录后评论
Sign In