tyltr技术窝

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+树示意图