B-Link-Tree
简介
B-Link-Tree是B+ Tree的一个变种；优化了B+ Tree结构调整时的锁粒度，提升并发度，保持高并发下的性能稳定
在中间节点增加字段link pointer，指向右兄弟节点，B-link Tree的名字也由此而来
在每个节点内增加一个字段high key，在查询时如果目标值超过该节点的high key，就需要循着link pointer继续往后继节点查找
特点
树结构调整时无需对全局或者局部子树加锁，进而有利于高并发下的性能稳定性；
每个节点增加额外字段，link pointer和high key，但代价不大
查询时需要额外判断，如果查询找超过high key，需要额外通过link pointer查询其后继节点，在数据库应用中可能会产生一次额外的IO，从而造成单次查找性能的下降，但由于树结构调整是一个频率较低的动作，而且查询后继节点的操作也只会发生在子节点调整和父节点调整过程之间，一旦父节点调整完毕，就可以通过父节点的指针直接查询了而无需再通过子节点的后继指针查找。
结构
节点分裂过程
B+ Tree在分裂时，为了保证一致性，需要使用全局锁住整棵树；
B-Link-Tree在分裂时，执行一种自底向上的调整方法，每次只对当前调整节点加锁，当子节点调整完毕后再向上回溯调整父节点，直到所有调整完毕。
应用
- 在GreenPlum中就使用了B-link Tree来作为其存储引擎的索引。