定义

M阶B+树的定义：

  • 任意非叶子节点最多有M个子节点；且M>2；
  • 除根节点以外的非叶子节点至少有 M/2个子节点；
  • 根节点至少有2个子节点；
  • 除根节点外每个节点存放至少M/2和至多M个关键字；（至少2个关键字）
  • 非叶子节点的子树指针与关键字个数相同；
  • 所有节点的关键字：K[1], K[2], …, K[M]；且K[i] < K[i+1]；
  • 非叶子节点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树；
  • 所有叶子节点位于同一层；
  • 为所有叶子节点增加一个链指针；
  • 所有关键字都在叶子节点出现；

B+树是对B树的一种变形树，它与B树的差异在于：
有k个子节点的节点必然有k个关键字
非叶节点仅具有索引作用，跟记录有关的信息均存放在叶节点中。
树的所有叶节点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

image.png