The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases( IEEE International Conference on Data Engineering)

摘要

RAM容量的发展使大多数数据库都能放到内存中。索引是内存数据库的至关重要的瓶颈。

传统的内存数据结构如二叉平衡搜索树在现代硬件上效率低，因为不能充分利用CPU cache。哈希表效率很高，但是只支持点查询。

ART 查找性能极好，也支持高效的插入与删除，节省空间，解决了最坏情况下的空间消耗。

简介

对于OLTP，生成的执行计划就是索引操作序列，因此索引效率是影响性能的至关重要的因素。

传统的内存索引结构是二叉搜索树，如T树，处理器架构的巨大改变使得其效率较低。原因是——原因是CPU cache的增大和不同的主存速度(NUMA)使统一内存访问(UMA)时间的基本假设过时。
（因此有了CCS树和CSB+树，基于缓存敏感对二叉搜索树和B+树的改进）

缓存敏感B+树(CSB+ Tree)有更缓存友好的内存访问机制，更新贵。而且二叉树和B+树在现代CPU上都还有一个问题就是：比较的结果不能简单的预测出来，the long pipelines of modern CPUs stall, which causes additional latencies after every second comparison (on average).

三类索引（搜索树、哈希表、前缀树）
搜索树：k路查询树和FAST(Fast Architecture Sensitive Tree)用SIMD同时进行多个比较。FAST通过最优化利用cache line和TLB来减少cache miss。它在查找上效率不错，但是不支持持续性的update。对于OLTP来说，持续的更新插入删除都是不可避免的，另一种解决方法delta又会导致额外的开销。
哈希表快，两个缺点：只支持点查询；不能很好处理数据的增长，溢出时需要O(n)重构 哈希表
前缀树Trie tree：时间复杂度O(k)，k是字符串长度。在大量数据下，因为它的时间复杂度只和k有关，和n无关，很好的性质。

多数前缀树都要通过设置全局的合法扇出系数(valid fanout parameter)来平衡树的高度与空间效率。ART的节点用了高效和紧凑的数据结构，可以基于孩子节点的个数动态选择。而路径压缩和lazy expansion允许ART折叠节点最终降低树的高度来更有效的索引长key。

相关工作：
CSB+，B+树更深的优化G. Graefe and P.-A. Larson, “B-tree indexes and CPU caches,” in ICDE,2001.
k-ary search
FAST
Tire
Kiss-Tree

Adaptive Radix Tree

准备工作

radix tree与基于比较的树的区分点：

• radix tree的高度取决于key的长度，一般与树中元素的个数无关
• radix不需要平衡
• key按词典顺序存放
• 路径代表叶子节点的key，key的存放是隐性的，可以由路径重构

两种节点，内部节点 映射(部分key—其他节点)，叶子节点 存相应key的value。中间节点一般是2的s次幂个指针的数组。树遍历的时候，s bit个chunk的key用于索引数组，无需比较得到下一个孩子节点。s叫span，对于radix tree的性能至关重要，s和key的length共同决定了树的高度。

在完全搜索树中，每次比较会排除一半的值，而在平衡radix tree当s>1时能排除更多。当n>2^(k/s)时，radix tree的高度就比搜索树低了。

假设对于large key的比较时间复杂度是O(k)，那么对于搜索树时间复杂度是O(k*log n)，而radix tree时间复杂度是O(k)。
span较大的radix tree比传统搜索树效率高。

Adaptive Nodes

span大，当大多孩子指针都是空的时候就造成了空间浪费

span的不同树的高度与空间消耗.png

随着span的增加，树的高度线性下降，空间消耗指数级增加。

ART用的是相对大的span有不同扇出的不同节点大小

这种节点不会影响树的结构，只会影响节点的大小。通过减少节点空间消耗，自适应节点允许用更大的span来增加性能。

持续的更新导致在每次更新后会重新构建节点大小，很贵； 这里用集中节点类型，每个都有不同的扇出。根据非空孩子的个数用对应的节点。当一个节点由于插入用完了，就用更大的节点类型取代。由于删除不满了，就换更小类型的节点。

中间节点的数据结构

节点大小是不同的

span为8，可以存的部分key就是1byte，实现起来简单，也不用进行位操作和标记操作

没有用键值对的list，而是将list分成了键 和 指针两部分——可以存的更紧凑

Node4：存4个孩子指针。key有序(1byte4 + 8byte4)
Node16：存5-16还孩子指针。key可以通过二分查找或者在SIMD中并行比较来快速查找。(1byte16 + 8byte16)
前面的key数组里面存的是key的值，在查找的时候是通过查找key数组来看它有没有，然后根据它所在key数组的位置(偏移量去)去指针数组中找

Node48：查找已经比较贵了。key不再直接存放了，用256元素的数组它可以直接用键字节索引。如果一个节点有17到48个子指针，这个数组将索引存储到第二个数组中，该数组最多包含48个指针。这比256个8byte指针节省空间，因为索引只需要6bit。(256 * 6bit + 48 * 8byte)
这里直接有长度256的key数组，它的位置就代表key的值，里面存的是它在指针数组的偏移量，因为指针数组长度48，可以用6bit表示，节省空间

Node256：只有一个数组，里面直接存的是孩子指针。(256*8byte)

每个节点还有一个固定大小的头文件,存节点类型、孩子的个数还有压缩路径

叶子节点的数据结构

假设是唯一key(非唯一 key可以加一个tuple id)
值的存储方式

• 单值叶子：用额外的叶子节点类型存一个值
• 多值叶子：用前面的中间节点存，只不过把里面的指针存成值
• 指针/值结合：如果值能放到指针里，不需要单独的节点类型；内部节点存指针的地方既可以存指针也可以存值。可以用额外的1bit来区分指针和值。

单值叶子最常用，因为它允许key和变长的值存在一个节点中。但是它增加了树的高度，查找时需要额外的指针遍历；多值叶子需要key有相同的长度；指针/值结合高效，并且可以存变长的key。

内部节点的压缩

lazy expansion：内部节点只有需要分成两个以上叶子节点时才会创建。像图中FOO，只有另一个以F为前缀的节点插入进来才会创建F节点。这个优化需要key存在叶子中或者能从数据库中检索。

路径压缩：在只有一个孩子时移除所有的内部节点，图中的A会被移除。两种方法

• 悲观：在每个内部节点中都有一个变长的Partial key vector。包含的是所有被移除的单路的节点。通过查找这个vector来进行比较在处理到下一个孩子节点前。
• 乐观：只存前面的单路节点的个数。查找时关键字跳过这几个字符继续进行比较。在最后到叶子节点时需要再次比较来防止错误。

乐观和悲观方法都可以保证内部节点只有一个孩子。乐观方法对于长字符串更有利但是需要额外的一次检查。悲观方法需要更多的空间，而且不同的节点大小会增加内存的碎片化。这里用的两种混合方式，会存一个定长的如8byte，当存的单路节点超过了，用乐观方法。
路径压缩和lazy expansion，前者针对中间节点只有一个内部节点孩子的情况，后者针对只有一个叶子节点孩子的情况。

算法

查找：需要注意lazy expansion和path compression
插入：简单情况下插入到一个叶子节点，如果它满了需要把它升级。如果是lazy expansion的情况，发现了一个叶子节点，这个时候需要把它变成一个中间节点和叶子节点。
批量加载：在一个已经存在的关系上加速构建索引：使用每个键的第一个字节，将键/值对以基数划分为256个分区，并创建适当类型的内部节点。在返回内部节点之前，通过使用每个键的下一个字节递归地对每个分区应用大容量加载过程来创建其子节点。
删除：删除与插入是对称的 如果当前节点只有一个孩子，用它的孩子节点取代，根据path compression进行调整。

空间消耗

稠密的数据无需优化也有很好的空间利用率，但是稀疏的数据会导致一些节点包含了大多空指针，其他节点很稠密。
adaptive nodes解决了这个问题，保证key的任何分布通过局部优化都能紧密存储。
最坏的情况，每个key都用多个adaptive nodes， lazy expansion和path compression。

构建二进制可比关键字

radix中的key是词典按位排序的。这对于ASCII编码的字符串是很好用的，但是对于不符合大多数数据类型，如负的有符号整型就比一个正整型大。
需要一种转换key的规则。在进行排序和查找前都需要把key先转换为二进制可比的key。
转换函数t，比较函数memcmp

无符号整型：本身已经是二进制可比deletion。只是需要注意机器是先高位后低位还是先低位后高位
有符号整型：有符号补码整型——因为负数需要补码只比价二进制数的话是比正数大的。可以把首位XOR1
下面的不再介绍了。

评估

先用不同的数据类型测试
然后都整合到Hyper中，用TCP-C测试

查找——数据量由少到多，总体介绍性能，然后用performance counter来看周期、指令、Misp.Branches、L3 Hit、L3 Miss更好的理解结果

单线程、多线程(不同步)
Pipeline对多线程的影响很大

Cache的影响——树的结构从Cache受益，因为树上层的节点被频繁访问，一般都会缓存在cache中。
随机查找对与cache是最不利的情况，随着偏斜的增大，ART与哈希表的性能会更好，因为他们比较少，而FAST需要更多的比较，cache受限小了又要受CPU多次比较的影响。
另外除了上面的所有的cache给了一个索引用，更现实的情况是cache中有多个索引和其他数据。模拟这种情况，用round-robin的方式在多个数据结构上查找数据。哈希表受cache影响较小(它无论如何都不能有效利用cache)，树形索引会随cache增大性能提升。

更新——尽管ART随着树的增大需要动态的替换中间节点，仍要比其他数据类型要快。adaptive node需要20%的代价比起只用node256，但是它节省的空间是值得的。
批量插入，此外有序的key能大量提升插入速度。

端到端测试
把这些索引都在hyper数据库中用TCP-C进行了测试

结论

快速且节省空间的内存数据库索引
high fanout、lazy expansion、path compression来降低树的高度
通过动态选择内部节点来解决radix tree的通病最坏情况下的空间消耗

未来的工作：索引上的并发控制与同步
latch-free同步
节点大小相同的节省空间的radix tree（不再是动态变化扇出，而是动态变化用来记录key的bits）

ART的实现 Github
C版本
Java版本 实现的比较完整，包括文中提到的将可以转化为二进制可比