什么是 ART ?
ART 是一个能提供高效点的增删查改，以及范围查询的索引结构。是一个有序的映射。名称中的 radix 表示这是一颗用基数来构建的结构，内部数据是有序存储的，所以有高效范围查询的能力。相比于其他常见的基数结构，ART 的空间利用率更高。这得益于它 adaptive 的特性，即能够根据空间使用情况动态地调节节点大小。
基数树
是trie树的一种。这种数据结构所储存的信息并不在某个节点上，而是由一条由根到叶节点的路径所表示（当用作映射的时候通常为键的信息储存在路径上，值的信息存于对应的叶节点）。
Adaptive Node
ART 使用能动态调节大小（自适应 adaptive）的节点作为内部树节点，能够提高内存使用率。DBMS 中常见的有序索引数据结构B-tree或者传统的radix tree因为每个节点的大小是固定的，因此存在空间放大的问题。类似于磁盘或内存页表的大小，节点的大小通常需要取舍，节点太大的话浪费很严重，节点太小路径又很长，影响读写效率。
虽然理论上说能够使用动态数组作为内部节点，但是这样会涉及到频繁的内存分配释放。为了解决这个问题，ART将节点的大小固定为了四种。分别为4、16、48以及256。并且每个节点根据大小，在具体的结构以及行为上会有细微不同
四种节点的具体实现
首先节点类型的变化仅发生在上溢或者下溢时，即可以/需要使用另一种类型的节点来代替。需要注意由于前缀树的特性，一个节点的最大宽度是有限的，因此并不会横向分裂成两个节点。
Node4 与 Node16
Node4 与 Node16 在结构上面是类似的，都是由一对数量相等的数组组成，其中一个存放键，另一个存放指针。
Node48
Node48 与前两种一样也是由两个数组组成，不过存储键的数组有256的容量，可以直接通过下标进行索引。
Node256
Node256与Node48相比其实就是第二个数组的大小也来到了256，键与值有满射的关系，可以省略一次索引。
路径压缩
文中将路径压缩分成了两种情况，分别是 path compression 和 lazy expansion。 path compression 指将只有一个 key 的节点往下合并，直到需要区分多个子节点为止。lazy expansion 表示把一个节点路径上没有分叉的部分折叠起来。
既然路径被压缩，那么在查找的时候也需要在比较 key 时进行相应的处理。文中将处理分为了两类。悲观的方式是节点储存一个长度不定的前缀值，在每次下降地时候使用这个值进行比较。乐观地方式是节点只储存被压缩地前缀地长度，在每次下降过程中直接跳过这个长度的 key 的处理，并在最后达到叶子节点时再比较 key 是否相等。文中的节点将这两种方式组合起来，在下降的时候按照前缀长度进行动态处理。
节点 header
一个节点除了自己的数据域之外，还包含了一些元信息。例如节点的类型，实际容量，压缩的路径（前缀和 / 或前缀的长度）等。在文中，节点有八字节的前缀区域以及四字节的前缀长度域，即上一段提到的悲观与乐观相结合的处理方法。
读写操作
查询
对于 Node4 采用遍历的方法，Node16 使用 SIMD 或者二分来比较当前的 key，Node48 与 Node256 分别只需进行两次 / 一次索引就能对比到前缀进行下降。
一个一般的查询流程为找到对应的节点进行下降或返回完成查找，对于不存在的键或者节点返回空。另外由于 path compression 的存在，可能一次下降会完成多个 bytes 的比较。
而 range scan 可以使用类似深搜的数次查询实现。
插入 / 删除
一般一个 key 的插入或删除可能出现几种特殊情况。发生上溢/下溢时需要进行节点的替换来完成扩/缩容；如果一次扩缩容触发了路径压缩，那么会有内部节点的新增或删除，以及节点元信息里前缀数据的调整。
如果一次扩容的节点是 lazy expansion 的，或者缩容导致节点的实际容量变为1，那么这条路径的长度会发生变化（以插入为例，使用一个新节点替换当前的叶子节点，这个新节点有两个叶子节点，分别为之前的以及新增的，节点的前缀也会变成两个叶子节点的 key 的重合部分）；如果新插入节点的 key 会影响一个节点的前缀，那么也会在该节点上面新增一个 inner 节点，并相应地调节前缀；其他的情况只需要进行简单的插入删除就行了。可以看到，在上述几种情况中，一次增删过程中会受到影响的节点最多仅有两个。
数据表示
为了实现数据有序排列，需要能将数据类型表示成二进制可比较（binary comparable）的形式。
无符号整型天然满足要求，只是需要注意大小端。有符号整型需要做一次异或操作来处理补码表示法。浮点数稍微复杂一些，按照 [ 正，负 ] x [ 规格化、非规格化、NaN、∞、0 ] 分为互不重叠的十类，然后重新给 rank。对于字符串有 Unicode 定义的比较算法。
应用
在本文的 benchmark 中可以看到，当数据的 key 分布比较密集时，ART 有着很优秀的表现。而且除了 range scan 范围读之外，ART 的 bulk load 范围写也有很大的发掘空间。
并发
文章介绍了两种并发方案，分别是 Optimistic Lock Coupling 和 Read-Optimized Write EXclusion (ROWEX)。它们的性能很接近。
Optimistic Lock Coupling
是在传统 Lock Coupling 方案上的一种优化。Lock Coupling 的重点在于一个操作同时最多持有两把锁，是线程同步 B-Tree 的常见做法。并且在 ART 的背景下，一次修改最多只会影响到两个节点，非常适合使用 Lock Coupling 来实现并发。但是 Lock Coupling 因为每次取得一把锁都会修改节点的内容，所以对缓存很不友好，导致其效率低下。在这里采用一种 Optimistic 的做法，即假设冲突很少出现，每次只在读完之后检测版本信息来判断有没有读到过时信息，而非预先上锁来确保互斥。如果检测到了过期信息则进行重试，为了防止饿死可以在若干次重试失败之后进行加锁。
ROWEX
则稍微复杂一点，它要求 writer 通过原子操作来保证 reader 不会出现脏读。这个方法也使用到了锁，不过仅针对 writer 提供互斥性，而读操作是 wait-free 并且与 Optimistic Lock Coupling 不同，是保证成功的。
Bench
在HOT (SIGMOD 2018) 的 appendix A 找到一个比较全面的 Cross Validation。TL; DR. 在数据密集查询比扫描多，写操作比重较多的情况下 ART 有很优秀的表现，纯扫表性能并不比 B-Tree 好。大量密集数据点查表现可以超过 HashTable，不过性能会受到数据分布的影响。
