【GaussTech技术专栏】GaussDB的BTree索引和UBTree索引

1. 简介

数据库通常使用索引来提高业务查询的速度。本文将深入介绍GaussDB中最常用的两种索引：BTree索引和UBTree索引。我们将重点解读BTree索引和UBTree索引的存储结构，探讨它们在读写并发、写写并发以及MVCC（多版本并发控制）能力方面的优势，并展望它们的未来演进。

2. BTree索引和UBTree索引结构

GaussDB的主流存储引擎有两种：Append Update存储引擎（Astore）和In-place Update存储引擎（Ustore）。更多Ustore，请阅《 GaussDB Ustore 存储引擎解读 》。

在Astore中，索引默认采用BTree；在Ustore中，索引默认采用UBTree。

相比于BTree，UBTree在叶子节点层额外维护了数据的MVCC信息。不管是BTree还是UBTree，都是采用基于L&Y撰写的论文《Efficient Locking for Concurrent Operations on B-Trees》和《ASYMMETRIC CONCURRENTB-TREEALGORITHM》改造而来的Blink Tree，其组织结构如图1所示。

图1：Blink Tree组织结构

图1中①到⑦都是独立的索引页面，GaussDB默认页面大小都是8K，采用堆表引擎结构，其中索引页和数据页分开存储。索引的叶子节点保留有指向数据页的行指针<K, V>，相比于传统B+树索引，Blink Tree具有以下特点：

1）不仅叶子节点兄弟之间有连接，非叶子结点的兄弟之间也有连接；

2）除了每层的最右侧节点外，其余节点内部都有一个highkey，该值是节点的upper boundary（上边界）；

3）一个节点的highkey，一定大于以该节点为根节点的子树的所有key；

4）除了叶子节点，其余节点每个<Key, Value>对（除highkey外）的value值均指向一个孩子节点，该key小于等于被指向子节点的最小值，是孩子节点的lower boundary（下边界）。

3. BTree索引和UBTree索引优势

3.1 高并发读写能力

BTree索引和UBTree索引，由于其特殊的结构设计，相比于传统的B+树，在数据查询方面有一定的性能优势，这主要是因为Blink Tree内部的两大特点：一是highkey的存在，二是所有层级兄弟节点之间直接相互连接的结构。这些特点使得BTree索引和UBTree索引在查询和插入操作时，能够采用更加友好的加锁协议，从而在高并发场景下实现了读写性能更佳。

• 读写并发优势

我们先来讨论BTree索引和UBTree索引在处理读写并发时的优势。为了更直观地对比，首先，回顾一下传统的B+树是如何查询数据的，其查询的流程如图2所示。

图2：B+树查询流程

首先，查询事务会先锁住根节点①，然后，通过二分查找找到<K11, V11>，接着锁住节点②，通过二分查找找到<K22, V22>，同时释放节点①的锁。之后，事务会锁住节点④，继续二分查找，直到找到目标值<K42, V42>，再释放掉节点②的锁，最后会释放节点④的锁。

以上过程是典型的蟹行协议，即总是会先持有子节点的锁，再释放父节点的锁，且同一时刻最多持有两把锁。显然，这对于高并发场景下的读写并发性能是不友好的。

我们再来看看BTree索引和UBTree索引在查询时是如何加锁的，其查询流程如图3所示。

图3：Blink Tree查询流程

首先，查询事务会锁住根节点①，然后，利用二分查找找到<K11, V11>。接着，事务会先释放节点①的锁，再锁住节点②，再利用二分查找找到<K22, V22>。紧接着，事务会先释放节点②的锁，再锁住节点④，最后通过二分查找找到目标值<K42, V42>后，再释放节点④的锁。

在以上过程中，总是先释放父节点的锁，再持有子节点的锁，且同一时刻最多持有一把锁。显然，这对于高并发场景下的读写并发性能是更友好的。

现在我们来讨论一下，为什么BTree索引和UBTree索引在查询时，相比传统B+树索引会有以上优势？

这主要是因为，一个事务在查询时，可能会有另外一个事务导致索引的节点分裂，进而导致从根节点到叶子节点的遍历过程中，如果先释放父节点的锁，再获取子节点的锁，可能会在持有子节点锁的时刻，目标元组<K, V>已经转移到了新分裂的节点。这时候需要有某种机制，可以快速地识别到这种情况，并且可以定位到目标<K, V>所在的节点，而Blink Tree的特殊结构可以比较简单地实现这种机制。

图4：Blink Tree Move Right机制

更直观地，以图4的例子来说，当查询事务在执行到Unlock ②与Lock ④之间的时间段时，如果有另外一个写事务插入了数据<K42’, V42’>，这将导致节点④发生了分裂，从而使得目标元组<K42, V42>转移到了新分裂的节点⑤中。

当查询事务再次Lock ④后，通过比较目标key，即K42和节点④的highkey大小，发现K42大于节点④的highkey，这说明K42已经不存在于节点④内部，而是存在于节点④右边的某个节点中（BTree索引和UBTree索引有约束，节点只能往右分裂）。此时会启动move right机制，从节点④开始往右遍历，直到找到一个highkey大于K42的节点，在图4中就是节点⑤。最后，在节点⑤中找到目标元组<K42, V42>。在这个过程中，同一时刻仍然最多持有一把锁。

相比之下，传统B+树索引目前是不能做到这些的。首先，它不能识别到节点④已发生分裂，其次，由于非叶子节点层的节点之间没有建立连接，故它不能实施一种类似于move right的机制。

• 写写并发优势

除了读写并发优势外，BTree索引和UBTree索引相比于B+树索引，还有数据写写并发的优势。BTree索引和UBTree索引与B+树索引在插入数据时，都会经历两个步骤：

1）找到插入位置；

2）插入数据。

步骤1是查询过程，BTree 索引和 UBTree索引在这个过程中，仍然可以保持同一时刻只有一把锁的优势。

步骤2是写入过程，如果节点需要分裂，BTree索引和 UBTree索引与B+树索引的处理机制并不相同，这时BTree索引和UBTree索引仍然有较大优势。

下面我们来探讨传统的B+树是如何插入数据的。

图5：B+树插入数据导致节点分裂

如图5所示，当新插入数据<K51’, V51’>找到了插入节点④时，发现节点④需要分裂成节点④和节点⑤，由于每一层节点的分裂，都有可能触发上一层节点发生分裂，因此会重新采用悲观加锁策略，将搜索路径上的所有节点（节点①，节点②和节点③）全部加写锁后，再执行插入和分裂操作。

这一操作对系统性能有显著影响。尽管部分存储引擎对B+树做了优化（比如加意向锁），但是往往只是优化读写并发的场景，写写场景的性能优化仍然比较困难。这是因为底层节点分裂时，需要一种轻量化的机制找到它的父节点以写入数据，而传统B+树难以实现。

那么为什么BTree索引和 UBTree索引在插入时就不需要悲观锁呢？

这仍然是Blink Tree特殊的存储结构决定的。我们来看Blink Tree是怎么在有其他写事务的干扰下实现节点分裂时找到正确的父节点的，如图6所示。

图6：Blink Tree 写写并发

事务1需在Blink Tree中插入新元组<K61’, V61’>。首先，从根节点到叶子节点遍历查找插入位置，在Unlock节点②和Lock节点④之间的时间段内，有事务2导致Blink Tree发生了分裂（节点②分裂成节点⑤），事务1找到节点④为插入节点，但发现节点④空间不足，遂节点④发生分裂，随后，事务1会根据记录的路径向上递归至父节点插入新的节点信息。当遍历到节点②时，事务1发现节点②并非节点④的父节点，于是从节点②开始move right，直到找到节点④真正的父节点。

由于move right机制的存在，BTree索引和UBTree索引从待分裂节点出发，向上能找到正确的父节点，并且只会对当前时刻涉及到写操作的节点加锁。这种方式相比于悲观地锁住整条搜索路径，更加轻量化，对于高并发的写写操作会更加友好。

3.2 MVCC能力和独立垃圾回收能力

UBTree索引是GaussDB Ustore的默认索引，它最大的特点是在叶子节点增加了MVCC能力以及独立过期旧版本回收能力。通过在索引页面的元组上维护版本信息，UBtree能够在索引层进行MVCC可见性检查。同时，UBtree也能通过版本信息独立判断索引元组是否已经无效（Dead），进而使得Ustore能实现数据表以及索引表上页级的空间清理，并在此基础上构建了一个不依赖Auto Vacuum的独立垃圾回收机制。

图7：UBTree与BTree查找、更新比较示意图

图7中的左图，展示了Astore和Ustore在索引扫描过程中的差异。索引扫描过程中，系统会通过扫描条件在索引上进行二分查找，找到符合条件元组的TID，再通过TID到数据表上查找对应的数据元组。对Astore而言，由于BTree索引没有版本信息，因此，元组的可见性检查需要完全在数据页面上进行。而对于Ustore，元组的可见性检查一部分可以在UBTree上完成，支持MVCC的UBTree索引过滤掉不可见的索引元组，从而减少了无效的页面访问和I/O操作。

图7中的右图，展示了Astore和Ustore索引列更新情况下的差异。在Astore中，更新操作会先将旧元组4标记为删除，再插入新元组10。由于BTree索引上4和10对应的TID不同，单次扫描中只有一个能通过可见性检查。

对于Ustore而言，更新操作采取in-place的方式，即直接在原位更新元组，可见性检查会返回一个对当前快照可见的版本。在in-place更新涉及索引列变更的情况下，4和10两个索引元组对应的TID会是相同的，若直接通过TID访问Ustore，会有两次读取可见版本的操作。然而，这种情况下UBTree通过索引层的可见性检查，能判断元组4已不可见，从而避免通过其对应的TID（如TID1）在Ustore上查找元组。

此外，对于UBTree而言，索引能实现页级别的独立清理。索引上的元组可以通过自身的版本信息来判断是否仍然有效。因此，在Insert空间不足时，可以直接清理页面上无效的元组。同时Ustore数据表上无效元组的行指针可以直接复用，这是因为UBTree同样可以检测出对应的索引元组无效，从而避免通过其TID来访问数据表。一旦数据表和索引都支持了页级别的独立清理逻辑，存储引擎就有可能一种实现完全不依赖Auto Vacuum的垃圾回收机制。

4. 总结与展望

本文先介绍了BTree索引和UBTree索引的存储结构BlinkTree，该索引的所有节点都和兄弟节点相连接，并且每个节点新增一个highkey作为节点key值的上边界。随后分析了BTree索引和UBTree索引，相比传统B+树在读写场景、写写场景有更强的并发能力的原因，这主要是因为Blink Tree特殊的存储结构，它可以支持move right机制，有效解决事务期间节点分裂的场景，使得事务在遍历Blink Tree时每个时刻持有更少的锁。最后，还介绍了UBTree的MVCC能力和独立垃圾回收能力。

尽管相比于传统B+树，BTree索引和UBTtree索引已经有诸多优势，但在未来，我们仍有许多关于BTree索引和UBTtree索引的优化工作。比如，UBTrree由于需要维护MVCC信息，导致索引占用空间变大。为了弥补这个劣势，我们可以将索引进行压缩或者寻找一种更节省空间的MVCC信息管理方法。GaussDB目前正在做一些这方面的研究工作，未来会分享我们的成果。

引用：

1. https://dl.acm.org/doi/10.1145/319628.319663

2. https://dl.acm.org/doi/10.5555/324493.324589

3. http://mysql.taobao.org/monthly/2020/06/02/