一、引言

在操作系统、网络协议栈、数据库和高性能存储系统中，经常需要根据某个键快速查找对应的数据。例如：

• 根据字符串查找对应的配置项。

• 根据 IP 地址查找路由表中的匹配项。

• 根据页索引查找 Linux 内核中的 page cache。

• 根据整数索引查找内核对象。

• 根据文件偏移或对象编号定位特定资源。

常见的解决方案包括哈希表、红黑树、普通 Trie 和 Radix Tree 等。

哈希表具有优秀的平均精确查找性能，但不擅长前缀查询和有序遍历；红黑树能够支持有序查找，但通常需要 (O(\log N)) 次树节点访问；普通 Trie 可以利用键的公共前缀，但可能产生大量只包含一个子节点的中间节点。

Radix Tree 通过利用键的数字或字符表示组织数据，并在适当的实现中压缩连续路径，兼顾查找效率、空间利用率和前缀查询能力，因此被广泛应用于索引结构、路由算法和操作系统内核。

需要注意，Radix Tree 在不同技术资料中有时是一个广义术语，有时专指压缩前缀树。Linux 内核历史上的 Radix Tree 则主要是按整数索引组织对象的多位树形结构，与字符串压缩树并不完全相同。

本文将从基本原理出发，介绍 Radix Tree 的数据结构、核心算法、C 语言实现、优缺点，以及它在 Linux 内核中的应用。

二、Radix Tree 的基本原理

2.1 什么是 Radix Tree？

Radix Tree 是一种根据键的字符、字节或二进制位组织数据的树形数据结构。

Radix 是数学中的基数，表示一个数制的基数。例如：

• 二进制的基数为 2。

• 十进制的基数为 10。

• 十六进制的基数为 16。

在数据结构中，Radix Tree 可以根据键的位或字符进行分支。对于固定宽度的整数键，可以将键划分成多个 bit 组，每一层根据其中一组 bit 选择子节点；对于字符串键，则可以根据字符序列构建前缀树。

Radix Tree 的一个重要变体是压缩 Radix Tree，也称为压缩 Trie。它将连续的单分支路径合并，减少中间节点的数量。

2.2 从普通 Trie 理解 Radix Tree

假设需要存储以下字符串：

• cat

• car

• cart

• dog

普通 Trie 通常以单个字符作为边标签。相同前缀的字符串共享路径。

例如，cat、car和cart都以ca开头，因此可以共享c和a对应的路径。

这种结构具有良好的前缀查询能力，但对于长字符串而言，如果大量路径只有一个子节点，就会产生很多不必要的中间节点。

例如，如果存储以下键：

• network_device_driver

• network_device_status

• network_device_config

普通 Trie 可能需要为公共前缀network_device_中的每个字符建立一个节点。

如果树中的大量节点只有一个孩子，那么节点分配、指针维护和内存访问都会产生额外开销。

2.3 路径压缩

压缩 Radix Tree 会将连续的单分支路径合并成一个包含多个字符的边。

例如，原先的路径：

n → e → t → w → o → r → k → _ → d → e → v → i → c → e → _

可以压缩成一条标签为network_device_的边。

其逻辑结构可以表示为：

root | | "network_device_" | +---- "driver" [terminal] | +---- "status" [terminal] | +---- "config" [terminal]

其中，terminal表示该节点对应一个完整键。

这种压缩方式减少了树中间节点的数量，同时保留公共前缀共享的优势。

需要注意，压缩 Radix Tree 并不是简单地把整个公共前缀复制到每个子节点中，而是通过共享路径和合并单分支边，减少重复存储。

2.4 Radix Tree 与 Trie 的关系

Trie 是按照键的序列组织数据的一类树结构。Radix Tree 在很多语境下可以看作 Trie 的一种变体，而压缩 Radix Tree 的主要特点是路径压缩。

两者的区别如下：

严格来说，Radix Tree 的具体定义会因实现而异。理解其压缩路径的思想，比单纯记忆名称更重要。

三、Radix Tree 的主要类型

3.1 普通 Trie

普通 Trie 逐字符或逐位组织键，适合字符串字典、关键字检索和前缀匹配。

优点是结构直观，插入和查找比较容易实现。

缺点是当键较长且存在大量单分支路径时，会产生大量中间节点。

3.2 压缩 Radix Tree

压缩 Radix Tree 合并连续的单分支路径，减少节点数量。

它适合字符串索引、前缀查询和某些路由表实现。

其主要挑战是插入时需要处理公共前缀分裂，删除时需要进行节点合并。

3.3 Binary Radix Tree

Binary Radix Tree 根据键的二进制位进行分支。

最简单的二进制树每层处理一个 bit，分为 0 和 1 两个分支。

对于固定宽度的整数键，树的最大深度与键的位宽有关。例如，64 位键的二进制树最多处理 64 层。

二进制 Radix Tree 适合位前缀索引、某些路由算法以及整数键组织。

3.4 多位 Radix Tree

多位 Radix Tree 每层不只处理一个 bit，而是一次处理多个 bit。

假设每层处理 4 bit，则每层最多有 (2^4=16) 个分支。

如果处理 6 bit，则每层最多有 (2^6=64) 个分支。

这种方式可以降低树的高度，减少查找过程中的层数，但每个节点可能需要更多指针或槽位。

Linux 内核传统 Radix Tree 就属于以整数索引为核心的多位树形索引结构，而不是前面介绍的字符串压缩树。

3.5 Adaptive Radix Tree（ART）

Adaptive Radix Tree 是一种针对内存数据库和高性能索引优化的 Radix Tree。

它会根据节点实际拥有的子节点数量，选择不同的节点布局，以减少稀疏节点的内存浪费，并改善缓存局部性。

ART 的设计重点是高性能内存索引，与 Linux 内核传统 Radix Tree 的实现目标并不完全相同。

四、Radix Tree 的核心操作

Radix Tree 的核心操作包括查找、插入和删除。

4.1 查找操作

查找时，从根节点开始，根据待查找键的内容选择对应子节点。

对于压缩字符串 Radix Tree，查找过程如下：

1. 从根节点开始。

2. 根据剩余键的首字符找到候选子边。

3. 比较剩余键与该边标签。

4. 如果整个边标签匹配，则跳过对应长度的字符并进入下一级节点。

5. 如果标签只匹配了一部分，或者出现字符不匹配，则查找失败。

6. 当所有待查找字符消耗完毕时，检查当前节点是否标记为完整键。

例如，查找foobaz：

root | | "foo" | +---- "bar" | +---- "baz"

查找时先匹配foo，再匹配baz，最终检查目标节点的终点标记。

一个重要细节是：某个节点可以既表示完整键，又包含子节点。例如，foo和foobar可以同时存在。因此，不能通过“节点是否有孩子”判断键是否存在。

4.2 插入操作

插入操作需要根据新键与现有边标签的公共前缀关系，决定创建节点还是分裂边。

主要有三种情况。

情况一：不存在匹配的子边。

直接创建一个新节点，将剩余键作为边标签，并将新节点标记为完整键。

情况二：新键完整匹配现有边。

沿现有路径继续向下，直到处理完新键。如果最终到达的节点已存在，就更新其值；如果该节点原先不是完整键，则将它标记为完整键。

情况三：只匹配了部分边标签。

需要将现有边分裂成公共前缀和不同的后缀。

例如，已有键foobar，现在插入foobaz。

原结构：

root | | "foobar" | +---- [value = 1]

两个键的公共前缀为fooba。插入后可以变成：

root | | "fooba" | +---- "r" [value = 1] | +---- "z" [value = 2]

如果插入的是foo，则公共前缀本身就构成一个完整键：

root | | "foo" [terminal] | +---- "bar" [terminal]

因此，插入操作的关键是计算公共前缀长度，并正确维护父节点、子节点、兄弟节点及完整键标记。

4.3 删除操作

删除操作首先查找目标键。

如果键不存在，返回失败；如果存在，则取消对应节点的完整键标记。

之后需要检查树的结构：

• 如果节点不是完整键且没有孩子，可以删除该节点。

• 如果节点不是完整键且只有一个孩子，可以将该节点与孩子合并。

• 如果节点仍然是完整键，或者有多个孩子，则通常保留该节点。

例如，原先存在foo和foobar：

root | | "foo" [terminal] | +---- "bar" [terminal]

删除foobar后：

root | | "foo" [terminal]

此时foo仍然有效，不应被删除。

删除操作的主要难点是从底向上恢复路径压缩性质，并且不能误删其他键共享的路径。

五、Radix Tree 的时间复杂度

设：

• (N) 为键的数量。

• (L) 为字符串键的长度。

• (W) 为整数键的位宽。

• (b) 为多位 Radix Tree 每层处理的 bit 数。

对于常见的压缩字符串 Radix Tree：

这些复杂度通常假设子边查找的代价受控。例如，如果子节点使用线性链表搜索，那么每个节点的孩子数也会影响实际时间。

对于固定宽度整数键，多位 Radix Tree 的最大层数通常不超过：

例如，对于 64 位键，每层处理 6 bit 时，最大层数约为 11 层。

这里的层数不一定等于实际分配的节点数量。稀疏索引通常只分配需要的节点，而具体空间开销取决于实现。

六、Radix Tree 的优势

6.1 查找性能稳定

Radix Tree 根据键的字符、字节或位序列逐层查找，不需要像普通二叉搜索树那样依赖键之间的比较和树的平衡。

对于固定宽度整数键，最大查找深度通常有明确上限。

对于字符串键，查找复杂度主要取决于键长度，而不是简单地取决于键的总数量。

6.2 可以利用公共前缀节省空间

压缩 Radix Tree 能够将连续的单分支路径合并，减少节点数量。

如果很多键共享较长前缀，这种方式通常比较有优势。

不过，实际内存占用还取决于节点结构、标签分配方式、指针开销和键的分布，并不能保证任何场景下都比哈希表省内存。

6.3 前缀查询能力强

Radix Tree 的路径与键的前缀直接对应，因此可以快速定位指定前缀，再遍历对应子树。

这对于字符串索引、字典、路由表和前缀匹配很有价值。

6.4 支持有序遍历

如果子节点按字符、位组或索引顺序组织，可以按键顺序遍历数据。

与通常不保证顺序的哈希表相比，这对范围查询和枚举键值具有优势。

6.5 适合稀疏索引

对于整数索引，如果只有少量位置实际存储了对象，按需创建索引路径可以避免预分配一个巨大的连续数组。

这是 Radix Tree 在内核索引管理中非常有价值的特性。

七、Radix Tree 的劣势

7.1 插入和删除实现复杂

边分裂、节点合并、父子指针维护和终点标记都需要严格处理。

如果插入时没有正确保留原来的兄弟节点指针，就可能导致树结构损坏或丢失其他分支。

7.2 内存分配与释放复杂

每个节点可能需要单独分配，边标签也可能需要动态分配。

因此，需要处理内存分配失败、节点释放、重复释放和错误路径等问题。

内核代码还需要考虑分配标志、锁、RCU 和对象生命周期。

7.3 指针访问可能影响缓存局部性

如果每个节点分散在不同内存位置，查找可能产生大量缓存未命中。

紧凑节点布局、自适应节点、内存池和多位分支可以改善部分场景的性能。

7.4 不一定适合单纯的精确查找

如果应用只需要根据键进行精确查找，哈希表往往是更简单的选择，平均查找时间也可能更短。

因此，应根据是否需要前缀查询、有序遍历、稀疏索引，以及实际的内存和延迟要求选择数据结构。

八、Radix Tree 与其他数据结构的比较

这里需要注意，大 O 复杂度并不能完全代表实际性能。缓存命中率、键长度、分支数量、节点布局和分配策略都会显著影响结果。

九、C 语言实现：压缩 Radix Tree

下面实现一个简化的压缩 Radix Tree，用于存储字符串到整数值的映射。

该实现使用以下设计：

• 每个节点保存一段边标签。

• 每个节点通过孩子指针和兄弟指针连接。

• terminal表示当前节点是否对应完整键。

• value保存对应的整数值。

• 支持插入、查找、删除和整棵树的释放。

为了便于理解，示例使用动态分配的字符串标签和孩子兄弟链表。它适合学习核心算法，但不是高性能或并发安全的生产级实现。

9.1 数据结构定义

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef struct RadixNode { char *label; bool terminal; int value; struct RadixNode *children; struct RadixNode *sibling; } RadixNode;

其中，label表示从父节点到当前节点的边标签。根节点的标签为空字符串。

children指向第一个孩子，sibling指向下一个兄弟节点。

这种结构不需要为每个节点固定分配 128 或 256 个孩子指针，但查找孩子时需要遍历兄弟链表。

9.2 创建节点与计算公共前缀

static char *dup_n(const char *s, size_t n) { char *p = malloc(n + 1); if (!p) return NULL; memcpy(p, s, n); p[n] = '\0'; return p; } static size_t common_prefix(const char *a, const char *b) { size_t i = 0; while (a[i] && b[i] && a[i] == b[i]) i++; return i; } static RadixNode *new_node(const char *label, size_t len) { RadixNode *n = calloc(1, sizeof(*n)); if (!n) return NULL; n->label = dup_n(label, len); if (!n->label) { free(n); return NULL; } return n; } static RadixNode *radix_create(void) { return new_node("", 0); }

common_prefix()是压缩 Radix Tree 的关键辅助函数。插入操作通过它确定是否需要分裂边。

9.3 查找孩子

static RadixNode *find_child(RadixNode *n, char first) { for (RadixNode *c = n->children; c; c = c->sibling) { if (c->label[0] == first) return c; } return NULL; }

由于每条非根边的标签不能为空，可以通过首字符找到候选边。

如果需要提高分支查找性能，可以改用排序数组、哈希映射或固定扇出节点。

9.4 查找键

static bool radix_lookup(RadixNode *root, const char *key, int *out) { if (!root || !key || !*key) return false; RadixNode *cur = root; const char *rem = key; while (*rem) { RadixNode *child = find_child(cur, *rem); if (!child) return false; size_t len = strlen(child->label); if (strncmp(rem, child->label, len) != 0) return false; rem += len; cur = child; } if (!cur->terminal) return false; if (out) *out = cur->value; return true; }

查找操作逐段比较标签。如果键在边标签中途结束，或者边标签与键不匹配，就返回失败。

当剩余键为空时，仍然需要检查terminal，因为一个节点可能只是某个更长键的公共前缀。

9.5 插入键

插入操作需要区分三种情况：

1. 没有匹配的孩子：创建新叶子。

2. 当前边完全匹配：沿路径继续。

3. 当前边只部分匹配：分裂边，将公共前缀保存到中间节点，再挂接旧后缀和新后缀。

例如，插入foobar后再插入foobaz，需要将公共前缀fooba独立出来。

为了保证数据结构的可靠性，实际代码应先完成新节点和新标签的分配，再提交指针修改；如果分配失败，必须保证原树仍然有效。

以下是插入操作的关键逻辑示意：

size_t k = common_prefix(child->label, rem); size_t child_len = strlen(child->label); if (k == child_len) { rem += k; cur = child; /* 继续向下查找 */ } else { /* 创建公共前缀中间节点 */ /* 为旧后缀和新后缀分配节点 */ /* 重新连接父节点与孩子链表 */ /* 设置 terminal 和 value */ }

这部分看似简单，但最容易出现链表连接错误。例如，在修改child->sibling前没有保存旧兄弟指针，就可能丢失其他分支。

因此，编写完整实现时，应把边分裂当成一个结构更新事务：先准备所有内存，再一次性更新链接。

9.6 删除键

删除操作先定位目标节点并取消terminal标记，然后根据节点状态进行清理：

• 非终点且无孩子：删除节点。

• 非终点且只有一个孩子：合并标签。

• 仍然是终点或拥有多个孩子：保留节点。

例如，删除foobar后，如果foo仍然是一个完整键，就不能把foo对应的节点一起删除。

9.7 释放整棵树

static void free_tree(RadixNode *n) { if (!n) return; RadixNode *child = n->children; while (child) { RadixNode *next = child->sibling; free_tree(child); child = next; } free(n->label); free(n); }

在释放孩子时，先保存兄弟指针，再递归释放当前孩子。这是因为当前孩子释放后，不能继续访问它的成员。

对于生产级实现，还需要考虑递归深度、分配失败后的结构一致性，以及并发读者可能仍然访问节点的情况。

十、Linux 内核中的 Radix Tree 与 XArray

10.1 为什么内核需要索引树？

Linux 内核中有大量需要根据整数索引查找对象的场景。

例如，page cache 需要根据文件页索引找到对应的缓存页。文件可能很大，但某一时刻只有部分页驻留在内存中。

如果直接分配一个覆盖全部页索引的巨大数组，会浪费大量空间。

Radix Tree 可以按需分配索引路径，使稀疏索引更加经济。

概念上可以表示为：

page index | v Radix Tree / XArray | +---- index 0 ---> page 0 +---- index 1 ---> page 1 +---- index 2 ---> page 2 +---- index 100 ---> page 100

实际内核实现会根据索引位组逐层选择节点，并使用专门的节点布局、标记和并发访问机制。

10.2 传统 Radix Tree 与 XArray

Linux 内核历史上提供了 Radix Tree API，用于整数索引对象的查找、插入、删除和遍历。

现代内核中，许多相关场景已经转向 XArray。XArray 是面向整数索引的通用数据结构，支持对象查找、存储、删除、遍历和标记等操作。它与字符串压缩 Radix Tree 的实现方式并不相同。

例如，概念性的 XArray 使用方式如下：

#include <linux/xarray.h> DEFINE_XARRAY(my_xa); /* 保存索引 10 对应的对象 */ void *old = xa_store(&my_xa, 10, obj, GFP_KERNEL); /* 查找对象 */ void *p = xa_load(&my_xa, 10); /* 删除索引 */ xa_erase(&my_xa, 10);

实际内核代码必须检查xa_store()的错误返回，处理对象生命周期，并根据调用上下文正确选择锁、RCU 和内存分配策略。示例中的变量、对象定义和错误处理仅用于说明接口概念。

10.3 为什么内核不能直接使用普通用户态实现？

内核中的数据结构不仅需要保证逻辑正确，还必须满足并发、安全和执行上下文约束。

主要包括：

内存分配。内核不能直接使用用户态的malloc()，而需要根据上下文选择适当的内核分配接口和分配标志。

并发访问。多个 CPU 可能同时访问或更新索引结构，必须保证节点和指针的状态一致。

对象生命周期。即使查找操作获得了一个指针，也不意味着该对象在后续使用期间一定不会被释放。

RCU。对适合 RCU 的读多写少场景，可以通过延迟释放机制保护读者正在访问的数据。但 RCU 并不自动解决所有写操作同步问题，也不能替代对象生命周期设计。

因此，用户态的压缩 Radix Tree 适合学习路径压缩算法，而 Linux 内核的 Radix Tree/XArray 还需要结合内核内存管理、并发控制和对象生命周期进行理解。

十一、Radix Tree 的典型应用场景

11.1 IP 路由表

IP 路由查找经常需要最长前缀匹配。例如，多个网络前缀可能同时匹配某个目标地址，系统需要选择最具体的有效前缀。

Radix Tree 的前缀结构天然适合这种需求。具体的路由实现也可能采用压缩 Trie、LC-trie 或其他经过优化的结构。

11.2 字符串字典和配置索引

当大量字符串共享前缀时，压缩 Radix Tree 可以减少重复路径，并支持按前缀枚举键。

11.3 数据库内存索引

在内存数据库中，Radix Tree 和 ART 可以用于字符串键或二进制键索引。它们的节点布局可以针对缓存局部性和分支数量进行优化。

11.4 Linux page cache 和整数索引

内核需要根据文件页索引或对象编号查找稀疏数据。传统 Radix Tree 和现代 XArray 都与这类索引需求密切相关。

十二、如何选择 Radix Tree？

选择数据结构时，应该先明确系统真正需要什么能力。

如果只需要精确查找，而且不需要有序遍历或前缀匹配，哈希表往往更合适。

如果需要维护有序键、支持范围查询，红黑树或其他有序树通常更容易表达需求。

如果需要字符串前缀匹配，普通 Trie 或压缩 Radix Tree 更自然。

如果需要根据整数索引高效管理稀疏对象，则应考虑多位 Radix Tree 或 XArray。

如果追求高性能内存字符串索引，可以进一步研究 ART 及其自适应节点布局。

最终选择应通过实际键分布、查询比例、更新频率、内存占用和缓存行为进行验证，而不是仅凭理论复杂度决定。

十三、总结

Radix Tree 是一种根据键的字符、字节或位序列组织数据的树形结构。压缩 Radix Tree 通过合并连续的单分支路径减少节点数量，在精确查找、前缀查询和空间利用方面具有优势。

它的主要代价是插入和删除更加复杂，需要处理边分裂、路径压缩、内存管理以及结构一致性。

理解 Radix Tree 时，最重要的是掌握以下几个方面：

1. 普通 Trie 与压缩 Radix Tree 的区别。

2. 如何根据公共前缀执行边分裂。

3. 为什么删除操作需要从底向上压缩路径。

4. 如何正确维护完整键标记和父子关系。

5. 如何分析键长度、索引位宽、分支数量和内存布局对性能的影响。

6. 如何区分字符串压缩 Radix Tree 与 Linux 内核历史上的整数索引 Radix Tree/XArray。

对于 Linux 内核开发人员而言，学习压缩 Radix Tree 有助于理解树形索引的设计思想，而进一步研究 XArray、page cache、RCU 和内存管理，则有助于将数据结构知识与实际内核实现联系起来。