B树与B+树

B树与B+树为了存储设备或者磁盘而设计的一种平衡查找树。

B树#

定义：一棵m阶树的B树,满足：

• 所有节点最多有m棵子树
• 根节点至少有2棵子树
• 除了根节点，其他节点最少有m/2棵子树
• 所有叶子节点都是在同一层
• 所有节点都包含形式的数据：
  (n,A0 ,K1 ,A1 ,K2 ,A2 , … ,Kn,An )， n表示这个节点关键字的数量，K是关键字，A是指针。可知每节点的子树比关键字数量大一。

下面是一个4阶B树

B+树#

B+树是B树的一个变种。m阶 B+树与m阶B树的差异在于：

• 节点如果有n个子树，那么就要n个关键字。即节点的关键字数量== 节点的子树数量。B树子树数量==关键字数量+1
• 叶子节点包含所有的信息，并且叶子节点会根据关键字大小组成链

B+树示意图