周刊（第23期）：图解Blink-Tree：B+Tree的一种并发优化结构和算法
引言：《Efficient Locking for Concurrent Operations on B-Trees 》论文中提出了一种称为“Blink-Tree”的数据结构，这个数据结构提供了B+Tree并发访问的一些优化方式，本文对这篇论文进行解读。
概论
由于Blink-Tree本质上是B+Tree的一种优化，所以要理解它首先要对B+Tree有一些了解，在这以前介绍过B+Tree，就不在这里阐述了，可以参考：
我们来看如果同时存在两个读写操作并发访问一颗B+Tree，会出现什么问题，见下图：
进程P1查询数据15，而进程P2写入数据9，当P2写入数据完毕时，树结构变成了下图这样：
由于原先的叶子节点要满足B+Tree的性质，所以分成了两个叶子节点，而这时P1进程对此并没有感知，还停留在旧的节点上，于是就导致了查询数据15失败。
一种最直观的优化方式是读、写的时候加全局锁，但是这样做的效率不高。Blink-Tree就是为了高效解决这类并发访问问题引入的一种结构和算法。
数据结构
Blink-Tree本质上还是一颗B+Tree，即数据存储在叶子节点上的B-Tree。
对于一颗k-degree的Blink-Tree而言，它有如下的性质：
- 所有叶子节点是同一高度的，即从根节点到每个叶子节点都是同一长度。（Each path from the root to any leaf has the same length, h.）
- 对于每个内部节点而言，除非是根节点，否则都至少有
k+1子节点。（Each node except the root and the leaves has at least k + 1 sons.） - 根节点要么是叶子节点，否则至少有两个子节点。（The root is a leaf or has at least two sons.）
- 内部节点最多有
2k+1个子节点（Each node has at most 2k + 1 sons），结合上面的内容即内部节点的子节点数量在[k+1,2k+1]之间。 - 数据都存储在叶子节点上。
可以看到，上面的性质和B+Tree很相似，在此基础上Blink-Tree还增加了以下数据：
-
在每个节点（包括内部节点和叶子节点）中，键以递增顺序排列。
-
内部节点还存储了称为“高键（high key）”的数据，这个数据用于存储本节点中最大键的数据。
-
同层的兄弟节点之间，以
“指针”相连接。
如下图就是增加了high key和link指针之后的blink-tree示意图：
算法
对数据结构有了解之后，来看看算法的实现，不过在具体展开之前，还要先了解几个概念。
high key引入的变化
有了high key之后，如果在插入数据之后发生了split，新旧节点会发生以下的变化（这里假设旧节点为a，split之后的节点从左到右为a'、b'）：
- 旧节点a：a的high key变成了
b'的high key。 - 新节点a’：新节点
a'产生了新的high key，同时这个high key被写入到了父节点中。
以上流程可以看看下面的图示：
上图中：
- split之前：旧节点
a的high key为74，这个值同时也做为父节点的key保存在父节点中。 - split之后：新节点
b'的high key还是旧节点a的high key（74），而新节点a'的high key为51，同时这个新的high key也更新到了父节点中。
这是引入high key这个数据最重要的变动，后面会讲到这个数据的作用。
safe和unsafe节点
在类B-tree类结构中，当插入、删除数据之后，可能会导致节点的数据量不满足条件，对应的就需要进行分隔（split）以及合并（merge）节点操作，于是就有了safe和unsafe节点的定义：
- safe节点：
- 在insert时，如果μ < 2k，这意味着即便插入数据完成也不会违反上面的节点数据量条件，这样就不需要分隔节点。
- 在delete时，如果μ > k，这意味着即便删除数据完成也不会违反上面的节点数据量条件，这样就不需要合并节点。
- 除了上面这两个条件之外，其他所有的更新数据操作都会导致节点变成
unsafe节点。
算法
查找流程
下面伪代码中的scannode(v,A)表示在内存中的节点A中查询v的子流程，就不在伪代码中表示出来了。
伪代码的流程其实很简单：从根节点开始，按照树形的结构查询数据，首先查内部节点，然后再查询叶子结点，这与常见的树形结构体查询流程并无太大区别，就不再展开解释了。值得注意的是前面讨论过的并发访问时的问题，这将在下面讨论。
procedure Search(）
/* 读入根节点到内存 */
current <- root; /* Get ptr to root node */
A <- get(current); /* Read node into memory */
/* 依次查找路径上的内部节点 */
while currentt is not a leaf do
begin /* Scan through tree */
current <- scannode(u，A）/*Find correct（maybelink）ptr */
A <- get(current） /* Read node into memory */
end；
/* 到了这里意味着查询到了叶子节点 */
/*Now we have reached leaves. */
while t< scannode(u，A）= link ptr of A do /*Keep movingright if necessary
begin
current <- t;
A <- get(current）/* Get node */
end；/* Now we have the leaf node in which U shouldexist.*/
/* 根据结果返回查询结果 */
if u is in A then done "success" else done “failure"
写入流程
原论文中，写入数据流程这部分的伪代码太长，我做一下精简和浓缩，如下：
向树中插入数据v：
初始化保存路径上经过节点的栈
// 第一部分：内部节点的遍历
如果当前的节点还是内部节点：
加载节点t到内存中
将当前节点t保存到栈中
查找路径上的下一个内部节点
// 到了这里意味着到了叶子节点这一层
// 第二部分：在叶子节点上遍历找到数据所在的叶子节点
对上一步最后的内部节点加锁
在叶子节点所在的层逐步向右遍历找到节点所在的叶子节点，流程如下：
如果当前节点不是v所在的叶子节点，且不为空节点：
加锁当前节点
释放上一个被锁住的节点
将当前节点读入内存中
// 到了这里意味着找到了所在的叶子节点，下面进行插入操作
// 第三部分：修改所在的叶子节点插入数据
修改所在的叶子节点A插入数据：
如果叶子节点A是安全（safe）节点：
插入数据
解锁叶子节点A
返回
否则如果是不安全（unsafe）的节点：
插入操作时不安全意味着就要进行split操作
分配新页面用于保存split后的新页面B'
插入的数据v写入节点A'，需要split出去的数据写入节点B'
y为split后的A'的high key
写入B
写入A，同时修改父节点对应节点A的key为y
从栈中弹出上一个层次的节点，继续回溯做可能的平衡节点操作
解锁当前节点
上面流程中，查找数据的流程与上面的查找流程大体相同，不同的是如果修改的叶子节点是unsafe节点的情况，以论文中的图例来说明这个流程：
在上图中，如果最终插入的数据在叶子节点a中，同时该节点是非安全节点，要做split操作，假设新的节点为a'和b'，流程是这样的：
- 首先分配
b'的页面，而a'复用旧节点a的页面。 - 图（b）：修改
b'的link指针，指向旧节点a的下一个节点c。 - 图（c）：修改
a'的link指针指向b'，这一步修改完毕之后，旧节点a就能被a'替换掉了，即原先父节点、左子树的指针都从指向a修改成指向a'。 - 图（d）：修复父节点的指针及key指向新增的
b'，至此修改完成。
除了上面这个修改非安全节点的流程需要特别解释意外，还有几点需要注意的：
-
关于加锁：从上面的流程里可以看到，每次加锁的流程大体都是：
- 先加锁当前的节点
- 再释放掉上一个被加上的锁。
这样的做法，让锁的粒度会更细，换言之提高了并发度。
-
栈和回溯操作：在修改路径上任一个被遍历到的内部节点，都保存到一个栈中，这是因为split之后的平衡操作是自底向上的，即：当修改了叶子节点进行split平衡操作之后，可能又会导致父节点不平衡，于是又要对父节点继续平衡，这一操作自底向上一直进行到某个父节点平衡为止。而要知道父节点，依赖的就是保存到栈中的节点信息，每次要继续向上平衡父节点，就从栈中弹出一个节点即可。
冲突的解决
以上大体清楚了BLink-Tree的查找和写入流程，回到本文最开始的问题：在读写并发的情况下，该数据结构如何保证不会出现待查找的数据刚好所在页面被split而查不到数据的问题？
答案是要借助high key的判断，还是把上面的high key示意图放在这里：
需要重复一下修改前后high key性质：当split出来之后的新节点a'，b'，其中a'的high key在split之后需要进行重新计算，同时这个high key需要更新到父节点的key中，也就是上图中的51；而b'节点的high key继续为旧节点的high key，也就是图中的74。
于是，查找到数据之后，如果数据所在的页面是非安全页面，那么页面可能发生split，即数据可能在a'或者b'这两个页面中，就有了以下两种可能的处理情况：
- 假设要找的数据落在了
a'中，那么不需要其它动作，直接返回即可，如图中的42、47还在a'中。 - 否则就是落到了
b'中，这时候需要沿着a'的link指针继续到右兄弟b'中查找，如图中的71，原先在旧页面a中，split之后落到了b'中。
问题来了：查找流程如何判断落在了split之后哪个页面中呢？答案是查找到数据之后，将数据与页面当前的high key进行对比即可，比如：
- 如图中如果查找的是42，比split之后的
a'的high key 51还小，于是就只会落到a'中。 - 否则如果查找的是
71，比split之后的a'的high key 51还大，于是就只会落到b'中。
可见：引入high key和link指针，解决了树在修改过程中发生平衡操作时的查找定位问题。
总结
- Blink-Tree是B+Tree的一种变形，引入了high key和指向右兄弟节点的link指针。
- 通过这两个数据的引入，在并发查找时可以做为节点是否发生变更的根据。
- 同时Blink-Tree的并发度更优，加锁粒度更细。