DB存储引擎：B-Trees存储引擎详细分解

【摘要】：存储引擎说白了就是如何存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。用户可以根据应用的需求选择如何来存储数据、索引、是否使用事务等。选择合适的存储引擎往往能够有效的提高数据库的性能和数据的访问效率，另外对于某些数据库中的多个表可以使用不同引擎的组合以满足各种性能和实际需求。相比哈希存储引擎，B树存储引擎不仅支持随机读取，还支持范围扫描。关系型数据库中通过索引访问数据，其用到的存储引擎大部分都是基于B树、B+树等技术实现的。本文主要基于B树存储引擎的数据结构、架构原理以及数据存取特点等关键技术进行讨论分解并展示一个详实的B树存储引擎视图，以便更好掌握相关数据库技术。

【关键字】：存储引擎；B树；B+树；随机读取

1. 存储引擎简介

接触数据库比较深的人可能对存储引擎并不陌生，但是大多数数据库管理员可能对存储引擎并不熟悉，因为我们大多数关系型数据库的学习者并不需要关心存储引擎的选择和应用，因为我们熟知的 Oracle 、 SQL Server 等数据库基本只有一种存储引擎，没有给大家选择和设计的机会。但是如果我们接触 MySQL 以及其他一些 NOSQL 数据库比较多的人可能对存储引擎就会深有感受。

那么存储引擎是什么？它主要解决什么问题呢？

首先，我们认为存储引擎就是如何为了解决存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。用户可以根据应用的需求选择更适合自己应用场景的存储引擎来提高数据库的性能和数据的访问效率。常见的存储引擎有哈希存储引擎、 B 树存储引擎、 LSM 树存储引擎等三种。不同的存储引擎对数据的结构、数据的存储方式、数据的读取方式等都有不同的要求和特点。今天我们要跟大家分享的是关系数据库当中最常见的 B 树存储引擎。 B 树存储引擎是一种利用 B 树、 B+ 树等数据结构对数据库进行增、删、改、查的存储引擎技术。利用 B 树存储引擎的常见数据库有 Oracle 、 DB2 、 MySQL 等关系型数据库。

2. B 树存储引擎的数据结构

基于平衡二叉树的改进版本有很多，常见的有 B 树、 B+ 树、 B* 树等。本文我们不做全部探究，只针对最常用最基本的 B 树 &B+ 树的数据结构特点进行展开。

2.1 B 树索引数据结构

相信大家在大学的课程当中都学过二叉树以及平衡二叉树数据结构， B 树数据结构其实是在此基础上的一种升级和改进。最早是由德国计算机科学家 Rudolf Bayer 等人于 1972 年在论文 《 Organization and Maintenance of Large Ordered Indexes 》提出。具体特征如图 2.1.1 所示， B 树事实上是一种平衡的多叉查找树，也就是说最多可以开 m 个叉（ m>=2 ），我们称之为 m 阶 b 树：

图 2.1.1 B 树

总的来说， m 阶 B 树满足以下条件： a. 每个节点至多可以拥有 m 棵子树。 b. 根节点，只有至少有 2 个节点（极端情况，就是一棵树就一个根节点 ) 。 c. 非根非叶的节点至少有 Ceil(m/2) 个子树 ( 图中 5 阶 B 树，每个节点至少有 3 个子树 ) 。 d. 非叶节点中信息包括 [n,A0,K1, … ,Kn,An] ，其中 n 表示该节点保存的关键字个数， K 为关键字且 Ki （对应到关系型数据库当中的信息，就是二位表当中记录的主键信息）。 e. 从根到叶子的每一条路径都有相同的长度，也就是指向这些节点的指针为空。

B 树的查询过程和二叉排序树类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。上文提到 B 树是基于平衡二叉树的升级或者改进版本，那么介绍到这里可能大家也比较清楚了，为什么要改进呢？ B 树的节点子树可以更多，这就意味着同样的数据元素规模， B 树的高度会更低，检索的时间复杂度就会低，如果这个检索在数据库当中大多数情况是落在磁盘上的寻址，那么这个改进的意义就更大了。

2.2 B+ 树索引数据结构

作为 B 树的加强版称之为 B+ 树，图 2.2.1 所示，从图中所示的状况我们可以很直观感受到： B+ 树与 B 树最大的不同是所有数据记录都保存在叶子节点中，叶子结点是有指针将所有数据连接起来的。

具体来说， B+ 树与 B 树的差异在于： a. 有 n 棵子树的节点含有 n 个关键字（也有认为是 n-1 个关键字） ; b. 所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接 ; c. 非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字 .

由于采用了这样的结构， B+ 树对比 B 树有以下两方面优点：

首先，索引节点上由于只有索引而没有数据，所以索引节点上能存储比 B 树更多的索引，这样树的高度就会更矮。那么查询的时间复杂度就会更低。

再有，因为数据都集中在叶子节点了并且叶子节点增加前后指针，指向同一个父节点的相邻兄弟节点，给范围查询提供遍历。而如果使用 B 树结构，由于数据既可以存储在内部节点也可以存储在叶子节点，范围查询可想而知是很繁琐的。

3. B 树存储引擎数据操作原理

3.1 B 树存储引擎数据检索算法

对于基于二叉树数据结构基础之上形成的树的存储结构，那么其查询数据最核心的算法就是二分法查找算法，即通过键值的比较排除一定比例的可能性，从而缩小数据查找的范围，最终通过几次比较定位到要查找的数据。直观表现期间，我们还是以图为例：

图 2.1.1 B 树检索算法

按照图示，我们查找的数据是 L ，

首先，将根节点的数据块从磁盘读入内存，读出 P 值，比较发现小于 P ；

接着，遍历根节点左指针指向数据块，读出 C 、 F 、 J 、 M 值，顺序比较后，找到 J&M 之间的指针；

最后，遍历指针指向数据块，读出 K 、 L 值，定位所查询的数据 L 。

根据以上算法，那么本次查找经历了三次磁盘的读取，三次内存数据的比较。由此看见， B 树检索的时间复杂度主要取决于树的深度以及节点内保存的数据数量的多少。

对于 B+ 树的检索，其实算法与 B 树非常类似，其主要区别在于 B+ 树的所有检索操作都不会在非叶子节点结束，每一个检索都会经历相同的长度，那就是从根节点到叶子节点，途中经历的非叶子节点只保留索引信息，只有叶子节点才会保留所有键值数据。这种算法把所有遍历的复杂度留在了叶子节点的扫描上，减少了检索途中的 IO 次数，保证了叶子节点扫描的局部优势，同时也保障了所有检索操作的时间复杂度相对的稳定性。因此大部分关系型数据库选择的是 B+ 树作为其存储引擎。

3.2 B 树存储引擎数据插入算法

形成一棵 B 树，那么必须遵循 B 树的基本规则（也就是其数据结构的特点），那么插入节点的时候，必须也得遵循其固有的数据结构特征（ a. 每个节点至多可以拥有 m 棵子树。 c. 非根非叶的节点至少有 Ceil(m/2) 个子树 ( 图中 5 阶 B 树，每个节点至少有 3 个子树 ) 。这样就形成了 B 树插入的基本算法：

首先、根据插入节点的键值来检索其合适的节点位置，具体算法与检索算法相同；

其次、当找到具体节点位置的时候需要做判断：插入数据节点是否已经溢出（节点当中的键值数量是否符合 B 树规则），如果没有溢出，则直接插入数据。如果已经溢出，那么寻找这些键值当中的关键中间值，以其为界分裂节点产生新的子树。

具体如图所示，由于插入数据 [V] ，导致节点 [P,Q,R,S,T,U,V] 数据量不满足平衡性要求，这时将其分裂为两个节点，同时将中间的节点 S 提升到父节点中形成 [N,S,W] ，同时修改子树指针。

图 3.1.1 B 树节点分裂

B+ 树的插入算法与 B 树非常类似，但是由于 B+ 树的非叶子节点只有索引信息没有键值信息，所以 B+ 树的节点分裂实在叶子节点上完成，同时非叶子节点需要更新其索引信息以及相应的指针信息。

3.3 B 树存储引擎数据删除算法

相对于插检索和插入算法来讲， B 树的删除算法相对比较复杂，代价也比较高，因为删除节点键值的操作非常有可能导致 B 树结构不符合既有的规则条件，那么就需要再平衡。

首先，我们需要知道 B 树达到平衡的重要条件：无论是内部节点还是叶子节点，其存储的键值数量在 [t-1,2t-1] 之间，如果数量不满足此条件，需要做重平衡操作。如果少于 t-1 ，需要借用或合并数据；反之，如果数据量大于 2t-1 ，则需要分裂成两个节点（这里我们用 t 表示 B 树的深度参数）。

接着，在明确了 B 树平衡的重要条件基础之上，我们来看 B 树删除节点时的具体算法步骤：

(1). 查询到键值所在的叶子节点，删除该叶子节点的数据。

(2). 如果删除叶子节点之后的数据数量，满足 B+ 树的平衡条件，则直接返回不用往下走了。

(3). 如果删除叶子节点之后的数据数量，不满足 B+ 树的平衡条件，就需要做平衡操作：

a. 如果该叶子节点的相邻节点的数据量可以借用，就借用过来满足平衡条件；

b. 否则，就只能与相邻的兄弟节点合并成一个新的子节点了。

(4). 在上面平衡操作中，如果是进行了合并操作，就需要向上修正父节点的指针，如果父节点也不再平衡，那么就按照前面的步骤也对父节点进行重新平衡操作，这样一直到整体平衡为止。

4. B 树存储引擎优略分析

通过对 B 树存储引擎的数据结构以及数据操作原理的介绍，相信大家对其优缺已经有所感悟。文到此处，有必要根据 B 树本身的特点来给大家明确其优缺之间的内在关系。

首先，通过对 B 树和 B+ 树的检索算法特点来看，从使用的角度上来说， B 树索引存储结构多用于 OLTP 型的数据库，因为这类数据库主要以事务，或是行级别的读取和存储为主的（比如 MYSQL ）。换言之，这种类型的数据库更多的操作是小批量或单行级别的随机读取和更新，并且还有事务方面的需求。在此前提条件之下，之所以有 B+ 树的诞生，取决于以下两点： a. 磁盘读写代价更低。 B 树的内部结点并无指向关键字具体信息的指针。所以其内部结点相对 B 树更小。若是把全部同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来讲 IO 读写次数也就下降了。 b. B+ 树只要遍历叶子节点就能够实现整棵树的遍历。并且在数据库中基于范围的查询是很是频繁的，而 B 树实现这样的操作需要的代价非常高，效率非常低。

其次，通过对 B 树和 B+ 树的更新和删除算法特点来看，虽然算法相对哈希及其他存储引擎实现的算法来讲会显得非常复杂，代价很高。但是从另外一个侧面来看，正是由于它没有通过大量的数据追加实现更新和删除，它就无需去管理那些不同时间戳版本的重复数据。有效地利用了磁盘空间和内存空间，这个也与我们 OLTP 型关系型数据库的规模以及通用服务器硬件的配置非常匹配。

以上两点是我们通过 B 树的特点本身来分析出它最适合的应用场景，同时也是因为他的优点导致了它在其他场景下的一些略势。正是因为它的平衡树的结构导致它无法处理一些大小变化无常的数据，无明显线性顺序的数据；正式因为他的插入和删除的高代价，它也不适合批量的顺序写入场景，甚至写多读少的场景也不适合。

5. 总结展望

B 树存储引擎仅仅是一种数据存取技术的设计思想，很多关系型数据库在具体实现的时候都是基于这种基本的思想来展开实现，实现的过程中可能会改进其中的一些算法细节从而实现部分缺陷的优化，尤其是一些开源的数据库。但是这种存储引擎的基本思想是决定具体数据库产品的适用场景的最根本原因，本文希望通过这些原理性的讨论和分析展示给大家有一个宏观的视图，从而指导具体的数据库设计实践。当然也希望更多同业能从更多维度继续分析讨论并分享。

【 参考文献】

[1] https://github.com/facebook/rocksdb/wiki/Performance-Benchmarks
[2] https://www.shangmayuan.com/a/c8d86c0f17564902a28441ce.html

[3] https://my.oschina.net/u/4271740/blog/4300371

[4] https://stackoverflow.com/questions/2574661/existing-implementation-of-btree-or-btree-in-java

…