一、blink-tree简介

索引页保留指向弟弟的指针（下文称为blink指针），其余同B+tree。

该指针的意义是在索引页分裂的中间状态提供检索路径，如图：

此时根节点还未设置好，对27的检索仍会找到其长子，但27已不属其长子这一脉，如果此时发现索引正在分裂，则向右检索其弟弟。

有了这样的性质以后，索引的分裂就可以不用阻塞查询，以提高读写并发。然而要达成这个目标，还必须满足一个前提条件，即对页的写入必须是原子的，否则正在分裂的页被读取到时，就不会是一致的状态。如上图中，页(21,23,27)分裂为(21,23)和(25,27)有一个移动数据的过程，只有这两个状态才是一致的。

二、innodb现状分析

显然，目前innodb并没有支持这方面的设计，并不满足原子性。一方面，innodb的页与操作系统的页大小不一致，这就不能保证原子写入；另一方面，innodb对页的访问还有buffer pool这一层，并不会直接向表空间读写，作为内存区域，其部分修改对其它线程是立即可见的，要保证原子性，就只能加锁，而如果通过加锁与查询互斥，那blink-tree的性质就没有价值了。所以只改动数据结构，不对innodb进行大幅调整是不可行的。

三、innodb调整方案

为了满足原子性，只能考虑分裂时直接拷贝出两个新的页，这样在拷贝期间原页依然可读，拷贝完成后，先设置其blink指针，再以原子切换的方式设置原页的前驱的blink指针替换掉原页，这一步完成以后，新分裂的两个页就可见了，然后在其父页插入新分裂的两页，删除原页。至于磁盘，由于所有表空间得读写均在buffer pool中转，如果buffer pool保证了原子性，磁盘就只是一个持久化手段，blink-tree逻辑上以buffer pool为准，不用考虑磁盘状态。该方案可行，但代价明显，分裂时拷贝的代价加倍了，这还是中点分裂策略，考虑到innodb中广泛存在伴随顺序插入的端点分裂策略，相比之下方案的代价高得离谱，这样的优化未必值得。

如果要考虑避免这样的代价，就必须在原页上完成分裂和原子切换，那就必须逻辑上通过一步原子操作移动页内内容，可以借助特殊的标志位来完成。分裂时先拷贝数据到新页，此时原页数据无须改变，可读。完成后，先设置新页的blink指针，这一步仍然不改变原页。接着设置原页blink指针和标志位必须在一个原子操作中完成，标志位必须能够指出哪些数据已经被移走了，因此不再可见，这可以通过锁数据线来实现。理论上该方案完全可行，略有风险，第一是现有的innodb上能否完成这样的修改，即该修改的影响范围，由于涉及到分裂时移动数据的细节，还没有仔细研究；第二是锁数据线的操作如何实现，汇编的话移植性就有问题了，标准库和第三方库是否有这样的封装还没来得及研究。