数据结构-多路平衡查找树:B+树

特点

一颗m阶的B+树和m阶的B树的异同点:

  • 所有的叶节点包含了全部的关键字信息key和data,及指向含有这些关键字记录的指针,通过指针将叶节点连接到了一起,且叶子结点本身依关键字的大小自小而大的顺序链接(B树的叶子节点并没有包括全部需要查找的信息);
  • 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字key。(而B 树的非终节点也包含需要查找的有效信息data)。
  • 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针,而且叶子结点按关键字的大小从小到大顺序链接;

特点

  • 根节点的最小值也是整颗B+树的最小元素。不论插入删除多少元素,始终要保持最小的元素在根节点中。

  • 叶子节点包含了所有元素的信息。并且除最右叶子节点,每一个叶子节点都带有下一个节点的指针,形成了有序链表。如 5->8->9->10->15->18…..

优点

主要体现在查询性能上。

  • 单行查询
    在单行查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点。与B树不同的是,B+树内节点没有关键字,所以同样大小的磁盘页可以容纳更多的节点元素,也就意味着,数据量相同的情况下,B+树的结构比B树更加”矮胖”,IO次数更少。另外一点,B+树的查询必须最终查找到叶子节点,而B树只要找到匹配元素即可,因此,B树的查找性能不稳定,而B+树的每一次查找都是稳定的。

  • 范围查询
    对于范围查找,B树只能依靠中序遍历;而对于B+树的范围查找,只需要遍历叶子节点,即在链表上做遍历即可。

总得来说,B+树比B树的优势有3个:1.IO次数更少 2.查询性能稳定 3.范围查找简单快速。

分裂

当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

总结

B+树的本质:平衡多叉树+有序数组链表。

参考

0%