《面试官:谈谈你对索引的认知》系列之B+树

原创
06/01 08:30
阅读数 723

写在前面

前面一讲我们介绍了B-树的特性,以及与平衡二叉树的对比得出B-树这类数据结构的优势。

《面试官:谈谈你对索引的认知》系列之B-树

那B+树作为B树的一个升级版,那它又有哪些优势呢?本讲继续为大家揭开B+树的神秘面纱,让它不再成为你前进的羁绊!

B+树 简介

B+树是B-树的一个升级版,也是一种多路搜索树,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。

从上图B-树的简化图,我们可以发现几个显著特点:

  • 据只出现在叶子节点(非叶子节点并不存储真正的 data)

  • 所有叶子节点增加了一个链指针

B+树 VS B-树

1、数据实现结构不同,查询复杂度不同

B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

如我们分别查询B-树/B+树节点 key 为 50 的 data。

  • B-树

key 为 50 的节点恰好就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

  • B+树

由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。

小结:

B树的由于每个节点都有key和data,所以查询的时候可能不需要O(logn)的复杂度,甚至最好的情况是O(1)就可以找到数据,而B+树由于只有叶子节点保存了data,所以必须经历O(logn)复杂度才能找到数据。

2、B+树可以更好的利用局部性原理

B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

小结:

由于B+树的叶子节点的数据都是使用链表连接起来的,而且他们在磁盘里是顺序存储的,所以当读到某个值的时候,磁盘预读原理就会提前把这些数据都读进内存,使得范围查询和排序都很快。

3、B+树每个节点能索引的范围更大更精确

因为它内节点不存储data,这样一个节点就可以存储更多的key。

由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。

小结:

由于B树的节点都存了key和data,而B+树只有叶子节点存data,非叶子节点都只是索引值,没有实际的数据,这就时B+树在一次IO里面,能读出的索引值更多。从而减少查询时候需要的IO次数!

总结

B-树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。

但是B+树的优势更加明显:

  • B+树的层级更少

相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;

  • B+树查询速度更稳定

B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;

  • B+树天然具备排序功能

B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。

  • B+树全节点遍历更快

B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

 

·················· END ··················

关注公众号,免费领取程序员成长大礼包

十年研发路,大厂架构师,CSDN博客专家

专注架构技术学习及分享,职业与认知升级

坚持分享接地气儿的干货,期待与你一起成长

 

推荐阅读

消息中间件

架构应用汇总

认知升级迭代

MySQL实用探秘

 


 

「架构精进之路」专注架构研究,技术分享

 

点“赞”和“在看”哦

本文分享自微信公众号 - 架构精进之路(jiagou_jingjin)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
1 收藏
分享
加载中
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部