别B+树了，out了

水深无声 2024-03-24 18:10 62阅读 0赞

想必大伙都非常熟悉 B+Tree，面试常客，但是 Blink Tree 确实很少有人提到，它是 B+Tree 的升级版，据阿里云文档所述，通过对 B+Tree 的优化，可以将交易场景下 PolarDB 的读写性能提升20%。

### **B+Tree 的问题** ###

那么 B+Tree 哪块表现的不好呢？

主要是并发场景下，写操作导致节点分裂（SMO，Split Merge Operation）的时候，刚好有并发读操作访问到错误的叶子节点，查错了节点，那么目标值肯定就搜索不到了，于是导致了错误查询。

> **举个例子，比如现有如下的一个 B+Tree：**

![图片][5f3479d369f07042f4dce261235f15ba.png]

此时，插入一个数据 27，恰好页A满了，需要触发分裂，新增一个页B，且同时有个读取请求，想要访问数据 29。

![图片][c0a234e0bebf95cdc88e0bba5e82847c.png]

那么很有可能在分裂的时候，读请求访问到老的页面指针，指向了页 A，而页 A 内的 29 已经被分裂到新的页 B 中，这样一来读请求就发现没有 29 ，于是返回没数据，这就错乱了。

而且，叶子节点的分裂，可能会导致父节点的分裂，这种调整最长可能级联到根节点，并发场景下很容易导致错误，为了避免这种情况的发生，最简单的操作就是在发生节点分裂时，把整颗 B+Tree 都锁了。

这样一来数据的正确性得到了保证，但是性能就很低了，因为全局锁会影响了对所有页的访问。

后续 MySQL 对其在 5.7 版本后做了优化，但是整个 B+Tree 同时只能支持一个 SMO 操作的发生，高并发时大数据量插入导致多 SMO 的发生还是会被阻塞，影响性能。

### **Blink Tree** ###

Blink Tree 主要引入了 high key 和 link 指针来解决并发读写中间态数据访问出错问题，能降低锁的粒度，提高性能。

high key 存储了每个节点的最大值，每个节点的 link 指针则指向了同层右侧的兄弟节点，在写入数据的时候，仅需对当前节点加锁，当前节点修改完毕后立马解锁，锁的粒度很细，并发度很高。

那具体是如何解决并发时候 SMO 中间态问题的呢？

> **我们直接来看来阿里云官网给的一个示意图：**

![图片][6d5e8792589baed81c99bde772b9786a.png]

可以看到，相比于 B+Tree，Blink Tree的兄弟节点也进行了指针相连，当分裂在进行中还未完成，也就是父节点到新的子节点的链接还没有建立时，B+Tree 我们已经演示过了，并发读可能导致数据查询不到。

而 Blink Tree 就能解决这个问题，当读请求沿着老指针访问老页面的时候，对比下 high key，发现查询的值比当前页 high key 大，那么就沿着 link 指针找到旁边新分配的页面，此时就可以找到要查询的值了。

[5f3479d369f07042f4dce261235f15ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e267461d5c42468d8db58372db1b4ae5.png
[c0a234e0bebf95cdc88e0bba5e82847c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9f99f575ead745748456db53be8fe9b8.png
[6d5e8792589baed81c99bde772b9786a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c840839a3b8348e3ab02845adc552d1e.png