Linux Insides 内核数据结构剖析：Radix Tree（基数树）的实现与 API
Linux Insides 内核数据结构剖析：Radix Tree（基数树）的实现与 API
导读
本篇是《Linux Insides》内核数据结构章节的第二部分，聚焦 Linux 内核中用于「整数键 → 值」映射的核心数据结构——Radix Tree（基数树）。你将了解到 radix tree 与普通 trie 的本质区别、内核中 radix_tree_root 与 radix_tree_node 两个核心结构的字段含义、GFP_ 分配标志的作用，以及初始化、插入、删除、查找等完整 API 的用法与语义。读完本篇，你不仅能读懂内核源码中 radix tree 的实现，还能在后续分析中断描述符树（irq_desc_tree）等真实内核场景时一眼认出它的身影。
什么是 Radix Tree：从 trie 到压缩 trie
Linux 内核提供了大量不同数据结构和算法的库函数。本部分要讨论的 Radix Tree（基数树）正是其中之一，其实现与 API 分布在内核源码的两个文件中：
include/linux/radix-tree.h——结构体定义与 API 声明；lib/radix-tree.c——具体实现。
要理解 radix tree，首先要理解 trie（字典树）。trie 是一种实现关联数组接口的数据结构，允许以 key-value 形式存储数据。键通常是字符串，但理论上任何数据类型都可以作为键。trie 与普通的 n-tree 的关键区别在于节点：trie 的节点不存储键本身，而是存储单个字符标签；某个节点对应的完整键，是从树的根节点一路遍历到该节点的路径上所有标签拼接而成的。例如：
+-----------+
| |
| " " |
| |
+------+-----------+------+
| |
| |
+----v------+ +-----v-----+
| | | |
| g | | c |
| | | |
+-----------+ +-----------+
| |
| |
+----v------+ +-----v-----+
| | | |
| o | | a |
| | | |
+-----------+ +-----------+
|
|
+-----v-----+
| |
| t |
| |
+-----------+
在这个例子中，从根出发沿 g → o 路径可得到键 go，沿 c → a → t 路径可得到键 cat。
Radix Tree 就是压缩后的 trie（compressed trie）：与普通 trie 不同，基数树会把所有「只有一个子节点」的中间节点移除并合并到路径中，从而大幅减少节点数量、节省内存并加快遍历。Linux 内核中的 radix tree 正是这样一种将整数键映射到值的数据结构。
内核中的核心结构：radix_tree_root 与 radix_tree_node
Radix tree 由 include/linux/radix-tree.h 中的两个核心结构体表示。
首先是树的根节点 radix_tree_root：
struct radix_tree_root {
unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode;
};
三个字段含义如下：
height——树的高度；gfp_mask——指明后续内存分配如何进行；rnode——指向子节点的指针（使用__rcu标注，说明内核通过 RCU 机制安全访问该指针）。
gfp_mask：内存分配行为开关
内核底层内存分配函数都会接收一组标志位作为 gfp_mask，用来描述这次分配应该如何进行。文档中列举了几种典型的 GFP_ 标志：
GFP_NOIO——分配可以阻塞（睡眠），但绝不能发起磁盘 I/O；__GFP_HIGHMEM——允许使用ZONE_HIGHMEM或ZONE_NORMAL内存；GFP_ATOMIC——高优先级分配，绝不能睡眠（典型用于中断上下文）。
除此之外，内核中常见的还有 GFP_KERNEL（可阻塞的常规内核分配，是驱动编写中最常用的标志）、GFP_NOWAIT 等变体。理解 gfp_mask 的意义在于：它直接决定 radix tree 在分配内部节点时能否睡眠、能否使用高端内存，从而影响其在不同上下文（进程上下文 vs 中断/原子上下文）中的可用性。
节点结构 radix_tree_node
struct radix_tree_node {
unsigned int path;
unsigned int count;
union {
struct {
struct radix_tree_node *parent;
void *private_data;
};
struct rcu_head rcu_head;
};
/* For tree user */
struct list_head private_list;
void __rcu *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
各字段含义如下：
path——在父节点中的偏移量以及自底部起的高度；count——子节点的数量；parent——指向父节点的指针；private_data——供树的用户（使用者）使用；rcu_head——用于节点释放（RCU 延迟回收）；private_list——供树的用户使用；slots[RADIX_TREE_MAP_SIZE]——存储数据指针的槽位数组；tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]——标签位图。
tags 和 slots 两个字段最为关键也最有趣。每个节点都包含一组 slots，用于存放指向数据的指针；空槽在内核 radix tree 实现中存放 NULL。radix tree 还支持「标签（tag）」机制，即通过 radix_tree_node 中的 tags 字段，为树中存储的记录设置独立的位标记（例如标记脏页、标记写回状态），从而支持对满足某个标签条件的记录做批量高效查找，而不必逐一检查数据本身。
初始化 API：两种初始化方式
了解结构体之后，我们来看它的 API，首先从数据结构的初始化开始。内核提供了两种初始化方式。
方式一：使用 RADIX_TREE 宏：
RADIX_TREE(name, gfp_mask);
传入 name 后，该宏会定义一个给定名字的、已初始化的 radix tree。其实现非常简洁：
#define RADIX_TREE(name, mask) \
struct radix_tree_root name = RADIX_TREE_INIT(mask)
#define RADIX_TREE_INIT(mask) { \
.height = 0, \
.gfp_mask = (mask), \
.rnode = NULL, \
}
RADIX_TREE 宏先定义一个名为 name 的 radix_tree_root 实例，再调用 RADIX_TREE_INIT 宏。后者只是把 radix_tree_root 结构体按默认值初始化：height 置 0、rnode 置 NULL，并把传入的 mask 赋给 gfp_mask。
方式二：手工声明结构体，再配合 INIT_RADIX_TREE 宏：
struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);
其中：
#define INIT_RADIX_TREE(root, mask) \
do { \
(root)->height = 0; \
(root)->gfp_mask = (mask); \
(root)->rnode = NULL; \
} while (0)
INIT_RADIX_TREE 做的事与 RADIX_TREE_INIT 完全一致——以默认值初始化根节点结构体。两种方式任选其一，即可得到一个空树。
插入与删除 API
内核提供两个函数用于向 radix tree 插入和删除记录：
radix_tree_insert——插入；radix_tree_delete——删除。
radix_tree_insert 接受三个参数：
- 树的根（
struct radix_tree_root *root）； - 索引键（index key）；
- 要插入的数据。
radix_tree_delete 接受的参数与 radix_tree_insert 相同，只是不需要数据参数——它根据键定位并移除对应记录。
查找 API：三种查找方式
radix tree 的查找通过三个函数实现：
radix_tree_lookup；radix_tree_gang_lookup；radix_tree_lookup_slot。
radix_tree_lookup 接受两个参数：树根与索引键，它尝试在树中找到给定键，并返回与该键关联的记录。
radix_tree_gang_lookup 的签名如下：
unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
void **results,
unsigned long first_index,
unsigned int max_items);
它从 first_index 开始，按键排序返回一批记录，返回的记录数不会超过 max_items，实际返回数量作为函数返回值给出。这类「批量（gang）查找」特别适合需要一次取出一段连续键范围的应用场景，比如页缓存中按偏移批量取页。
最后一个 radix_tree_lookup_slot 则返回「槽位」——即最终会存放数据的那个指针位置，调用者可以直接读写槽位本身，避免二次查找的开销。
内核中的真实应用：本仓库内的佐证
radix tree 在内核中并非孤立存在，本仓库的其它章节恰好提供了两处真实使用证据：
- 在 Interrupts/linux-interrupts-7.md 中，内核初始化中断子系统时维护了一个
irq_desc_treeradix tree：在为每个中断描述符分配空间后，把中断描述符插入该树，以支持按 IRQ 号高效查找中断描述符。这正是「整数键 → 值」映射的典型场景——IRQ 号即键，中断描述符即值。 - 在 Initialization/linux-initialization-9.md 中，内核启动流程会调用
radix_tree_init（定义于lib/radix-tree.c）来初始化 radix tree 机制本身，随后中断子系统等模块才能使用上述 API。
此外，页缓存（page cache）也是 radix tree 的经典用户：以页偏移为整数键快速定位缓存页，并借助 tags 机制标记脏页——这与本部分讲解的 slots + tags 结构设计完全对应。
总结
通过本部分，我们完成了对 Linux 内核 radix tree 的完整剖析：它是以整数为键的压缩 trie；radix_tree_root 记录高度、分配标志与根子节点；radix_tree_node 通过 slots 存放数据指针、通过 tags 支持记录级位标记，并借助 RCU 机制安全回收节点；API 层面提供了 RADIX_TREE/INIT_RADIX_TREE 两种初始化方式、radix_tree_insert/radix_tree_delete 增删接口，以及单点查找、批量 gang 查找和槽位查找三类查询手段。
建议读者结合本仓库 DataStructures/linux-datastructures-1.md（内核侵入式链表与 container_of）与 DataStructures/linux-datastructures-3.md（位数组与位运算）一起阅读，即可系统掌握内核中「链式、树形、位级」三大基础数据结构；章节总览见 DataStructures/README.md 与 SUMMARY.md。后续在中断子系统（Interrupts/linux-interrupts-7.md）和内核初始化（Initialization/linux-initialization-9.md）的源码分析中，你会反复见到 radix tree 的身影。