数据结构与算法里总有一类结构看名字很冷门但真正用起来特别能打Rax树就是其中之一。Rax树是经过路径压缩的基数树严格说属于字典树Trie家族。我第一次在 Redis 源码里看到这个名字时还以为是什么小众玩具直到把 Streams 的实现读完才意识到它在长键共享前缀、内存开销和有序遍历这三件事上同时做得很好。这一篇就把 Rax 树的实现逻辑拆开讲节点怎么设计路径怎么压缩插入删除时如何分裂合并最后给一个可以自己上手跑的教学版实现。不管你是为了期末复习还是准备算法面试把这一类压缩字典树的思路吃透比死记一堆排序模板要划算得多。1. Rax树是什么先解决普通Trie的两个老毛病1.1 普通Trie的“一字符一路径”问题普通字典树的做法是每个字符占一个节点节点里挂一个子节点数组或者哈希表。插入abcd和abce时前三个字符a、b、c各自形成单链条到d和e才分叉。这个模型很好懂但有两个老毛病。第一个是节点数量太多。一个长度为 100 的 key哪怕它没有共享前缀也要创建 100 层节点。每个节点除了字符本身还要保存子节点指针、可能的数组扩容余量算下来一个字符平均消耗几十个字节。大量长 key 存在时内存会涨到让人肉疼。第二个问题是缓存局部性差。普通 Trie 沿着路径往下走时每一步都要跳一个地址不连续的节点cache miss 是常态。键越长cache miss 次数越多性能衰减得越明显。所以业界早就意识到必须对单分支路径做压缩。这就是 Patricia Trie 和基数树的出发点。Rax 树是 Redis 作者 Antirez 写的基数树实现它在压缩路径的基础上还专门为“存储 key 到 value 的映射”做了很多细节优化。很多资料把 Rax 和基数树混着叫严格说 Rax 是一棵有序的、带值的压缩基数树适合做前缀搜索、范围遍历、键值存储这一类场景。1.2 压缩节点和非压缩节点怎么分工Rax 树里只有两种节点形态压缩节点iscompr1和非压缩节点iscompr0。压缩节点表示这一段路径上没有任何分叉所有 key 都共享这段前缀所以开场就是一段连续的字符直接一口气比较完。比如只有abcd和abce两个 key 时公共前缀abc就可以存在一个压缩节点里子节点再走到分叉点。非压缩节点则表示这是分叉点每个字符对应一棵子树。图上的表达方式其实就是把普通 Trie 的“单分支链”折叠成一个节点路径短了节点少了比较次数却不会增加。需要注意Rax 的压缩节点并不是把整个公共前缀和后续分叉完全混在一起。节点里会保留“最后一个字符”的特殊语义为的就是让插入和删除时的分裂操作可控。这个细节在实现篇里非常关键很多人写简化版 Rax 时没注意导致插入新 key 时不知道在哪一刀切开。1.3 天然有序带来的连锁好处Rax 树还有一个容易被忽略的优点它天然按键的字典序排列。插入操作会把 key 放到正确位置不需要再事后调用排序算法。这个特性和稳定排序不一样但能直接替代“先收集 key再统一排序输出”的流程。 配合栈做 DFS或者配合双端队列做层序遍历就能平滑地输出有序结果。 这一点在自动补全、范围查询、批量导入后需要按序处理的场景里非常有用。2. Rax树节点设计与内存布局解析2.1 一个位域和一个size字段撑起全部状态先看一份精简后的节点定义和 Redis 源码里的结构高度一致typedef struct raxNode { uint32_t iscompr:1; // 1压缩节点0普通节点/叶子 uint32_t size:31; // 压缩节点存储前缀长度普通节点存储子节点数量 unsigned char data[]; // 柔性数组字符和子指针都放这里 } raxNode;只有 4 字节的头部外加一段柔性数组。iscompr 一个比特区分两种节点形态size 字段在两种形态下含义不同压缩节点里表示公共前缀的字节数非压缩节点里表示分了多少支也就是有多少个子节点。我一开始读源码时最不习惯的就是 size 字段的“双重语义”。写查找逻辑时必须先看 iscompr 再决定怎么解释 size。如果默认 size 是子节点数遇到压缩节点时长度判断会直接出错。这个坑我踩过后面在排查篇里再展开。2.2 压缩节点里的字符和指针怎么排布教学版可以把字符数组和子指针数组分开存比如chars单独 mallocchildren单独 malloc。但真实 Rax 为了内存紧凑是把字符和指针塞进同一个 data 区域里的。压缩节点的 data 布局大致是先放 size 个公共前缀字符再放一个尾部字符最后放一个指向唯一子节点的指针。这个尾部字符其实承担了“分叉依据”的角色。非压缩节点的 data 布局则是先放 size 个分叉字符再放 size 个连续的子节点指针字符按字典序排列方便二分查找。真实源码里指针是直接放在unsigned char数组后面的所以 C 语言层面上存在未对齐访问风险。我印象很深刻的是它用了memcpy把指针从 data 区安全拷到局部变量而不是直接强制类型转换。这在高版本编译器里属于很稳妥的做法。从微架构角度看字符和指针贴在一起后节点整体只要一次 malloc释放时也只要一次 free还能减少内存碎片cpu cache 命中率也会好看很多。2.3 叶子节点其实就是 size0 的非压缩节点Rax 没有单独的叶子类型。当一个节点的 iscompr0 且 size0它就是一个叶子表示某一条 key 在这里结束。叶子里保存的是这个 key 对应的 value 指针。刚开始我总觉得叶子应该单独加一个 flag读完源码才明白没必要普通节点的 size 本来就表示子节点数量为 0 就是没有孩子天然等价于结束标记。叶子节点是整棵树里唯一不需要比较字符的节点查找走到叶子时必须保证剩余长度刚好为 0才算真正命中。这个设计还衍生出一个细节如果某个 key 是另一个 key 的前缀比如abc和abcd同时存在路径上必然需要一个分支点一个方向指向空叶子表示abc结束另一个方向继续走d。这就是后面要说的“分裂”操作。2.4 分裂和合并Rax树的动态平衡手段插入新 key 时如果新 key 和老路径在某个字符处分叉原来的压缩节点就必须分裂。核心思想是“把共同前缀留在原地把分歧字符拆成一个普通节点”。举例说明当前压缩节点存储abcd子节点指向某个子树。现在要插入abce共同前缀是abc第 4 个字符一个是d一个是e。分裂动作是把原压缩节点缩短成abc然后新建一个非压缩节点这个普通节点的字符数组里放d和e两个字符分别指向原来的子树和新插入的子树。反过来删除 key 时如果某个普通节点只剩下一个有效分支那么就可以把这段单分支重新压缩回父节点把多余的节点合并掉。合并不是正确性的必须条件但如果不做树会逐渐退化成普通 Trie压缩特性就白费了。真实实现里删除后会有选择地进行压缩教学实现可以先做懒惰合并确认逻辑正确后再优化。3. 从零实现一个可用的极简Rax树3.1 结构定义和初始化为了便于演示这一版用直观的字符数组加指针数组先不追求 Redis 那种柔性数组布局。关键是保留 iscompr、size 字段以及分裂合并逻辑。typedef struct raxNode { int iscompr; // 1压缩节点0普通节点或叶子 size_t size; // 压缩节点用前缀长度普通节点用子节点数量 unsigned char *chars; // 压缩节点用前缀字符普通节点用分叉字符 struct raxNode **children; // 子节点指针数组 void *value; // 叶子节点保存关联值 } raxNode; typedef struct rax { raxNode *head; // 头节点就是根 size_t numele; // 已插入的 key 数量 size_t numnodes; // 总节点数 } rax;初始化空树时head 直接指向一个叶子节点rax *raxNew(void) { rax *rt calloc(1, sizeof(*rt)); raxNode *root calloc(1, sizeof(*root)); root-iscompr 0; root-size 0; // 叶子 rt-head root; return rt; }教学实现里为了让“前缀关系”处理起来直观可以在 key 尾部显式补一个\0哨兵表示结束。真实 Rax 并不需要调用方传\0它在内部通过叶子节点判断结束。教学版加上哨兵后abc会按abc\0参与比较这样abc和abcd的公共前缀就是abc而分叉点出现在结束哨兵和d之间代码逻辑统一很多。3.2 查找从根到叶的完整路径匹配查找算法是理解整棵树的最佳入口。核心逻辑是压缩节点整段比较普通节点按字符查找叶子节点判断是否恰好走到 key 末尾。raxNode *raxFind(rax *rt, unsigned char *key, size_t keylen) { raxNode *n rt-head; size_t pos 0; while (n) { if (n-iscompr) { // 压缩节点整段前缀比较 if (keylen - pos n-size) return NULL; if (memcmp(key pos, n-chars, n-size) ! 0) return NULL; pos n-size; n n-children[0]; // 压缩节点只有一个子节点 } else if (n-size 0) { // 叶子节点必须正好走完 key return (pos keylen) ? n : NULL; } else { // 普通节点在分叉字符里二分查找 if (pos keylen) return NULL; unsigned char c key[pos]; int lo 0, hi n-size - 1, idx -1; while (lo hi) { int mid (lo hi) / 2; if (n-chars[mid] c) { idx mid; break; } else if (n-chars[mid] c) lo mid 1; else hi mid - 1; } if (idx -1) return NULL; pos; n n-children[idx]; } } return NULL; }这段代码有两点值得注意。第一压缩节点不能用strlen求长度必须用显式 size 字段。因为压缩内容可能包含二进制字节或哨兵字符字符串函数一遇到\0就断直接翻车。第二普通节点的字符数组保持有序是二分查找的前提插入新分叉时必须维护字符顺序绝对不能简单 append。3.3 插入两种分裂场景要分开处理插入是 Rax 树里最容易写崩的部分。先走一遍查找逻辑找到“最接近”的节点然后判断是在压缩节点中部发生分歧还是在普通节点缺失字符。两种场景处理方式不同。场景一普通节点里找不到 key 的下一个字符。这种情况最简单。把新字符按字典序插到普通节点的 chars 数组里再挂一个新节点做叶子即可。场景二压缩节点里的前缀没有完全匹配或者前缀匹配完但后面还需要继续分叉。这里需要分裂压缩节点。大致步骤如下计算共同前缀长度 split表示前 split 个字符仍然一致。新建一个普通节点用来承接 split 之后的分叉字符。老节点剩下的字符作为一个分支插入到这个普通节点中。key 剩余部分作为另一个分支插入到这个普通节点中。老节点缩短为只保留 split 个字符并把子节点指针指向新建的普通节点。我举一个直观的例子。当前树只有一个 keyabcd\0路径是压缩节点 charsabcd\0子节点是叶子。现在插入abce\0两个串的共同前缀是abcsplit3。压缩节点缩短为 charsabc新建普通节点分叉字符数组为{d, e}字符d指向原来的叶子字符e指向新 key 的叶子。最终路径变成abc压缩节点 普通分叉节点 两片叶子。如果插入的是abc\0也就是已有 key 的前缀那么 split3普通节点的分叉字符为{\0, d}\0指向新叶子d指向 old 叶子。还有一个更隐蔽的边界如果共同前缀长度 split0说明两个 key 在压缩节点的入口处就开始分叉。这时候不能把原压缩节点继续留着当父节点而应该在顶部新建一个普通节点用原节点压缩串的第一个字符和 key 的第一个字符作为两个分叉。这里的处理很容易漏特判我建议写代码时把split 0单独拎出来不要和其他分裂逻辑混在一起。3.4 删除先摘叶子再考虑合并删除相对直接先找到叶子节点摘掉 value释放对应存储然后自底向上清理。如果某个普通节点删完只剩一个有效分支就可以把它的父节点和子节点合并。合并操作最怕递归过度。教学版本可以只做一层合并删完叶子后如果父节点是普通节点且 size 变为 1就把父节点的唯一字符并入祖父节点然后丢掉父节点。如果删除后立刻做全量压缩代码会变得很难维护。我的建议是第一版先保证正确性用遍历验证删除后所有 key 仍然能查到之后再补压缩逻辑。删除流程 1. 从根走到叶子记录完整路径。 2. 删除叶子更新父节点字符数组和子指针数组。 3. 如果父节点变成空直接释放父节点。 4. 如果父节点 size1尝试向上合并。真实 Rax 的删除逻辑比我这里复杂因为它要考虑压缩节点的尾巴字符、value 覆盖释放等问题。但教学版掌握了这套基础读源码时就不会再一头雾水。3.5 有序遍历递归、栈和双端队列Rax 树按字典序组织遍历时只要从左到右访问普通节点的每个分支就能输出有序结果。递归写法最简单void raxWalk(raxNode *n, unsigned char *prefix, size_t prefixLen) { if (!n) return; if (!n-iscompr n-size 0) { printf(%.*s - %p\n, (int)prefixLen, prefix, n-value); return; } size_t base prefixLen; if (n-iscompr) { memcpy(prefix prefixLen, n-chars, n-size); prefixLen n-size; raxWalk(n-children[0], prefix, prefixLen); return; } for (size_t i 0; i n-size; i) { prefix[prefixLen] n-chars[i]; raxWalk(n-children[i], prefix, prefixLen 1); } }递归在树深度很大会有栈溢出风险。实际嵌入到服务进程里我更喜欢用显式栈把要访问的节点压栈或者用双端队列做 BFS。配合双端队列还可以做层序遍历输出每个深度上的分叉信息这对调试压缩效果特别有用。 千万别一边遍历一边修改树迭代器会直接失效。4. 实操中的常见问题与排查实录4.1 未对齐的指针访问最隐蔽真实 Rax 把子节点指针放在unsigned char data[]里直接(raxNode**)node-data offset这类写法在某些架构上会触发总线错误。最稳的解法是memcpy到局部变量再使用。我自己的教学实现虽然把 chars 和 children 分开 malloc但只要你想复刻 Redis 的紧凑布局就一定会在对齐上踩坑。排查信号是程序在小端 x86 上跑得好好的交叉编译到某种 32 位平台后插入第二十个 key 时直接 SIGBUS。这类问题用 gdb 看堆栈往往只看到 memcpy 或者赋值语句不会直接提示对齐。提前在结构体里做对齐填充或者统一走 memcpy 读取是最省心的防御手段。4.2 压缩节点长度算错查找路径直接跑飞size 字段的双重语义很容易导致错误。我见过一份仿写代码在压缩节点里用node-size当作子节点数量去遍历 children结果遍历出一个悬垂指针。排查时先打印每个节点的 iscompr、size、chars 内容很快就能定位。另外插入分裂后旧节点的 chars 要重新分配并拷贝前 split 个字符如果拷贝长度写成strlen(oldChars)会被内部哨兵坑掉。记住所有长度都用 size 字段。4.3 遍历和修改同时进行Rax 的迭代器本质是保存了当前节点指针和路径栈。如果遍历过程中插入新 key分裂会导致老节点被修改甚至被 free。最常见的表现是遍历到一半出现重复 key或者程序直接崩溃。要安全遍历要么先把 key 都收集到数组里遍历结束再批量插入要么使用 Redis 源码里那种带路径栈的 raxIterator每次操作前后都重新定位。我在做流式前缀匹配时就吃过亏一边收集匹配结果一边删除结果集里的 key最终导致迭代器失效。后来改成两阶段遍历阶段只收集索引删除阶段另开一轮问题立刻消失。4.4 内存碎片和缓存命中率Rax 树减少节点数量的本质是在牺牲部分写操作复杂度的前提下换取更少的内存分配次数和更好的缓存命中率。但如果在分裂合并时频繁 malloc/free碎片依然会上升。现实项目里插入量和删除量都很大时建议每创建一批节点就观察 RSS 曲线。如果 RSS 持续增长但 numnodes 没涨多少大概率是某个合并分支没有释放老节点。排查内存泄漏可以给节点分配函数加计数器对比rax-numnodes和实际 malloc 次数。这个计数器在调试期非常宝贵千万别删。5. Rax树在自己的项目里怎么用5.1 前缀匹配和自动补全Rax 树最直接的场景是前缀匹配。给定一个前缀沿着树走到对应节点然后把这棵子树完整遍历出来得到的就是所有以该前缀开头的 key。自动补全、关键词联想、敏感词过滤的前缀命中都能用。普通 Trie 也能做这件事但 Rax 的长键共享前缀能力更强。比如几万个 URL 都从同一个域名开头普通 Trie 要存几十层单分支节点Rax 一个压缩节点就能吃掉。内存和 cache 都会好看很多。5.2 替代“先收集再排序”的有序输出有些项目本来用哈希表收集 key最后要按字典序输出时再把这些 key 倒进数组执行快排。换成 Rax 后插入阶段就维护了有序性遍历时天然有序省掉一次排序算法的时间和额外空间。这不是说排序算法不重要而是让你知道某些场景下选对底层结构比事后排序更高效。如果你同时还需要“按插入顺序访问”那么可以额外挂一个双端队列或链表辅助记录顺序。Rax 负责字典序双端队列负责时间序两个结构配合就很顺手。5.3 常见结构选型对比结构查找复杂度有序遍历内存特征适合场景哈希表O(1) 平均不支持每个 key 额外存哈希桶单点存取不要求前缀查询跳表O(log n)支持每层指针冗余区间查询、排名统计普通 TrieO(len)支持节点多内存开销大短 key 字典Rax树O(len) 但常数小支持压缩前缀节点少长 key、共享前缀、前缀匹配B树O(log n)支持磁盘页友好大规模外存存储时间复杂度上 Rax 每次比较都是一整段内存比较而不是逐字符跳节点所以常数比普通 Trie 小很多。空间复杂度方面Rax 的节点数大致等于“所有分叉点的数量 叶子数量 被压缩路径的段数”相比普通 Trie 按每个字符一个节点省掉的是那些没有分支的单链表节点。5.4 后续可以继续扩展的方向如果你把这一章的极简版跑通了下一步可以照着真实 Rax 源码改进三件事第一把字符和指针合并进同一块柔性数组加 memcpy 安全读取第二实现支持随机访问的迭代器让 seek、next、prev 能操作第三给节点加入引用计数或持久化支持让数据能落盘。另外还可以思考如何处理 value 的覆盖释放Rax 允许插入同样 key 并替换 value替换时必须把旧 value 返回给调用方而不是直接覆盖丢失。最后说两句实操体会我自己实现完这版 Rax 之后最大的感受是路径压缩听起来简单真正处理分裂边界时才体会到源码里那些位域和柔性数组为什么这样设计。特别是压缩节点缩短、普通节点中插字符、叶子哨兵这类小细节任何一个没想清楚都可能把整棵树的顺序打乱。我的习惯是在白纸上画一棵只有两三个 key 的小树插入一个新 key 后把每个节点的 iscompr、size、chars 都写出来一步一步跟踪。这样做哪怕代码写错了也比直接看内存快得多。如果你准备拿 Rax 去优化自己的项目建议先从这章的教学版跑通再考虑要不要引入 Redis 的完整实现。多跑几个前缀关系复杂的例子你会比读十遍源码更有底气。