1 定义

B+树是B-树的一个变种。 B+树对B-树做了改进,使得数据存储操作更为便捷。B+ 树通常用于数据库, 操作系统中的文件系统。

一个M阶的B+树有以下性质:

  • 每个非叶子节点最多只有M个子节点
  • 除根节点外,每个非叶子节点有M/2到M个子节点,根节点至少有两个字节点
  • 有k个子节点必须有k个关键字key。
  • 叶子节点的数据都是有序的,并且通过链表相连。

2 实现