• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

什么是B+Tree

技术杂谈 勤劳的小蚂蚁 3个月前 (01-13) 95次浏览 已收录 0个评论 扫描二维码


B+Tree的定义
B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征:
  1. 有m个子树的节点包含有m个元素(B-Tree中是m-1)
  2. 根节点和分支节点中不保存数据,只用于索引,所有数据都保存在叶子节点中。
  3. 所有分支节点和根节点都同时存在于子节点中,在子节点元素中是最大或者最小的元素。
  4. 叶子节点会包含所有的关键字,以及指向数据记录的指针,并且叶子节点本身是根据关键字的大小从小到大顺序链接。
更直观的图
1、红点表示是指向卫星数据的指针,指针指向的是存放实际数据的磁盘页,卫星数据就是数据库中一条数据记录。
2、叶子节点中还有一个指向下一个叶子节点的next指针,所以叶子节点形成了一个有序的链表,方便遍历B+树。
B+树的优势1、更加高效的单元素查找

B+树的查找元素3的过程:
第一次磁盘IO
第二次磁盘IO
第三次磁盘IO
这个过程看下来,貌似与B树的查询过程没有什么区别。但实际上有两点不一样:
a、首先B+树的中间节点不存储卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素,如此一来,相同数量的数据下,B+树就相对来说要更加矮胖些,磁盘IO的次数更少。
b、由于只有叶子节点才保存卫星数据,B+树每次查询都要到叶子节点;而B树每次查询则不一样,最好的情况是根节点,最坏的情况是叶子节点,没有B+树稳定。

2、叶子节点形成有顺链表,范围查找性能更优
B树范围查找3-8的过程
a、先查找3
b、再查找4、5、6、7、8,中间过程省略,直接到8的查找
这里查找的范围跨度越大,则磁盘IO的次数越多,性能越差。

B+树范围查找3-11的过程
先从上到下找到下限元素3,然后通过链表指针,依次遍历得到元素5/6/8/9/11;如此一来,就不用像B树那样一个个元素进行查找。
 
总结
  1. 单节点可以存储更多的元素,使得查询磁盘IO次数更少。
  2. 所有查询都要查找到叶子节点,查询性能稳定。
  3. 所有叶子节点形成有序链表,便于范围查询。
PS:在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。

    丨极客文库, 版权所有丨如未注明 , 均为原创丨
    本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
    转载请注明原文链接:什么是B+Tree
    喜欢 (0)
    [247507792@qq.com]
    分享 (0)
    勤劳的小蚂蚁
    关于作者:
    温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

    您必须 登录 才能发表评论!

    • 精品技术教程
    • 编程资源分享
    • 问答交流社区
    • 极客文库知识库

    客服QQ


    QQ:2248886839


    工作时间:09:00-23:00