B树,B+树比较

首先注意:B树就是B-树,"-"是个连字符号,不是减号。也就是B-树其实就是B树

B-树是一种平衡的多路查找(又称排序)树,在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance) 

B+树是对B树的一种升级, B树每个节点都存储data, 而B+树只在叶子节点存储data,B+降低了树的深度,将“瘦高”的树变得“矮胖:

实现方法: 

(1)、每个节点存储多个元素 
(2)、摒弃二叉树结构,采用多叉树

B树:

B+树:

B+树有更高的查找效率 

1. B+树中间节点没有卫星数据,只有索引,而B树每个结点中的每个关键字都有卫星数据;这就意味着同样的大小的磁盘页可以容纳更多节点元素,在相同的数据量下,B+树更加“矮胖”,IO操作更少 

2、其次,因为卫星数据的不同,导致查询过程也不同;B树的查找只需找到匹配元素即可,最好情况下查找到根节点,最坏情况下查找到叶子结点,所说性能很不稳定,而B+树每次必须查找到叶子结点,性能稳定
3、在范围查询方面,B+树的优势更加明显
  B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限,在不断通过中序遍历,知道查找到范围的上限即可。整个过程比较耗时。
  而B+树的范围查找则简单了许多。首先通过二分查找,找到范围下限,然后同过叶子结点的链表顺序遍历,直至找到上限即可,整个过程简单许多,效率也比较高。

小结:

B+树相比B树的优势: 
  1.单一节点存储更多的元素,使得查询的IO次数更少; 
  2.所有查询都要查找到叶子节点,查询性能稳定; 
  3.所有叶子节点形成有序链表,便于范围查询。

原文地址:https://www.cnblogs.com/snow-man/p/10064035.html