ART 自适应基数树 — 内存数据库为主索引重新选材

是什么

ART（Adaptive Radix Tree）是 2013 年 Leis、Kemper、Neumann 三人提的内存数据库主索引结构。日常类比：像一本会自己换厚薄的字典——常用字母页用薄目录，冷门字母页用厚正文，整本字典既不胖、查找还快。

传统做法两难：B+ 树这类比较树要按 key 大小逐层比、CPU 缓存装不下时一路慢；哈希表查得飞快但只支持点查，做不了 WHERE id BETWEEN 100 AND 200 这种范围扫描。ART 走第三条路——基数树（trie），按 key 的字节分叉而不比较，速度只看 key 长度 k 不看条目数 n。

老基数树有个老问题：每个内部节点都开 256 个槽位（对应一个字节），大多数槽是空的，空间爆炸。ART 的解法是为每个节点动态选 4 种尺寸的容器，再加 path compression（合并单子节点）和 lazy expansion（截掉通向单叶子的尾巴）。

最终结果是：单线程 lookup 与精心调优的哈希表持平，TPC-C 端到端比红黑树快近 4 倍，而且仍然支持范围扫描和前缀查询——一举打破”有序索引必慢于哈希”的传统取舍。

为什么重要

不理解 ART，下面这些事都没法解释：

为什么 DuckDB / HyPer 这类内存列存数据库选基数树而不是 B+ 树做主键索引
为什么”哈希表更快”是常识，但有序索引仍然需要——范围扫描 / 前缀模糊匹配是 SQL 的基本盘
为什么单纯改 B+ 树缓存友好（CSB+ 树）2000 年那波改造没赢——CPU 分支预测才是真瓶颈
为什么内存便宜不等于”索引随便用”——一个表上可能有 7 个二级索引，每字节都重要
为什么 SIMD 指令在数据库里不只是分析查询的事——主索引的节点内查找也能从 SSE 一次比 16 字节里赚速度

核心要点

ART 的设计思路可以拆成 三层组合拳：

基数树而不是比较树：把 key 当字节序列，每一字节决定走哪个子节点。类比：查电话号码本时按数字位逐位翻页，不像查英文词典那样比较”AAA 大还是 ABA 大”。优点是复杂度 O(k) 与 n 无关，且天然有序、无需 rebalance。
4 种自适应节点：Node4（≤4 子，线性扫）/ Node16（≤16 子，SIMD 一条指令并行比 16 个字节）/ Node48（≤48 子，先查 256 字节索引数组拿下标再查指针）/ Node256（直接 256 指针数组）。类比：抽屉小就用列表抽屉、抽屉中等用旋转架、抽屉满了直接铺货架。容量扩张就升级、删除变稀就降级。
两个折叠技巧：path compression 把”只有一个子节点的链”合并成一条压缩前缀；lazy expansion 把”只通向一个叶子”的尾巴整段截掉。这两招让 worst-case 空间被压到 ≤52 字节/key，常见场景只要 8.1 字节/key。

这三层组合拳的设计目标是同时优化”时间”和”空间”两个轴，而不是像传统 trie 那样只能在 fanout 上做单维取舍。

实践案例

案例 1：4 种节点是怎么”逐字节查找”的

存了三个 key："ART"、"AND"、"ANY"。基数树按字节分叉：

根节点（Node4）
  字节 'A' → 中间节点（Node4）
              字节 'N' → 中间节点（Node4）
                          字节 'D' → 叶 "AND"
                          字节 'Y' → 叶 "ANY"
              字节 'R' → 中间节点
                          字节 'T' → 叶 "ART"

逐部分解释：

每个节点不存完整 key，只存”下一个字节 → 子指针”
查 "ART" 的过程：根→看 A→看 R→看 T→命中
完全没比较，只是按字节当数组下标取
Node4 内部是两个长度 4 的数组（keys、children），并排存所以好搜
Node16 用一条 SSE 指令 _mm_cmpeq_epi8 一次比 16 个字节，再用 ctz（count trailing zero）拿到匹配位置——比二分搜索快几倍
4 种节点的内存布局差异（论文 Table I）：Node4 占 52 字节、Node16 占 160 字节、Node48 占 656 字节、Node256 占 2064 字节
当一个 Node16 装满第 17 个孩子时，会原地分配一个 Node48 把内容拷过去；删除变稀也对称地降级

案例 2：path compression 怎么省一层

如果只存了一条 "ART"，朴素基数树会建 3 层（A、R、T 各一个内部节点）。但中间两层都只有一个子节点，没必要分开存：

# 朴素 trie（3 层）
root → 'A' → node → 'R' → node → 'T' → leaf

# 加 path compression（折成 1 层）
root → prefix="ART" → leaf

ART 的做法是在节点头部存 8 字节的 compressed path，超长才退化到 optimistic 模式（叶子处再校验整 key）。这一招让长字符串 key 不会让树高变成 key 长度。

论文里给的 TPC-C 实测：customer 表的复合索引 key 是 40 字节，朴素 trie 的树高是 40，加上 path compression + lazy expansion 后平均高度只有 8.1——10 倍的查找加速直接来自这两个折叠技巧。

案例 3：binary-comparable key 怎么让 signed int / float 仍能 range scan

基数树按字节字典序排，但有个问题——负数补码字典序大于正数（-1 的字节表示是 FFFF...），直接拿原始字节当 key 会让 -1 > 100 这种荒谬结论出现。ART 给每种类型一个转换：

// signed int 32 位：翻最高位
uint32_t encode(int32_t x) {
    return x ^ 0x80000000;
}
// 这样 INT_MIN 编码成 0、INT_MAX 编码成 0xFFFFFFFF，字典序正确

float / 字符串 / NULL / 复合 key 各有一套规则，但思路都是”把领域值映射到一段字节串，使得字节比较结果 = 领域比较结果”。这个概念叫 binary-comparable key。

float 的转换更曲折：先按符号位、是否 normalized、是否 NaN 分 10 类算 rank，再像 unsigned int 一样存。复合 key 就更直接——把每个字段独立转换后顺序拼起来即可。

踩过的坑

把 ART 当无脑替换 B+ 树：当 key 极短（如 32 位 dense int）且只做点查时，哈希表仍然更快；ART 的优势在于”同时要范围扫描 + 紧凑空间”。点查为主、空间不敏感的场景换 ART 收益甚微。
直接拿 signed int / float 的字节当 key：负数补码字典序大于正数，必须做 binary-comparable 转换，否则 range scan 顺序全错；调试时 WHERE x BETWEEN -10 AND 10 会返回奇怪的结果。
实现节点类型转换时省略缩节点逻辑：只升不降会让删除后空间不回收，长跑会越来越胖；论文规定 underfull 时必须降级到更小节点类型。
path compression 用 pessimistic 存全前缀向量但不限长度：会让节点变长引发内存碎片；论文做法是固定 8 字节，超长才退化到 optimistic（叶子处校验整 key）。

适用 vs 不适用场景

适用：

内存数据库的主键 / 二级索引（HyPer / DuckDB / Umbra 默认）
同时需要点查 + 范围扫描 + 前缀匹配的场景
key 分布不均匀（dense 与 sparse 混合），传统固定 fanout 的 trie 会浪费空间
TPC-C / OLTP 这类”点查多、写也多”的工作负载
字符串 / 复合 key 占多数的索引——path compression 收益最大

不适用：

纯磁盘 / SSD 数据库——数据不在 RAM 里时 B+ 树的块批量读更划算（b-tree-1972 / comer-1979-btree）
写多远多于读、不需要有序的场景——LSM Tree 更合适（lsm-tree-1996 / rocksdb-lsm）
只做点查的 KV 缓存——哈希表更直接
高并发写入未做并发改造的原版 ART——2013 年原论文不含并发原语，需要后续 ROWEX 等扩展
key 极短且全 dense（如 1..n 整数）——朴素哈希表或紧凑数组反而更快

历史小故事（可跳过）

1968 年：Morrison 提出 PATRICIA trie，第一次把 path compression 引入 trie 用于字符串检索。
1986 年：Lehman & Carey 在 VLDB 提出 T-Tree 给内存数据库用，主导了 20 年；本质仍是平衡二叉树，CPU 缓存时代被淘汰。
2000 年：Rao & Ross 提出 CSB+ 树，让 B+ 树缓存友好，但更新代价更大；只是给老结构打补丁。
2010 年：Kim 等人的 FAST 用 SIMD + 缓存行分块把只读搜索树做到极致，但不支持增量更新——OLTP 没法用。
2013 年：Leis 等人把”adaptive node + path compression + binary-comparable key”三件套打包，第一次让一个有序索引在内存场景同时打过 FAST 和哈希表。
2016 年起：Leis 又出 ROWEX 论文给 ART 加 latch-free 并发原语；DuckDB 把 ART 设为默认主键索引；LeanStore 等新型缓冲池系统也在用。

学到什么

基础数据结构选型不是终点——CPU 架构变了（cache 层级 / 分支预测），上层数据结构就得跟着重选；T-Tree → CSB+ → ART 这条线就是不断”对齐硬件”的演化
adaptive 是通用药——不只 ART，Judy 数组也用同样思路；当一个参数（fanout / span）需要在不同情况下取不同值时，让节点自己变身比全局调参更好
实测胜过直觉：哈希表在内存里仍然比有序结构快，但”快 30%“和”丢失一半功能”换不换值得，是工程取舍
小论文也能改写工业：ART 论文 12 页，今天 DuckDB / HyPer / LeanStore 都依赖它，证明经典 system 论文不必很厚
设计目标的清单决定结构选型：先把”要点查 / 要范围 / 要省空间 / 要支持更新”列清楚，再选结构；ART 之前没人把这四个目标同时按住，所以才有了它的位置

关联

b-tree-1972 —— B 树是磁盘场景的有序索引；ART 是 RAM 时代的对应物
comer-1979-btree —— B+ 树普及综述；ART 论文里 CSB+ 树是主要 baseline 之一
lsm-tree-1996 —— 写优化的另一种思路；与 ART 的”读+写都好”形成对比
rocksdb-lsm —— LSM 工程化代表；ART 在内存层（memtable）也常被用到
skip-list-1990 —— 另一种”无需 rebalance”的有序结构；与 ART 都是 B+ 树的替代候选
hindley-milner —— 同为 ICDE / POPL 这种”小论文改写工业”代表，可对照设计思路的简洁与影响力

反向链接

b-tree-1972 —— B-Tree 1972 — 磁盘友好的索引结构
comer-1979-btree —— Comer 1979 — B-Tree 综述：为什么这棵树到处都有
hindley-milner —— Hindley-Milner — 编译器自己猜变量类型
lsm-tree-1996 —— LSM-Tree 1996 — 写优化存储引擎
memcached-fb-2013 —— Scaling Memcache at Facebook — 万台缓存怎么不被踩塌
rocksdb-lsm —— LSM-tree 与 RocksDB — 把所有写都变成顺序写
skip-list-1990 —— Skip List — 用抛硬币代替平衡树