自适应基数树(ART)

定义

自适应基数树(Adaptive Radix Tree,ART)由 Viktor Leis 等人于 2013 年在 ICDE 会议论文中提出,是面向内存数据库的 256 叉基数树:根据实际子节点数量,内部节点在 Node4、Node16、Node48、Node256 四种布局间动态切换,兼顾空间与速度。

原理

Node4/Node16 用键数组加指针数组线性或 SIMD 查找;Node48 用 256 字节索引映射到最多 48 个指针;Node256 直接用完整指针数组。配合路径压缩(合并单链)与惰性展开(叶子存完整键)进一步降低树高与内存,查找复杂度取决于键长而非数据量。

应用

ART 是 HyPer 内存数据库的主索引结构,DuckDB 也用 ART 实现主键与唯一约束索引;其并发变体(如乐观锁耦合 OLC)被多篇后续研究和系统采用,是现代内存索引研究的代表性成果。

优缺点

优点是缓存友好、空间紧凑、点查询性能可与哈希表竞争且保持键有序;缺点是实现复杂,长公共前缀较少的随机长键场景优势缩小。