B-Link树

B-Link Tree总结

B-Link Tree相比传统的B+树，主要有两个特点：

1. 内页有一个指向右兄弟页的指针。
2. 内页有一个high key，大于当前节点以及所有子节点中最大的key。

这两个特点，结合B-Link Tree的搜索、封锁、分裂方式，可以极大地降低并发冲突。主要特征总结如下：

搜索

• 搜索B树时，对非叶子节点只会上S锁，仅叶子节点可能上X锁。
• 搜索到叶子节点后，只会有对叶子节点的封锁，路径上的节点完全无锁。
• 获取下层页前，会先释放当前内页的封锁。
• 搜索时会将搜索路径上的页和索引元组登记到一个栈中。

插入

• 插入前，只会对待插入的叶子页上X锁，上层页都没有锁
• 插入时，若插入的叶子页已满导致分裂，将会自底向上加锁，X封锁父亲内页，插入索引元组，保证锁粒度始终是最小的。

  这一步为什么不会死锁： 按DM现有的逻辑理解，若线程1已经X封锁叶子页，发生分裂，试图X封锁其父亲页。线程2在搜索B树，已经S封锁了父亲页，试图获取叶子页，此时貌似会发生死锁，其实不然 关键在于，获取下层页时，会先释放当前内页的封锁，再对下层页加锁，所以此时线程2会先解开父亲页的封锁，抓叶子页时锁冲突等待，线程1可以对父亲页上X锁并完成分裂。

分裂

• 插入时，若发生分裂，利用搜索栈中登记的搜索路径，自底向上向上封锁、访问父亲页。
• 分裂时维护highkey，左页的highkey是右页最小key，即右页的索引元组，右页的highkey就是分裂前页的highkey。
• 分裂时会将左页打上分裂未完成标记，表示新右页的索引元组缺失，并记录redo日志。将新右页的索引元组插入到父亲页中后，会清除左页的分裂未完成标记。
• 若分裂时数据库宕机，重启后B树结构可能会不完整，只会有一种情况，即父亲内页中缺少分裂产生的新右页的索引元组。
• 即使分裂未完成宕机造成B树结构不完整，由于highkey和内页右指针的存在，以读方式访问B树时，也能保证搜索的正确性，即只读事务能正常查询该B树。
• 以写方式访问B树时，访问到分裂未完成的页，会为新的右兄弟页补全索引元组，插入到父亲页中。

更新删除

• 没有参考，需自主设计

原型设计

基于以上分析，可以得出以下结论：

• 理论上，B-Link Tree在高并发场景下可以极大地降低读写冲突，性能会显著优于当前的B树
• 即使没有并发，由于搜索栈的存在，分裂时不用重新搜索B树，而是直接自底向上访问父页，理论上性能也会更优
• B-Link Tree非最右内页的highkey很关键，必须维护，作用不可替代，页上也需要有一个标记表示分裂未完成，现有的存储需要调整
• 由于B-Link Tree的搜索、封锁、分裂等流程与当前的B树差距太大，需要新写一系列接口
• 由于PostgreSQL不会对B树进行更新，删除也仅支持批量删除，相关逻辑没有参考，需要自主设计
• 上层使用btr接口的地方，和目前的B树耦合度太高，需要排查修改
• 当前ptx仅支持释放S锁页，而且必须是memo数组最后；ptx需要支持单独释放中间的页，且可以是被上X锁且修改的页

原型开发计划

fys: 理论研究，架构设计，并发正确性研究，参考PG、Gauss等代码构建框架，接口实现

• nbtr_cur_search定位BLink树游标，上层使用方式与现在一致，底层走bltr_cur_search，仅支持读、写模式，不再区分MODIFY_LEAF、MODIFY_TREE
• nbtr_cur_insert插入记录到BLink树，底层走bltr_doinsert，之前必须用WRITE方式搜索游标。该函数内，传入的ptx可能会提交重启。
• nbtr_cur_delete删除BLink树记录，自主设计
• nbtr_cur_update原地更新，自主设计
• bltr_split分裂BLink树，过程中维护highkey，分裂点选择先按照原有逻辑
• bltr_insert_parent插入索引元组到父亲页
• bltr_insertonpg递归插入记录到页中
• bltr_moveright如果并发分裂，则访问右兄弟页
• pbcur适配BLink Tree

研发2: 配合完成btr层接口实现细节

• nbtr_cur_search，< <= = > >=五种模式，以及读写两种方式，搜索B树时游标应该落在哪里，研究现有策略，确保接口兼容性
• 根页分裂，PG用新的根页，我们需要保证根页地址不变
• 接口内封锁、修改页与当前ptx适配
• 分裂操作的原子性保证，redo日志生成适配
• ptx适配，目前页锁与ptx关系密切，修改页后，不能释放对页的封锁，必须ptx commit时一起释放，故改造后一次B树插入可能要用多个ptx完成
• 加锁、解锁逻辑，如何用现有ptx实现和PG一样的流程，如果无法实现，是否需要改造ptx

研发3: btr上层

• 语法支持，创建B-Link Tree索引时，字典的type是BL，xtype新增一个位表示B-Link Tree，类似于现在数组索引、空间索引等实现，只有显式指定才会创建BLink树索引
• CSEK、SSEK、CSCN等搜索B树操作符，确保正确性
• nins2_index_insert_entry中先以MODIFY_LEAF方式插入，页中空间不足失败，再以MODIFY_TREE方式插入，改造后不再需要进行重试，直接以WRITE方式插入B树即可
• nins2_clu_ins_new/nins2_sec_ins_new：其中NBTR_MODIFY_TREE_OPT相关逻辑不再需要，直接调用游标插入接口即可，类似的地方需要排查
• 回滚记录的处理，当前回滚记录可能和插入使用一个ptx，改造后插入本身就可能是多个ptx完成，需要重新设计
• fins、sins等需要适配
• 重建、重组索引等需要适配

TODO： 分裂过程中宕机，新的右兄弟页缺少pivot tuple，需要故障恢复，按照PG的方式 DSC、DPC等集群环境