[ICDE'13] The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases 论文阅读

发表于 分类于 阅读次数： 本文字数： 291 阅读时长 ≈ 1 分钟

https://db.in.tum.de/~leis/papers/ART.pdf

#0. 摘要

主存容量的增长使得大多数数据库都能装入内存 (RAM) 中. 对于主存数据库系统而言, 索引结构的性能是一个关键瓶颈. 传统的内存数据结构, 例如平衡二叉搜索树 (BST), 在现代硬件上效率低下, 因为它们没有充分利用 CPU 缓存. 哈希表也常用于主存索引, 虽然速度快, 但仅支持点查询.

为了克服这些不足, 我们提出了 ART, 一种用于高效主存索引的自适应基数树 (trie). 它的查找性能超越了经过高度优化的只读搜索树, 同时还支持非常高效的插入和删除操作. 此外, ART 空间利用率极高, 通过自适应地为内部节点选择紧凑高效的数据结构, 解决了大多数基数树普遍存在的空间占用过高的问题. 尽管 ART 的性能与哈希表相当, 但它以排序顺序维护数据, 这使得它能够执行范围扫描和前缀查找等额外操作.