一、引言在操作系统、网络协议栈、数据库和高性能存储系统中经常需要根据某个键快速查找对应的数据。例如根据字符串查找对应的配置项。根据 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 TreeRadix Tree 是一种根据键的字符、字节或二进制位组织数据的树形数据结构。Radix 是数学中的基数表示一个数制的基数。例如二进制的基数为 2。十进制的基数为 10。十六进制的基数为 16。在数据结构中Radix Tree 可以根据键的位或字符进行分支。对于固定宽度的整数键可以将键划分成多个 bit 组每一层根据其中一组 bit 选择子节点对于字符串键则可以根据字符序列构建前缀树。Radix Tree 的一个重要变体是压缩 Radix Tree也称为压缩 Trie。它将连续的单分支路径合并减少中间节点的数量。2.2 从普通 Trie 理解 Radix Tree假设需要存储以下字符串catcarcartdog普通 Trie 通常以单个字符作为边标签。相同前缀的字符串共享路径。例如cat、car和cart都以ca开头因此可以共享c和a对应的路径。这种结构具有良好的前缀查询能力但对于长字符串而言如果大量路径只有一个子节点就会产生很多不必要的中间节点。例如如果存储以下键network_device_drivernetwork_device_statusnetwork_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 的主要特点是路径压缩。两者的区别如下特性普通 Trie压缩 Radix Tree边标签通常是单个字符或固定宽度的位组可以是多个字符或多个位组单分支路径通常保留多个节点可以合并节点数量可能较多通常较少插入操作相对直观可能需要分裂边删除操作删除节点即可必要时清理路径可能需要合并边前缀查询支持支持严格来说Radix Tree 的具体定义会因实现而异。理解其压缩路径的思想比单纯记忆名称更重要。三、Radix Tree 的主要类型3.1 普通 Trie普通 Trie 逐字符或逐位组织键适合字符串字典、关键字检索和前缀匹配。优点是结构直观插入和查找比较容易实现。缺点是当键较长且存在大量单分支路径时会产生大量中间节点。3.2 压缩 Radix Tree压缩 Radix Tree 合并连续的单分支路径减少节点数量。它适合字符串索引、前缀查询和某些路由表实现。其主要挑战是插入时需要处理公共前缀分裂删除时需要进行节点合并。3.3 Binary Radix TreeBinary Radix Tree 根据键的二进制位进行分支。最简单的二进制树每层处理一个 bit分为 0 和 1 两个分支。对于固定宽度的整数键树的最大深度与键的位宽有关。例如64 位键的二进制树最多处理 64 层。二进制 Radix Tree 适合位前缀索引、某些路由算法以及整数键组织。3.4 多位 Radix Tree多位 Radix Tree 每层不只处理一个 bit而是一次处理多个 bit。假设每层处理 4 bit则每层最多有 (2^416) 个分支。如果处理 6 bit则每层最多有 (2^664) 个分支。这种方式可以降低树的高度减少查找过程中的层数但每个节点可能需要更多指针或槽位。Linux 内核传统 Radix Tree 就属于以整数索引为核心的多位树形索引结构而不是前面介绍的字符串压缩树。3.5 Adaptive Radix TreeARTAdaptive Radix Tree 是一种针对内存数据库和高性能索引优化的 Radix Tree。它会根据节点实际拥有的子节点数量选择不同的节点布局以减少稀疏节点的内存浪费并改善缓存局部性。ART 的设计重点是高性能内存索引与 Linux 内核传统 Radix Tree 的实现目标并不完全相同。四、Radix Tree 的核心操作Radix Tree 的核心操作包括查找、插入和删除。4.1 查找操作查找时从根节点开始根据待查找键的内容选择对应子节点。对于压缩字符串 Radix Tree查找过程如下从根节点开始。根据剩余键的首字符找到候选子边。比较剩余键与该边标签。如果整个边标签匹配则跳过对应长度的字符并进入下一级节点。如果标签只匹配了一部分或者出现字符不匹配则查找失败。当所有待查找字符消耗完毕时检查当前节点是否标记为完整键。例如查找foobazroot | | 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和foobarroot | | foo [terminal] | ---- bar [terminal]删除foobar后root | | foo [terminal]此时foo仍然有效不应被删除。删除操作的主要难点是从底向上恢复路径压缩性质并且不能误删其他键共享的路径。五、Radix Tree 的时间复杂度设(N) 为键的数量。(L) 为字符串键的长度。(W) 为整数键的位宽。(b) 为多位 Radix Tree 每层处理的 bit 数。对于常见的压缩字符串 Radix Tree操作典型时间复杂度查找(O(L))插入(O(L))包括边分裂删除(O(L))包括路径压缩前缀定位与前缀长度相关遍历匹配前缀的所有键取决于输出数量和遍历的子树大小这些复杂度通常假设子边查找的代价受控。例如如果子节点使用线性链表搜索那么每个节点的孩子数也会影响实际时间。对于固定宽度整数键多位 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 与其他数据结构的比较特性Radix Tree哈希表红黑树普通 Trie精确查找与键长度或层数相关平均 (O(1))(O(\log N))(O(L))前缀查询优秀通常需要额外机制通常需要遍历或额外索引优秀有序遍历可以通常不自然优秀可以插入删除可能需要分裂和合并需处理碰撞及扩容需旋转与再平衡需管理节点空间利用取决于路径压缩和节点布局取决于负载因子和实现有节点指针等开销可能有大量单分支节点典型用途前缀索引、整数索引精确查找有序键、范围查询字典和字符串前缀这里需要注意大 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 插入键插入操作需要区分三种情况没有匹配的孩子创建新叶子。当前边完全匹配沿路径继续。当前边只部分匹配分裂边将公共前缀保存到中间节点再挂接旧后缀和新后缀。例如插入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 与 XArray10.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 与 XArrayLinux 内核历史上提供了 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 时最重要的是掌握以下几个方面普通 Trie 与压缩 Radix Tree 的区别。如何根据公共前缀执行边分裂。为什么删除操作需要从底向上压缩路径。如何正确维护完整键标记和父子关系。如何分析键长度、索引位宽、分支数量和内存布局对性能的影响。如何区分字符串压缩 Radix Tree 与 Linux 内核历史上的整数索引 Radix Tree/XArray。对于 Linux 内核开发人员而言学习压缩 Radix Tree 有助于理解树形索引的设计思想而进一步研究 XArray、page cache、RCU 和内存管理则有助于将数据结构知识与实际内核实现联系起来。
一、引言在操作系统、网络协议栈、数据库和高性能存储系统中经常需要根据某个键快速查找对应的数据。例如根据字符串查找对应的配置项。根据 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 TreeRadix Tree 是一种根据键的字符、字节或二进制位组织数据的树形数据结构。Radix 是数学中的基数表示一个数制的基数。例如二进制的基数为 2。十进制的基数为 10。十六进制的基数为 16。在数据结构中Radix Tree 可以根据键的位或字符进行分支。对于固定宽度的整数键可以将键划分成多个 bit 组每一层根据其中一组 bit 选择子节点对于字符串键则可以根据字符序列构建前缀树。Radix Tree 的一个重要变体是压缩 Radix Tree也称为压缩 Trie。它将连续的单分支路径合并减少中间节点的数量。2.2 从普通 Trie 理解 Radix Tree假设需要存储以下字符串catcarcartdog普通 Trie 通常以单个字符作为边标签。相同前缀的字符串共享路径。例如cat、car和cart都以ca开头因此可以共享c和a对应的路径。这种结构具有良好的前缀查询能力但对于长字符串而言如果大量路径只有一个子节点就会产生很多不必要的中间节点。例如如果存储以下键network_device_drivernetwork_device_statusnetwork_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 的主要特点是路径压缩。两者的区别如下特性普通 Trie压缩 Radix Tree边标签通常是单个字符或固定宽度的位组可以是多个字符或多个位组单分支路径通常保留多个节点可以合并节点数量可能较多通常较少插入操作相对直观可能需要分裂边删除操作删除节点即可必要时清理路径可能需要合并边前缀查询支持支持严格来说Radix Tree 的具体定义会因实现而异。理解其压缩路径的思想比单纯记忆名称更重要。三、Radix Tree 的主要类型3.1 普通 Trie普通 Trie 逐字符或逐位组织键适合字符串字典、关键字检索和前缀匹配。优点是结构直观插入和查找比较容易实现。缺点是当键较长且存在大量单分支路径时会产生大量中间节点。3.2 压缩 Radix Tree压缩 Radix Tree 合并连续的单分支路径减少节点数量。它适合字符串索引、前缀查询和某些路由表实现。其主要挑战是插入时需要处理公共前缀分裂删除时需要进行节点合并。3.3 Binary Radix TreeBinary Radix Tree 根据键的二进制位进行分支。最简单的二进制树每层处理一个 bit分为 0 和 1 两个分支。对于固定宽度的整数键树的最大深度与键的位宽有关。例如64 位键的二进制树最多处理 64 层。二进制 Radix Tree 适合位前缀索引、某些路由算法以及整数键组织。3.4 多位 Radix Tree多位 Radix Tree 每层不只处理一个 bit而是一次处理多个 bit。假设每层处理 4 bit则每层最多有 (2^416) 个分支。如果处理 6 bit则每层最多有 (2^664) 个分支。这种方式可以降低树的高度减少查找过程中的层数但每个节点可能需要更多指针或槽位。Linux 内核传统 Radix Tree 就属于以整数索引为核心的多位树形索引结构而不是前面介绍的字符串压缩树。3.5 Adaptive Radix TreeARTAdaptive Radix Tree 是一种针对内存数据库和高性能索引优化的 Radix Tree。它会根据节点实际拥有的子节点数量选择不同的节点布局以减少稀疏节点的内存浪费并改善缓存局部性。ART 的设计重点是高性能内存索引与 Linux 内核传统 Radix Tree 的实现目标并不完全相同。四、Radix Tree 的核心操作Radix Tree 的核心操作包括查找、插入和删除。4.1 查找操作查找时从根节点开始根据待查找键的内容选择对应子节点。对于压缩字符串 Radix Tree查找过程如下从根节点开始。根据剩余键的首字符找到候选子边。比较剩余键与该边标签。如果整个边标签匹配则跳过对应长度的字符并进入下一级节点。如果标签只匹配了一部分或者出现字符不匹配则查找失败。当所有待查找字符消耗完毕时检查当前节点是否标记为完整键。例如查找foobazroot | | 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和foobarroot | | foo [terminal] | ---- bar [terminal]删除foobar后root | | foo [terminal]此时foo仍然有效不应被删除。删除操作的主要难点是从底向上恢复路径压缩性质并且不能误删其他键共享的路径。五、Radix Tree 的时间复杂度设(N) 为键的数量。(L) 为字符串键的长度。(W) 为整数键的位宽。(b) 为多位 Radix Tree 每层处理的 bit 数。对于常见的压缩字符串 Radix Tree操作典型时间复杂度查找(O(L))插入(O(L))包括边分裂删除(O(L))包括路径压缩前缀定位与前缀长度相关遍历匹配前缀的所有键取决于输出数量和遍历的子树大小这些复杂度通常假设子边查找的代价受控。例如如果子节点使用线性链表搜索那么每个节点的孩子数也会影响实际时间。对于固定宽度整数键多位 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 与其他数据结构的比较特性Radix Tree哈希表红黑树普通 Trie精确查找与键长度或层数相关平均 (O(1))(O(\log N))(O(L))前缀查询优秀通常需要额外机制通常需要遍历或额外索引优秀有序遍历可以通常不自然优秀可以插入删除可能需要分裂和合并需处理碰撞及扩容需旋转与再平衡需管理节点空间利用取决于路径压缩和节点布局取决于负载因子和实现有节点指针等开销可能有大量单分支节点典型用途前缀索引、整数索引精确查找有序键、范围查询字典和字符串前缀这里需要注意大 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 插入键插入操作需要区分三种情况没有匹配的孩子创建新叶子。当前边完全匹配沿路径继续。当前边只部分匹配分裂边将公共前缀保存到中间节点再挂接旧后缀和新后缀。例如插入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 与 XArray10.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 与 XArrayLinux 内核历史上提供了 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 时最重要的是掌握以下几个方面普通 Trie 与压缩 Radix Tree 的区别。如何根据公共前缀执行边分裂。为什么删除操作需要从底向上压缩路径。如何正确维护完整键标记和父子关系。如何分析键长度、索引位宽、分支数量和内存布局对性能的影响。如何区分字符串压缩 Radix Tree 与 Linux 内核历史上的整数索引 Radix Tree/XArray。对于 Linux 内核开发人员而言学习压缩 Radix Tree 有助于理解树形索引的设计思想而进一步研究 XArray、page cache、RCU 和内存管理则有助于将数据结构知识与实际内核实现联系起来。
