什么是B+Tree

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)中,叶子节点带有指向卫星数据的指针。

参考文献:

【1】很直观的图:http://www.jianshu.com/p/6f68d3c118d6

【2】《算法导论》

原文发布于微信公众号 - 高性能服务器开发(easyserverdev)

原文发表时间:2018-04-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android相关

基于红黑树的TreeMap使用

最近在项目中做异步任务调度服务的时候,用到红黑树来实现异步任务的管理,挑选出最符合条件的任务执行,于是使用到了TreeMap来管理

27360
来自专栏ACM算法日常

POJ-3641:Pseudoprime numbers(快速幂)

Fermat's theorem states that for any prime number p and for any integer a > 1, a...

11710
来自专栏java 成神之路

ConcurrentHashMap 原理解析(JDK1.8)

34670
来自专栏一枝花算不算浪漫

Java中常见数据结构Set之HashSet

32860
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

47670
来自专栏数据结构与算法

P3369 【模板】普通平衡树(Treap/SBT)(pb_ds版)

题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询...

28070
来自专栏xcywt

《大话数据结构》 查找 以及一个简单的哈希表例子

第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):...

954120
来自专栏数据结构与算法

洛谷P3384 【模板】树链剖分

题目描述 如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路...

32450
来自专栏mySoul

java队列

队列为特殊的线性表,队列的特点先进先出(FIFO),队列插入为入队,队列删除为出对。

28900
来自专栏趣学算法

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出:数据结构+算法=程序。数据结构是程序的骨架,算法则是程序的灵魂。

10530

扫码关注云+社区

领取腾讯云代金券