Radix Tree在Hyper中的实现：解读Hyper论文《 The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases 》

刺骨的言语ヽ痛彻心扉 2022-06-17 03:23 48阅读 0赞

有问题可以给我发邮件zhangtiey@gmail.com

本文讨论如何在实际的数据库系统中应用Radix Tree作为索引，暨解读HyPer的论文：The Adaptive Radix Tree:ARTful Indexing for Main-Memory Databases。本人和其作者Viktor有过一段时间的共事，希望对大家能有帮助。

Radix Tree实际上就是前缀树，也称之为Trie。相比B-Tree，其最大的特性是1）数的高度不随表的大小而增长，而是和key的长度有关；2）更新和删除不涉及到树结构的调整。但是因为常用方法往往造成空间上的浪费，所以Radix Tree并没有广泛应用在DBMS中。相比之下Linux的文件系统使用Radix Tree进行文件路径的索引，显而易见是因为前缀树的正好符合文件路径的特性。HyPer的这篇文章从实用的角度（发在ICDE也是这个原因）阐述了如何在实际的DBMS中实现Radix Tree。

其核心的思想是如何减少空间的浪费。让我们先举一个简单的例子，看看Radix Tree如何浪费空间的。如下图所示，我们有一颗Radix Tree，每个Node是一个vector<char>，里面的每个元素存了一个byte（实际系统中，byte是最好的方式）。如果我们要存储字符串，那么vecotr的大小是26。因此每个Node的大小是26 Bytes。假如我们有100个字符串要索引，但每个字符串只用到了a, b ,c , d，那么对于26 Bytes的空间，只用了4个Byte，剩下的全部浪费掉了。

ART设计了4中Node类型：Node4，Node16，Node48和Node256，这里数字的含义是包含了多少个元素。比如Node4只能存放4个元素，Node16存放16个元素，Node48存放48个元素，Node256存放256个元素。为什么最大的类型是存放256个元素呢？因为上面我们提到，vector中每个元素是一个Byte，即8 bit。那么表示的范围是0~255。也就是说我们不仅仅能存储字符串，也可以存储integer。比如存储一个整数5，那么对于64-bit的机器而言，它的表示方式是0x00 00 00 05。即4个Byte。对于Radix Tree需要四层来存这个整数，每一层存一个Byte前缀。

![Center][]

在ART的设计中，Node4是两个数组，一个数组是vector<char> key(4)，一个是vector<Tree\*> pointer(4)：key里是4个元素，每个元素是一个Byte；pointer存了对应的子树指针（指针是8个字节）。例如我们要存储字符串art（如上图所示），树的第一层的node是Node4类型，第一个数组key存了字母a，相应地，第二个数组pointer的第一个元素存了a对应的子树的指针。同理Node16也是两个数组，结构一样，只不过可以存16个元素。

Node48也是两个数组，只不过第一个数是256个元素（这样就涵盖了Byte所有表示的全部可能性），第二个数组是48个元素（每个元素还是指针），这也是为什么叫Node48的原因。所以可以看到，虽然第一个数组可以存256个元素，但实际上只存了48个元素，有一定的空间浪费，但为了效率，只能这么做了。

Node256只包含了一个数组vector<Tree\*> pointer(256)，因此可以直接通过下标访问，判断对应的指针是否存在。

上面四中类型就是ART最重要的数据结构。每次新生成节点的时候，都是Node4类型，也就是最小的。插入数据的时候，如果发现放不下了，就要扩充节点容量变成比当前大一级的节点。

请同时参照ART的论文进行理解。

[Center]: /images/20220617/db39f21dc2ab44e5be40643a265f6361.png