B-Link树

B-Link Tree总结

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

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

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

搜索

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

插入

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

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

分裂

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