理解 B+ 树算法

作者:毛见峰

导语: 最近有接触到b+树,花了点时间,顺便总结梳理下方便后续翻阅;时间仓促,且文中多是个人的理解,仅供参考。

定义

参考百度百科及wiki百科定义:B +树是一个N叉排序树,每个节点通常有多个孩子,一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点,也可能是一个包含两个或两个以上孩子节点的节点。

B+ 树主要价值在于存储用于在面向块的存储环境中高效检索的数据,通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

结构类似如下:

B+树的特点剖析

  1. 只有叶子节点才记录数据,非叶子节点只包含索引;换句话说,所有叶子节点中包含了全部关键字的信息,及指向这些关键字记录的指针,所有的非终端节点(内部节点)并不存储数据信息,而是保存其叶子节点的最小值作为索引。 此点设计初衷,主要作用体现在降低磁盘IO方面。
  2. 能够提供稳定高效的范围扫描(range-query)功能;这也是为什么数据库和操作系统中的文件系统通常会采用b+树作为元数据索引的原因,这个特点主要得益于所有叶子节点相互连接,并且叶子节点本身依关键字的大小自小而大顺序链接。这种设计在扫描时可以避免的耗时的遍历树操作。所以,b+树通常可以提供两种查找方式,一,从根节点起随机查找(起点是指向根节点的root); 二,顺序查找(起点是指向最小关键字的sqt)。
  3. 所有叶子节点均出现在同一层;因为在实现上B+树元素插入采用的是自底向上分裂算法(删除元素类似同理),具体实现可参看下节图示。另外说明的一点,B+中的B并不是代表二叉(Binary),而是代表平衡(Balance)。
  4. 对于m阶B+树,m的值越大,固定高度的B+树存放的值就越多。实验数据表明当m处于50~400之间,性能最好[待验证];在wiki百科里的b+树的介绍里提到的m值也通常是100甚至更多:B+ trees have very high fanout (number of pointers to child nodes in a node,[1] typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree。
  5. 在B+树的索引中,用户可以得到页表(或者叫块)级别的位置信息;但如果要进行一次比如key1到key3的范围查询,则可能需要读取两个在磁盘上不连续甚至可能相隔很远的叶子节点页表;这种情况,通常在B+树的设计中会含有一组被称为OPTIMIZE TABLE(优化表)命令,TA的作用是把表重写,从而使表的范围查询变成磁盘的多段连续读取,提高范围查询的执行效率。

B+树插入删除操作图示

插入基本算法(参考wiki定义):

执行搜索以确定新记录应该进入哪个节点。

  • 如果节点不满,添加记录。
  • 否则,拆分节点。
    1. 分配新的叶子节点,并将一半的原节点元素移动到新的叶子节点。
    2. 将新叶子节点的最小键和地址插入父节点。
    3. 如果父节点满了,分拆。
    4. 将中间键添加到父节点。
    5. 重复一遍,直到找到不需要拆分的父节点。
  • 如果根分裂,创建一个新的根,分别取自叶子的最小键。
  • B树在根部生长,而不是在叶子上生长。

举个栗子:往下图的3阶B+树中依次插入关键字:10、21、68、65、85

首先查找10应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。插完如下图所示:

继续查找21应插入的叶节点(还是最左下角的那一个),插入,发现该叶子节点已经破坏了B+树的性质,则分解成[8 10], [15 21]两个,并把15往父节点移;

这时可以发现父节点也破坏了B+树的性质,则把之再分解成[8 15], [34 93]两个,并把8和34(由于此时是根节点)向上产生一个新根节点;

如下图:

接着查找68应插入的叶节点(第三个叶子节点),插入发现没有破坏B+树的性质,完毕。插完如下图所示:

接着查找65应插入的叶节点(第三个叶子节点),插入,发现该叶子节点已经破坏了B+树的性质,则分解成[34 65], [68 78]两个,并把68往父节点移;如下图所示:

最后查找85应插入的叶节点(第四个叶子节点),插入发现没有破坏B+树的性质,完毕。插完如下图所示:

至此完毕!

删除算法类似,但更为复杂些,插入算法节点之间只与父节点产生关系,而删除算法则需要考虑兄弟节点和父子节点的关系;在此不赘述了。

总而言之 B+树多用于文件系统索引(比如NTFS, ReiserFS, NSS, XFS等)和数据库索引(比如innodbinnodb存储引擎等)方面,其优势主要体现在(针对B树):

  1. 降低磁盘IO方面做的更好 B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存 中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。 举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B+树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候,B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转寻道的时间)。
  2. 查询效率更加稳定 由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

但是如果对写数据敏感度比较高,则更倾向于使用LSM树,LSM树能够保证更稳定的数据插入速率;后续有时间整理介绍。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏高性能服务器开发

Redis应用总结

首先, 我带大家简单的了解一下Redis Redis常用数据类型(最为常用的数据类型主要有以下五种) ●String ●Hash ●List ●Set ●Sor...

2947
来自专栏向治洪

迭代子模式

概述 概念:在阎宏博士的《JAVA与模式》中关于迭代子模式的定义是这样的:迭代子模式又叫游标(Cursor)模式,是对象的行为模式。迭代子模式可以顺序地访问一个...

2016
来自专栏angularejs学习篇

angularjs学习第九天笔记(指令作用域【隔离作用域】研究)

531
来自专栏听雨堂

深入理解字符串和字节数组转换

      前文中,论及字符串和字节数组的转换,虽然能够找到某个代码页,保证转换的可逆,但是在实际处理中,仍然还有一些细节问题需要注意.       最重要的...

1668
来自专栏java达人

漫谈数据库索引

一、引言 对数据库索引的关注从未淡出我的们的讨论,那么数据库索引是什么样的?聚集索引与非聚集索引有什么不同?希望本文对各位同仁有一定的帮助。有不少存疑的地方,诚...

1739
来自专栏老马说编程

(28) 剖析包装类 (下) / 计算机程序的思维逻辑

本节探讨Character类,它的基本用法我们在包装类第一节已经介绍了,本节不再赘述。Character类除了封装了一个char外,还有什么可介绍的呢?它有很多...

1757
来自专栏高性能服务器开发

什么是B+Tree

B+Tree的定义 B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征: 1、有m个子树的节点包含有m个元素(B-Tree中是m-1...

2928
来自专栏用户画像

外部排序的方法

在实际应用中,由于外存设备的不同,通常又可分配磁盘文件排序和磁带文件排序两大类。磁带排序和磁盘排序的基本步骤相类似,主要的不同之处在于初始归并段在外存介质中的分...

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

agc016D - XOR Replace(图论 智商)

不难看出,我们把所有数$xor$起来的数替换掉之后再次$xor$,得到的一定是被替换掉的数。

585
来自专栏angularejs学习篇

angularjs学习第九天笔记(指令作用域【隔离作用域】研究)

1002

扫码关注云+社区