共计 3125 个字符，预计需要花费 8 分钟才能阅读完成。
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 来作为其存储引擎的索引。
