B+Tree自从创造以来就成为了各种数据库引擎的首选，尽管近些年来LSM-Tree构造的数据库如雨后春笋般涌现，但B+Tree因为其优异性能以及各场景中平衡的性能体现，仍然是各数据库的首选项。

但B+ Tree也并非毫无毛病，作为一种均衡多叉树结构，其劣势是在数据量大时也能放弃较低的树高，因此其无论查问或者是更新其代价均较低。但树的一大弊病是在更新时会触发结构调整，这种结构调整最长可能从叶子节点延长至根节点，而这种树结构的调整会阻塞并发的读写操作，进而导致性能消退。因而，如何优化B+ Tree在该场景下的并发拜访性能也是学术界和工业界的一个重要的钻研方向。

本文对于B-Tree和B+Tree进行了一个简略的介绍，并且重点介绍了在B+Tree的根底上提出的一种称之为B-link Tree的数据结构，通过一种比拟奇妙的办法优化了B+ Tree结构调整时的锁粒度，晋升并发度，放弃高并发下的性能稳固。

一、B Tree和B+Tree

B-Tree是为磁盘等外存储设备设计的一种均衡查找树。因而在讲B-Tree之前先理解下磁盘的相干常识。

零碎从磁盘读取数据到内存时是以磁盘块（block）为根本单位的，位于同一个磁盘块中的数据会被一次性读取进去，而不是须要什么取什么。

InnoDB存储引擎中有页（Page）的概念，页是其磁盘治理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

mysql> show variables like 'innodb_page_size';

而零碎一个磁盘块的存储空间往往没有这么大，因而InnoDB每次申请磁盘空间时都会是若干地址间断磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为根本单位，在查问数据时如果一个页中的每条数据都能有助于定位数据记录的地位，这将会缩小磁盘I/O次数，进步查问效率。

B-Tree构造的数据能够让零碎高效的找到数据所在的磁盘块。为了形容B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不雷同。

B-Tree中的每个节点依据理论状况能够蕴含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范畴域对应三个指针指向的子树的数据的范畴域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范畴为小于17，P2指针指向的子树的数据范畴为17~35，P3指针指向的子树的数据范畴为大于35。

B+Tree是在B-Tree根底上的一种优化，使其更适宜实现外存储索引构造，InnoDB存储引擎就是用B+Tree实现其索引构造。

从B-Tree结构图中能够看到每个节点中不仅蕴含数据的key值，还有data值。而每一个页的存储空间是无限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查问时的磁盘I/O次数，进而影响查问效率。在B+Tree中，所有数据记录节点都是依照键值大小程序寄存在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样能够大大加大每个节点存储的key值数量，升高B+Tree的高度。

因为B+Tree的非叶子节点只存储键值信息，假如每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其构造如下图所示：

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环构造。因而能够对B+Tree进行两种查找运算：一种是对于主键的范畴查找和分页查找，另一种是从根节点开始，进行随机查找。

B+Tree绝对于B-Tree有的不同能够通过如下几点进行演绎：

  • 非叶子节点只存储键值信息
  • 所有叶子节点之间都有一个链指针
  • 数据记录都寄存在叶子节点中

二、B-Link Tree的外围主张

第一，在两头节点减少字段link pointer，指向右兄弟节点，B-link Tree的名字也由此而来。

第二，在每个节点内减少一个字段high key，在查问时如果目标值超过该节点的high key，就须要循着link pointer持续往后继节点查找。

一棵典型的B-link Tree如下：

图中咱们看到，每个两头节点也减少了一个后继指针指向其右兄弟节点，如果要查问的值超过该节点内的high key，那么还须要查问其后继节点。

咱们举例说明B-link Tree的劣势。假如有上面这样一颗B+ Tree且叶子节点y已满：

如果此时线程A要查问15，而线程B要在节点y内插入值9，咱们看上面的执行序列：

如果不作任何的并发爱护，就会呈现因为节点决裂而导致拜访了谬误叶子节点进而查找的目标值不存在问题，很显著这与理论状况不符。

最简略的计划是在树结构调整时应用全局锁住整棵B+ Tree，阻止所有并发拜访直到树结构调整结束，InnoDB晚期也是采取了该做法，当然这会导致性能特地差。

而B-link Tree则回绝全局锁这一做法。它执行一种自底向上的调整办法，每次只对以后调整节点加锁，当子节点调整结束后再向上回溯调整父节点，直到所有调整结束。

下图演示了插入新记录引发的节点决裂过程：首先创立新节点，将原节点上的局部数据拷贝至新节点，建设这两个节点的连贯关系（这个步骤最为要害），最初再向其父节点插入新的索引节点（图中d和e）。

B-link Tree这种无需加锁的设计可能导致的问题是父节点视图（尚未插入新索引）和曾经决裂的子节点不统一，那它是如何解决下面提出的问题呢？

这时候link pointer便显示出了价值。如果其余线程在子节点批改实现后但父节点批改前拜访，顺着父节点查问到旧的子节点时可能查不到已有数据，此时就须要沿着该子节点通过其link pointer找到正确的拜访门路。

同样还是下面的例子：

当节点y决裂成为y和y+两个节点后，而父节点x中尚未体现出这种决裂，此时查找15，顺着x找到节点y，在y中未能找到15，但判断15大于其中记录的high key，于是顺着指针找到其后继节点y+，最终找到该值，因此能确保正确性。

在B-link Tree的决裂计划中并没有对波及决裂的子树加全局锁，但通过节点的右连贯指针也能够正确地进行查找。

三、B-link Tree优劣势总结

B-link Tree的劣势在于树结构调整时无需对全局或者部分子树加锁，进而有利于高并发下的性能稳定性。

而B-link Tree的劣势则次要集中在以下两个方面：

第一，每个节点减少额定字段，link pointer和high key，但代价不大；

第二，查问时须要额定判断，如果查问找超过high key，须要额定通过link pointer查问其后继节点，在数据库利用中可能会产生一次额定的IO，从而造成单次查找性能的降落，但因为树结构调整是一个频率较低的动作，而且查问后继节点的操作也只会产生在子节点调整和父节点调整过程之间，一旦父节点调整结束，就能够通过父节点的指针间接查问了而无需再通过子节点的后继指针查找。

总结来看，B-link Tree通过空间换工夫，在每个两头节点也减少后继指针来防止在树结构调整时全局加锁而带来性能消退，这是一种很优良的计划，在GreenPlum中就应用了B-link Tree来作为其存储引擎的索引。