Skip to content

Latest commit

 

History

History
152 lines (98 loc) · 8.03 KB

note.md

File metadata and controls

152 lines (98 loc) · 8.03 KB

https://zhuanlan.zhihu.com/p/271739790 ART 的全称是 Adaptive Radix Tree，中文是自适应基数树，实际上就是基数树的升级版。

https://github.com/plar/go-adaptive-radix-tree

Adaptive Radix Tree（简称 ART） 是一种面向内存、用于索引（Indexing）和快速查询的数据结构。它在保留前缀树（Trie）快速精确匹配优势的同时，通过“自适应”地调整节点大小，来显著减少内存占用并提高查询效率。下面将从原理、节点结构、核心算法与优势等多个方面，对 ART 进行详细介绍。

1. 背景与动机

1.1 前缀树（Trie）的特点

  1. 前缀匹配
    Trie 通常用于存储字符串或其他可拆分为“字符”（或字节）序列的 key，其核心思想是根据 key 的每个字符层层下钻进行匹配。
  2. 查询复杂度
    在最理想情况下（没有过度冲突或过度分支时），Trie 的查找复杂度可以与 key 的长度呈线性关系，即 O(k)，其中 k 是 key 的长度。
  3. 空间占用
    一般的 Trie 会为每一层字符序列中的所有可能分支开辟一个数组，比如字符集（ASCII/Unicode）可能会比较大，这就会造成大量不必要的内存浪费，尤其在节点分支很稀疏的情况下。

1.2 传统 Trie 的不足

  • 内存浪费：Trie 在层层下钻时，若某一层节点只有几个有效分支，而字符可能的范围却很大（例如 256 个可能的字节值），则会产生大量空闲指针数组，造成内存浪费。
  • 缓存命中率低：当节点规模过大时，会导致访问一个节点需要大量随机访存，降低 CPU 缓存命中率。

1.3 ART 的设计思路

ART 针对前缀树节点开辟空间过大的问题，提出了**自适应节点（Adaptive Node）**的思想：根据节点分支数量的多少，以不同大小的“容器”来存储分支，从而兼顾查询性能和空间效率。

2. ART 的节点结构

ART 中常见的节点类型（针对 8 位字符，或说字节级别）通常有四种，分别被称为 N4, N16, N48, N256，它们的名称含义与分支数量紧密相关：

  1. Node 4 (N4)

    • 最多存储 4 个分支。
    • 若某一节点分支只有 1~4 个时使用。
    • 常见结构：
      • 一个 4 元素的数组，用于存储实际字符（key 的当前字节）
      • 一个指针数组（大小也为 4），存放指向子节点的指针

  2. Node 16 (N16)

    • 最多存储 16 个分支。
    • 若分支数超过 4 个时，就会从 N4 扩容到 N16；如果分支数降至 3 或更少，就会缩容到 N4。
    • 常见结构：
      • 一个 16 元素的数组，用于存储分支字符
      • 一个指针数组（大小也为 16），存放子节点指针

  3. Node 48 (N48)

    • 最多存储 48 个分支。
    • 如果分支数超过 16，则从 N16 扩容到 N48；低于 16 时可缩容到 N16。
    • 与前两种节点的区别：N48 通常会有一个 256 大小的索引数组（或称标记数组），每个索引对应一个可能的字符值（0~255），其中保存一个下标（指向另一个大小为 48 的指针数组的位置）。这种设计可以兼顾查询速度和空间利用率。
    • 这样当插入或查找时，先通过当前字符的值在 256 大小的索引数组里找到是否存在有效分支，如果存在，就到指针数组（大小 48）中找到对应的子节点指针。

  4. Node 256 (N256)

    • 最多存储 256 个分支。
    • 如果分支数量超过 48，则从 N48 扩容到 N256；当分支降到 48 以下时，可以缩容回 N48。
    • N256 节点通常直接包含一个大小为 256 的指针数组，索引对应着每个可能的字符值（0~255）。

由于节点类型可以根据分支数动态变化，这就是“Adaptive（自适应）”的由来。ART 只在需要时才会使用更大容器，从而避免了传统 Trie 所面临的大量稀疏空指针问题。

3. 核心算法流程

3.1 插入（Insert）

  1. 从根节点开始，逐字节（或逐位）地与 key 进行匹配，寻找对应分支。
  2. 如果当前节点类型还能容纳新的分支（例如 N4 只有 3 条分支，还能容纳第 4 条），则直接将新的分支加入。
  3. 如果节点已经存满，则进行“扩容”操作：
    • N4 (\to) N16
    • N16 (\to) N48
    • N48 (\to) N256
  4. 继续向下层节点插入，直到 key 的最后一个字符被插入完毕。

3.2 查询（Search）

  1. 从根节点开始，依次读取 key 的每个字符（或字节）。
  2. 在当前节点的分支容器中查找这个字符：
    • 若能找到对应分支，则顺着该分支指针继续向下；
    • 若没找到（表示不存在该 key），则直接返回查询失败。
  3. 若成功匹配到 key 的最后一个字符，返回查询成功。

3.3 删除（Delete）

  1. 按照查询的方式找到待删除的 key 对应的叶子节点。
  2. 若找不到，则说明该 key 不存在。
  3. 若找到对应节点并进行删除后，若当前节点的分支数量过少，可进行“缩容”操作：
    • N16 (\to) N4
    • N48 (\to) N16
    • N256 (\to) N48
  4. 删除操作完成后，需要注意可能导致父节点分支变得极少，从而继续级联缩容。

4. 关键优化点

  1. 路径压缩（Path Compression）

    • 当某些节点只包含唯一分支时，可以将连续的、没有分叉的路径进行压缩，一次性存储这段前缀，以减少树的深度和访问开销。
    • 这在使用较长字符串作 key 时非常重要。

  2. 局部性与缓存优化

    • ART 的节点大小控制在较为紧凑的范围内，保证节点在 CPU Cache 中能有较高的命中率，提高查询效率。
    • 对于 N48 的索引数组而言，由于其大小为 256，可以通过简单的 byte 索引寻址，减少跳转。

  3. 自适应扩容与缩容

    • 在插入或删除时，ART 会动态切换节点类型，以适应当前分支数量，从而提升空间利用率。

  4. 并发控制（高级实现）

    • 对于实际工程中的并发场景，可以对节点使用乐观并发控制（Optimistic Lock Coupling）或更细粒度的锁分离技术，以实现多线程的高效并发访问。

5. ART 的优势与应用场景

  1. 高效的查询性能

    • 相比于哈希表（Hash Table），ART 保留了 key 的有序信息，可以进行前缀搜索、范围查询等。
    • 相比于 B+Tree 等传统树结构，对于较长的字符串或变长 key，ART 可以更好地利用前缀共享，减少冗余存储。

  2. 更好的内存利用率

    • 自适应节点使得节点不会过度浪费空间，降低了 Trie 普遍存在的稀疏化问题。

  3. 适合多种类型的 key

    • 不仅可以处理字符串，也可以直接将整数（如 64 位整型）视为 8 个字节序列存入 ART，实现快速的按位匹配、前缀搜索等操作。

  4. 在数据库索引中的应用

    • 一些现代数据库（例如内存型数据库）可能使用 ART 替代传统的 B-Tree 作为索引结构，以获得更好的性能。

6. 小结

Adaptive Radix Tree（ART）有效结合了 Trie 的快速按字符（或字节）层次匹配优势，以及自适应节点结构所带来的高空间利用率与高查询效率。它通过在插入或删除时灵活地对节点进行扩容或缩容，避免了传统 Trie 大量空指针占用内存的问题；同时，通过路径压缩和紧凑的节点设计来提升查询性能和缓存利用率。因此，ART 尤其适合在内存数据库以及需要高并发、低延迟的应用场景中使用，逐渐成为一类重要的索引数据结构。

若需要更深入地了解，可以参考以下文献和资料：

  • "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases" (2013) by V. Leis, A. Kemper, T. Neumann
  • 相关开源数据库（如 HyPer, MemSQL 等）的实现细节

通过对 ART 的原理、数据结构、算法、优化策略以及实际应用的学习，可以更好地理解和使用这类高效的内存索引结构。