那次我在翻Redis Streams的源码想知道消费者组名字到底存在哪里。顺着结构体一路找过去看到一个叫rax的东西。第一反应是哦Radix Tree嘛前缀树但越看越不对劲——它的节点居然能在路径中间直接挂一个值而且压缩节点能压住一整段字符串。这不是我熟悉的那个经典Radix Tree而是antirez单独造的一个变体。后来我花了一整个下午把rax.c和rax.h啃了一遍又把插入、删除、迭代器的行为用随机数据跑了几轮才算真正摸清它的实现逻辑。这篇就当作系列里的第25章把Rax树从数据结构定义到核心算法完整拆开讲一遍。适合正在学数据结构的人、想读Redis源码但卡在rax这一块的人以及任何需要实现字符串前缀索引的工程师——它比你自己用Trie魔改要成熟得多。1. 为什么需要Rax从Trie到压缩前缀树的演进1.1 我是在哪里遇到它的先说结论Rax是Redis作者自己写的通用数据结构本质是一棵压缩前缀树。我在Redis Streams的源码里见到它时它承担的是字符串关联存储的任务——比如消费者组名称到游标信息的映射。这类数据和普通的字典不一样它有明显的前缀复用group-a、group-b、group-abc这些key共享group-这一段。如果用哈希表所有前缀信息全被打散你想按前缀遍历根本做不到。如果用普通Triekey之间的公共前缀会被拆成一长串单字符节点路径很长、内存很碎。Rax则把公共前缀压进同一个节点里让前缀匹配和有序遍历都变得很自然。这也是我建议每个研究数据结构的人都读一遍rax.c的原因它展示了一个真实的高性能索引结构如何平衡查询效率、内存占用和实现复杂度比教科书里的示例代码完整得多。1.2 Trie的问题与Radix Tree的压缩思路教科书里的Trie是逐字符分叉的。插入hello和help前三个字符hel会形成三条单独的路径每个节点只存一个字符。这种做法在字符集很大时尤其浪费每个节点还要为子节点维护一个指针集合要么开256个槽位的定长数组要么用一个哈希表这两种方案要么内存爆炸要么多一层哈希计算。Radix Tree把连续的单子节点路径压成一个节点节点里存一段字符串而不是单个字符。比如hello和help共享的hel就变成一个节点后面分出p和lo两个分支。这样做的好处很明显单个路径的深度大幅下降查找时可以跳过整段字符的比较内存也不再为一个字符分配一个节点头。但经典Radix Tree有个尴尬之处值通常只能存在叶子节点。如果我想同时保存foo1和foobar2经典做法要么把foo继续扩展成一个子路径要么额外做规则约定。因为中间节点默认不承担值的角色你没法自然表达这个字符串本身也是一个key。1.3 三张对照表结构节点存储内容值的存放位置前缀查询典型问题Trie单个字符一般挂在叶子支持但不高效路径深、内存碎经典Radix Tree压缩后的字符串段通常只在叶子支持中间key表达困难Rax压缩后的字符串段任意节点都可存支持且高效实现复杂度较高Rax的关键就是在Radix Tree的压缩思想上给每个节点加了iskey标记。某个压缩路径的中间位置如果恰好是一个完整key直接在该节点上挂值即可。真正需要拆开的时候插入算法再把节点分裂成两段。这个任意节点可存值的设计让Rax变成了一个既能前缀匹配、又能存储任意key-value的有序字典。我第一次看到iskey字段时觉得不过是一个布尔位后来自己动手实现类似结构才发现就是这个字段重新定义了整棵树的写入逻辑——插入、分裂、删除合并全部要围着它转。2. 内存布局拆解raxNode的位域与柔性数组2.1 一个node节点到底长什么样想要理解Rax的算法先得把raxNode的内存布局刻在脑子里。它是整个实现的地基。typedef struct raxNode { uint32_t iskey:1; /* 当前节点是否存有一个完整的key */ uint32_t isnull:1; /* 存的value是否为NULL */ uint32_t iscompr:1; /* 是否为压缩节点 */ uint32_t size:29; /* 压缩路径长度或子节点个数 */ unsigned char data[]; } raxNode;这里用位域把头部压缩到了4字节四个核心标记塞进一个uint32_t。size字段有29位理论上单个节点最多存2^29个字符或子节点这个上限在实际内存中都碰不到所以可以放心。data[]是一个柔性数组它不占结构体大小真正的数据全部跟在头部后面。这就是为什么你不能把raxNode当成一个定长结构体来看——你拿到的是一个不完整的头具体内容要靠字段自己推断。2.2 压缩和非压缩节点的两种内存排布Rax的节点分两种形态每种形态的data[]排布完全不同。非压缩节点是标准的分岔口形态size表示子节点个数。它的data里先连续铺size个字符代表每个子分支的字符字符之后紧跟size个void*指针每个指针对应前面对应字符的子节点如果iskey为1指针后面还会有一个8字节的值指针。压缩节点则是单行道形态size表示路径字符串的长度。它的data里先铺size个字符的路径内容之后只有一个void*子节点指针如果iskey为1末尾同样多一个值指针。为什么非压缩节点要把字符数组和指针数组分开铺直接每个字符后面跟一个指针不是更直观吗这样做是为了缓存友好。查找时逐个字符比较字符在内存中是连续的一段CPU能一次加载很多字节确定分支后又要跳到对应指针。如果把字符和指针交错存放每次比较都要跨越指针跳跃缓存命中率会明显下降。2.3 指针偏移计算的坑这里我要提醒你一个非常容易踩的坑压缩节点后面那个子节点指针不是简单地从data size位置取的。因为指针需要按8字节对齐而压缩路径的字符串长度是任意的你必须在路径结尾处做一次对齐向上取整。/* 压缩节点子节点指针的起始位置需要对齐到8字节 */ child_ptr (raxNode**) ((unsigned char *)node-data node-size 7 ~(size_t)7);我第一次读源码时没留意这个细节自己照着data size直接取指针结果在长度为奇数的那批节点上频繁拿到错地址查了一晚上才发现是对齐问题。以后你要是自己实现类似结构或者写raxNodeSize()这类辅助函数一定记得把对齐逻辑单独抽出来测试。3. 插入分裂Rax树最核心的写路径3.1 raxLowWalk先找到分歧点插入的第一步不是急着建节点而是沿着现有路径找到这个key会在哪里和已有路径分道扬镳。走查逻辑是从根节点开始的碰到压缩节点直接拿data里那段字符串与目标key逐字节比较碰到非压缩节点根据当前字符走对应的子指针。三种情况会结束这次走查第一种key的每个字符都匹配完最终落在一个已有节点上这时就是普通的值更新第二种key匹配完了但当前节点还有更长的路径那么新key是某个已有key的前缀需要在当前节点额外挂一个分支第三种某个字符匹配不上而且这个不相符的位置正好落在一个压缩节点的中间这才触发分裂。在代码里这个函数叫raxLowWalk它还会返回当前比较到的字节偏移。这也是为什么插入函数能准确知道该从哪里下手。3.2 分裂到底在做什么压缩节点只能有一个子节点这条路是单车道。现在要在这里分岔你就必须把这条单车道改造成一个岔路口。分裂的本质是把一段压缩字符串从分歧点切成两段。想象一个压缩节点原来存着字符串foobar后面带着一个子节点。现在要插入foobaz两个key在fooba处完全一致到r和z才分家。Rax会把原来的节点改造成一个只存fooba的压缩节点同时创建两个新的子节点一个存r继续保留原来foobar的value和后续子节点另一个存z挂上新插入的foobaz的value。这一步的关键在于分裂时原先节点的iskey、isnull、子节点指针、值指针都要按正确的位置重新安置。如果公共前缀本身就是一个完整key那么分裂后的新节点必须设置iskey如果原来被切掉的部分是一个key这个身份要转移到后缀节点上。一个比较绕的细节是分裂后的新节点和旧节点在内存里都是新建的旧节点实际上会被改造成后缀节点。你在代码里会看到raxSplit()函数它接收一个old节点指针然后返回新节点地址——如果你拿着旧指针继续访问极有可能读到被回收的内存。3.3 一个完整的插入过程演示我拿foo、foobar、foobaz这三个key走一遍过程你就能看到整棵树怎么一步步长起来的。初始时树是空的插入foo根节点就是一个压缩节点data里存foo设置iskey1挂上值1。此时树只有一个大字符串节点干净利落。插入foobar从根节点走查发现foobar的前三个字符foo完全匹配根节点的路径字符串但根节点路径到此结束而目标key还剩bar。于是根节点保持不变在它下面新挂一个子节点存字符串bar并在这个子节点上设置iskey1存值2。此时树是foo(value1) -bar(value2)。插入foobaz同样从根节点走查匹配完foo后进入子节点bar。比较子节点的路径字符串bar和剩余keybaz前两个字符ba一致到了r和z分叉。这个不匹配的位置落在bar这个压缩节点的中间于是触发分裂。分裂之后的结构是foo(value1) -ba(非key节点) -r(value2)以及ba-z(value3)。bar节点本身被改造成一个只包含ba的节点原来的r分支和value2都转移到新子节点上。看起来只是三个key实际上已经完整覆盖了普通插入、后缀追加、中途分裂三种情况。你拿这三组数据跑通之后Rax的写路径就基本没有盲区了。3.4 我调试插入逻辑时的经验我自己照着思路实现过一遍Rax的插入调试阶段最大的教训是分裂完成之后旧指针不能再用。Rax的分裂为了性能会复用旧节点内存分裂后它的语义已经变了你必须从父节点重新拿子节点指针。我一开始图省事在分裂后直接访问旧节点里的子节点指针结果一连串段错误。另外一个建议写一个校验函数递归检查整棵树的不变量。比如每个非压缩节点的子节点数量必须等于size每个压缩节点必须只有一个子节点所有节点的iskey标志和值指针是否一致。我后来靠这个校验函数几分钟就定位到了指针偏移错误比反复拿gdb打印节点高效得多。4. 查找与删除对称的读路径与回收逻辑4.1 raxFind的遍历策略查找比插入简单得多核心就是顺着压缩边一路对比下去。从根节点开始对每个压缩节点直接比对整段路径字符串如果完全匹配继续深入唯一子节点如果中间某个字符不匹配立即返回未找到。对非压缩节点取当前字符直接通过字符索引跳到对应子节点如果没有这个字符同样返回未找到。这个策略最好的地方在于压缩节点把多次字符比较合并成一段连续内存的比较。现代CPU对连续内存的扫描速度非常快而且你跳过的是一整段节点指针寻址次数大幅减少。最理想情况下查找一个长key只需要访问key_length / 平均压缩长度个节点。你可以这样验证插入10万个带公共前缀的随机字符串然后对比raxFind和哈希表的点查速度。哈希表可能稍快一点因为它的常数小但Rax的差距通常在一个数量级以内而且它还额外支持前缀遍历——这是哈希表完全做不到的。4.2 删除时如何收敛合并是分裂的逆操作删除逻辑是Rax里我个人认为最需要小心的部分因为它在删除节点之外还会可能做一次压缩合并。删除一个key的基本步骤是先走查找到对应节点把该节点的iskey清掉并释放值指针。但如果这个节点同时还有子节点说明它只是一个路径中间的路过者比如foo这个key被删掉时它下面还挂着bar分支这时只清iskey就够了节点本身必须保留。麻烦的是另一种情况节点没有子节点了它变成纯叶子。这时要把这个叶子从父节点摘除。摘除之后父节点如果恰好只有一个子节点并且父节点本身不是key就满足合并条件——把父节点和唯一子节点拼接成一个更长的压缩节点。这就是分裂的逆操作。合并时要小心iskey的归属。假设父节点不是key但子节点是key合并后的新节点必须继承子节点的iskey标志和值指针。如果两边都不是key合并后的节点就保持非key状态。这个过程我建议写4到6个用例专门覆盖删除叶子、删除中间key、删除后触发合并、删除根节点使树为空。一次跑完这些边界基本就稳了。4.3 删除实现中容易被忽略的边界我在实现中吃过两次亏都出在边界。第一次是删除一个中间key之后没有及时检查父节点是否需要合并。结果是树里留下一个退化的压缩节点一个非key节点只有一个子节点本来可以直接合并成一个更长的字符串却硬生生多了一层指针跳转。树还是对的但性能和压缩的初衷背道而驰。第二次是处理isnull。Rax里如果存储的value本身就是NULL内存里不一定分配那个指针空间而是靠isnull标记。删除时如果只清iskey忘了处理isnull对应的指针分配状态再插入同一个key时就会遇到该释放的没释放、该分配的被跳过的错乱。我的建议是删除和插入共用同一套节点状态转换逻辑别在两边各写一套否则状态组合一旦多起来很容易漏掉某一支。5. 迭代器与遍历有序输出所有key5.1 迭代器的栈式路径记录Rax的节点不存父指针所以它设计了一个迭代器来处理遍历。raxIterator内部维护一个栈栈里保存的是从根节点到当前节点的完整路径。每次访问一个节点就把当前节点和这个节点上匹配到的字符偏移压入栈中需要回溯时从栈里弹出节点继续寻找下一个未访问的分支。这里有一个非常容易被初学者忽略的点raxNext返回的key不是从节点上直接拿字符串拼出来的而是迭代器通过对栈里所有路径片段做累加拼接得到的。因为每个节点都可能存一段多个字符的字符串你必须把栈上每一段的data内容按顺序合并。这个拼接逻辑本身不复杂但你需要保证迭代器的当前节点与栈顶状态一致否则在压缩节点上移动一步栈里的拼出来的key就会错位。5.2 迭代器上的三个常用操作迭代器通常有三个核心操作要配合使用。raxSeek负责定位它可以把迭代器移动到某个精确key上也可以移动到第一个大于等于目标key的位置。这个能力是范围遍历的基础。raxNext和raxPrev负责单调遍历。raxNext会从当前位置出发按中序找到下一个比当前key大的节点。如果你把raxSeek定位到最小key然后反复调用raxNext就能按字典序输出全树所有key。raxStop则负责回收迭代器内部的动态缓冲区。如果你是嵌入式环境或者对内存峰值敏感一定要在遍历完成后及时调用它别依赖GC。一个实用的技巧是用迭代器把整棵树遍历一遍收集所有key再和插入前的原始数组排序后的结果做一次全等对比。这个测试能同时验证迭代器正确性、插入正确性和树结构完整性比任何单元测试都高效。5.3 用迭代器写一个随机验证脚本我建议你上手之后至少跑一遍下面的流程我自己就是这么验证Rax实现的先生成10万条随机字符串作为测试集然后依次插入Rax树。插入完毕后用迭代器从头到尾把所有key收集出来做两个断言第一集合大小必须等于插入数据的总数不能有重复或丢失第二迭代器输出的key序列必须和排序后的原始数组完全一致。最后再随机删除其中3万条key再次迭代遍历确认剩下的key仍然有序且数量正确。这个脚本看起来简单但能一次性暴露出寻址错误、合并逻辑错误和迭代器状态错乱这三个最常见的实现bug。我在自己的实现里头一轮就跑出20多个assert失败几乎全集中在对齐和合并这两个地方。把这些坑填平之后整棵树的稳定性才算真正过关。6. 生产环境的应用与选型建议6.1 Rax在Redis里的具体工作Rax不是理论玩具它在Redis里有实际落地的场景。我最初就是在Streams模块里碰到它的消费者组相关的字符串元数据需要按组名做快速查找也经常需要按前缀或顺序遍历。这个需求用哈希表太散用普通Trie太碎Rax正好卡在两者之间。Rax在Redis里承担的角色本质上是一个有序字符串字典既有dict一样的点查效率又能像跳表一样顺序遍历。如果你需要给某个系统设计一个带前缀查询的KV存储Rax的实现思路可以直接抄。6.2 什么时候该用Rax什么时候别用先说适合的场景。第一key是字符串而且存在明显的公共前缀——比如URL、路径、命令行补全词表这类数据用Rax能获得极高的压缩率。第二你需要同时支持精确查找和前缀扫描比如输入foo自动联想出foo开头的全部key。第三你的数据量在千万级别以下且内存常驻——Rax是纯内存结构。不适合的场景也有。第一你的key是随机分布的前缀复用了了无Rax的压缩优势完全体现不出来这时候一个简单的哈希表加一个跳表配合效果反而更容易控制。第二数据量超大且需要落盘Rax没有就地序列化和磁盘页结构你要持久化它得自己设计格式这时候B树或LSM树更合适。第三你只需要范围数值查询而不关心字符串前缀——Rax对数值类型没有天然的压缩优势用skiplist或B树更顺手。最后说一个我最常被问到的问题Rax和B树到底哪个好如果你是在内存里做动态字符串索引Rax的结构更轻、实现更直接而且前缀遍历是天生的能力。B树强在磁盘存储上节点大小和页对齐深度绑定纯内存场景优势不明显。一些题外话我读rax.c最大的收获不是记住那些宏和指针偏移而是看到一个工程上成熟的结构如何被隔离出来。它的分裂和合并逻辑放在任何一棵树上都是一样的思路——但加上了任意节点可存值这个约束之后所有细节都微妙地变了。真正的经验不会写在教科书里只会藏在这些边界处理和一眼看不太懂的对齐宏里。如果你想动手验证我建议把Redis源码里的rax.c和rax.h拎出来写个简单的包装替换掉rax_malloc相关函数然后跑一遍我上面说的随机插入、遍历、删除测试。这个工程量不大但跑通之后你对于前缀树到底能优化到什么程度会有非常直观的体感。它值得你花上一个周末。
Redis源码解析：Rax树——压缩前缀树的变体与实现
那次我在翻Redis Streams的源码想知道消费者组名字到底存在哪里。顺着结构体一路找过去看到一个叫rax的东西。第一反应是哦Radix Tree嘛前缀树但越看越不对劲——它的节点居然能在路径中间直接挂一个值而且压缩节点能压住一整段字符串。这不是我熟悉的那个经典Radix Tree而是antirez单独造的一个变体。后来我花了一整个下午把rax.c和rax.h啃了一遍又把插入、删除、迭代器的行为用随机数据跑了几轮才算真正摸清它的实现逻辑。这篇就当作系列里的第25章把Rax树从数据结构定义到核心算法完整拆开讲一遍。适合正在学数据结构的人、想读Redis源码但卡在rax这一块的人以及任何需要实现字符串前缀索引的工程师——它比你自己用Trie魔改要成熟得多。1. 为什么需要Rax从Trie到压缩前缀树的演进1.1 我是在哪里遇到它的先说结论Rax是Redis作者自己写的通用数据结构本质是一棵压缩前缀树。我在Redis Streams的源码里见到它时它承担的是字符串关联存储的任务——比如消费者组名称到游标信息的映射。这类数据和普通的字典不一样它有明显的前缀复用group-a、group-b、group-abc这些key共享group-这一段。如果用哈希表所有前缀信息全被打散你想按前缀遍历根本做不到。如果用普通Triekey之间的公共前缀会被拆成一长串单字符节点路径很长、内存很碎。Rax则把公共前缀压进同一个节点里让前缀匹配和有序遍历都变得很自然。这也是我建议每个研究数据结构的人都读一遍rax.c的原因它展示了一个真实的高性能索引结构如何平衡查询效率、内存占用和实现复杂度比教科书里的示例代码完整得多。1.2 Trie的问题与Radix Tree的压缩思路教科书里的Trie是逐字符分叉的。插入hello和help前三个字符hel会形成三条单独的路径每个节点只存一个字符。这种做法在字符集很大时尤其浪费每个节点还要为子节点维护一个指针集合要么开256个槽位的定长数组要么用一个哈希表这两种方案要么内存爆炸要么多一层哈希计算。Radix Tree把连续的单子节点路径压成一个节点节点里存一段字符串而不是单个字符。比如hello和help共享的hel就变成一个节点后面分出p和lo两个分支。这样做的好处很明显单个路径的深度大幅下降查找时可以跳过整段字符的比较内存也不再为一个字符分配一个节点头。但经典Radix Tree有个尴尬之处值通常只能存在叶子节点。如果我想同时保存foo1和foobar2经典做法要么把foo继续扩展成一个子路径要么额外做规则约定。因为中间节点默认不承担值的角色你没法自然表达这个字符串本身也是一个key。1.3 三张对照表结构节点存储内容值的存放位置前缀查询典型问题Trie单个字符一般挂在叶子支持但不高效路径深、内存碎经典Radix Tree压缩后的字符串段通常只在叶子支持中间key表达困难Rax压缩后的字符串段任意节点都可存支持且高效实现复杂度较高Rax的关键就是在Radix Tree的压缩思想上给每个节点加了iskey标记。某个压缩路径的中间位置如果恰好是一个完整key直接在该节点上挂值即可。真正需要拆开的时候插入算法再把节点分裂成两段。这个任意节点可存值的设计让Rax变成了一个既能前缀匹配、又能存储任意key-value的有序字典。我第一次看到iskey字段时觉得不过是一个布尔位后来自己动手实现类似结构才发现就是这个字段重新定义了整棵树的写入逻辑——插入、分裂、删除合并全部要围着它转。2. 内存布局拆解raxNode的位域与柔性数组2.1 一个node节点到底长什么样想要理解Rax的算法先得把raxNode的内存布局刻在脑子里。它是整个实现的地基。typedef struct raxNode { uint32_t iskey:1; /* 当前节点是否存有一个完整的key */ uint32_t isnull:1; /* 存的value是否为NULL */ uint32_t iscompr:1; /* 是否为压缩节点 */ uint32_t size:29; /* 压缩路径长度或子节点个数 */ unsigned char data[]; } raxNode;这里用位域把头部压缩到了4字节四个核心标记塞进一个uint32_t。size字段有29位理论上单个节点最多存2^29个字符或子节点这个上限在实际内存中都碰不到所以可以放心。data[]是一个柔性数组它不占结构体大小真正的数据全部跟在头部后面。这就是为什么你不能把raxNode当成一个定长结构体来看——你拿到的是一个不完整的头具体内容要靠字段自己推断。2.2 压缩和非压缩节点的两种内存排布Rax的节点分两种形态每种形态的data[]排布完全不同。非压缩节点是标准的分岔口形态size表示子节点个数。它的data里先连续铺size个字符代表每个子分支的字符字符之后紧跟size个void*指针每个指针对应前面对应字符的子节点如果iskey为1指针后面还会有一个8字节的值指针。压缩节点则是单行道形态size表示路径字符串的长度。它的data里先铺size个字符的路径内容之后只有一个void*子节点指针如果iskey为1末尾同样多一个值指针。为什么非压缩节点要把字符数组和指针数组分开铺直接每个字符后面跟一个指针不是更直观吗这样做是为了缓存友好。查找时逐个字符比较字符在内存中是连续的一段CPU能一次加载很多字节确定分支后又要跳到对应指针。如果把字符和指针交错存放每次比较都要跨越指针跳跃缓存命中率会明显下降。2.3 指针偏移计算的坑这里我要提醒你一个非常容易踩的坑压缩节点后面那个子节点指针不是简单地从data size位置取的。因为指针需要按8字节对齐而压缩路径的字符串长度是任意的你必须在路径结尾处做一次对齐向上取整。/* 压缩节点子节点指针的起始位置需要对齐到8字节 */ child_ptr (raxNode**) ((unsigned char *)node-data node-size 7 ~(size_t)7);我第一次读源码时没留意这个细节自己照着data size直接取指针结果在长度为奇数的那批节点上频繁拿到错地址查了一晚上才发现是对齐问题。以后你要是自己实现类似结构或者写raxNodeSize()这类辅助函数一定记得把对齐逻辑单独抽出来测试。3. 插入分裂Rax树最核心的写路径3.1 raxLowWalk先找到分歧点插入的第一步不是急着建节点而是沿着现有路径找到这个key会在哪里和已有路径分道扬镳。走查逻辑是从根节点开始的碰到压缩节点直接拿data里那段字符串与目标key逐字节比较碰到非压缩节点根据当前字符走对应的子指针。三种情况会结束这次走查第一种key的每个字符都匹配完最终落在一个已有节点上这时就是普通的值更新第二种key匹配完了但当前节点还有更长的路径那么新key是某个已有key的前缀需要在当前节点额外挂一个分支第三种某个字符匹配不上而且这个不相符的位置正好落在一个压缩节点的中间这才触发分裂。在代码里这个函数叫raxLowWalk它还会返回当前比较到的字节偏移。这也是为什么插入函数能准确知道该从哪里下手。3.2 分裂到底在做什么压缩节点只能有一个子节点这条路是单车道。现在要在这里分岔你就必须把这条单车道改造成一个岔路口。分裂的本质是把一段压缩字符串从分歧点切成两段。想象一个压缩节点原来存着字符串foobar后面带着一个子节点。现在要插入foobaz两个key在fooba处完全一致到r和z才分家。Rax会把原来的节点改造成一个只存fooba的压缩节点同时创建两个新的子节点一个存r继续保留原来foobar的value和后续子节点另一个存z挂上新插入的foobaz的value。这一步的关键在于分裂时原先节点的iskey、isnull、子节点指针、值指针都要按正确的位置重新安置。如果公共前缀本身就是一个完整key那么分裂后的新节点必须设置iskey如果原来被切掉的部分是一个key这个身份要转移到后缀节点上。一个比较绕的细节是分裂后的新节点和旧节点在内存里都是新建的旧节点实际上会被改造成后缀节点。你在代码里会看到raxSplit()函数它接收一个old节点指针然后返回新节点地址——如果你拿着旧指针继续访问极有可能读到被回收的内存。3.3 一个完整的插入过程演示我拿foo、foobar、foobaz这三个key走一遍过程你就能看到整棵树怎么一步步长起来的。初始时树是空的插入foo根节点就是一个压缩节点data里存foo设置iskey1挂上值1。此时树只有一个大字符串节点干净利落。插入foobar从根节点走查发现foobar的前三个字符foo完全匹配根节点的路径字符串但根节点路径到此结束而目标key还剩bar。于是根节点保持不变在它下面新挂一个子节点存字符串bar并在这个子节点上设置iskey1存值2。此时树是foo(value1) -bar(value2)。插入foobaz同样从根节点走查匹配完foo后进入子节点bar。比较子节点的路径字符串bar和剩余keybaz前两个字符ba一致到了r和z分叉。这个不匹配的位置落在bar这个压缩节点的中间于是触发分裂。分裂之后的结构是foo(value1) -ba(非key节点) -r(value2)以及ba-z(value3)。bar节点本身被改造成一个只包含ba的节点原来的r分支和value2都转移到新子节点上。看起来只是三个key实际上已经完整覆盖了普通插入、后缀追加、中途分裂三种情况。你拿这三组数据跑通之后Rax的写路径就基本没有盲区了。3.4 我调试插入逻辑时的经验我自己照着思路实现过一遍Rax的插入调试阶段最大的教训是分裂完成之后旧指针不能再用。Rax的分裂为了性能会复用旧节点内存分裂后它的语义已经变了你必须从父节点重新拿子节点指针。我一开始图省事在分裂后直接访问旧节点里的子节点指针结果一连串段错误。另外一个建议写一个校验函数递归检查整棵树的不变量。比如每个非压缩节点的子节点数量必须等于size每个压缩节点必须只有一个子节点所有节点的iskey标志和值指针是否一致。我后来靠这个校验函数几分钟就定位到了指针偏移错误比反复拿gdb打印节点高效得多。4. 查找与删除对称的读路径与回收逻辑4.1 raxFind的遍历策略查找比插入简单得多核心就是顺着压缩边一路对比下去。从根节点开始对每个压缩节点直接比对整段路径字符串如果完全匹配继续深入唯一子节点如果中间某个字符不匹配立即返回未找到。对非压缩节点取当前字符直接通过字符索引跳到对应子节点如果没有这个字符同样返回未找到。这个策略最好的地方在于压缩节点把多次字符比较合并成一段连续内存的比较。现代CPU对连续内存的扫描速度非常快而且你跳过的是一整段节点指针寻址次数大幅减少。最理想情况下查找一个长key只需要访问key_length / 平均压缩长度个节点。你可以这样验证插入10万个带公共前缀的随机字符串然后对比raxFind和哈希表的点查速度。哈希表可能稍快一点因为它的常数小但Rax的差距通常在一个数量级以内而且它还额外支持前缀遍历——这是哈希表完全做不到的。4.2 删除时如何收敛合并是分裂的逆操作删除逻辑是Rax里我个人认为最需要小心的部分因为它在删除节点之外还会可能做一次压缩合并。删除一个key的基本步骤是先走查找到对应节点把该节点的iskey清掉并释放值指针。但如果这个节点同时还有子节点说明它只是一个路径中间的路过者比如foo这个key被删掉时它下面还挂着bar分支这时只清iskey就够了节点本身必须保留。麻烦的是另一种情况节点没有子节点了它变成纯叶子。这时要把这个叶子从父节点摘除。摘除之后父节点如果恰好只有一个子节点并且父节点本身不是key就满足合并条件——把父节点和唯一子节点拼接成一个更长的压缩节点。这就是分裂的逆操作。合并时要小心iskey的归属。假设父节点不是key但子节点是key合并后的新节点必须继承子节点的iskey标志和值指针。如果两边都不是key合并后的节点就保持非key状态。这个过程我建议写4到6个用例专门覆盖删除叶子、删除中间key、删除后触发合并、删除根节点使树为空。一次跑完这些边界基本就稳了。4.3 删除实现中容易被忽略的边界我在实现中吃过两次亏都出在边界。第一次是删除一个中间key之后没有及时检查父节点是否需要合并。结果是树里留下一个退化的压缩节点一个非key节点只有一个子节点本来可以直接合并成一个更长的字符串却硬生生多了一层指针跳转。树还是对的但性能和压缩的初衷背道而驰。第二次是处理isnull。Rax里如果存储的value本身就是NULL内存里不一定分配那个指针空间而是靠isnull标记。删除时如果只清iskey忘了处理isnull对应的指针分配状态再插入同一个key时就会遇到该释放的没释放、该分配的被跳过的错乱。我的建议是删除和插入共用同一套节点状态转换逻辑别在两边各写一套否则状态组合一旦多起来很容易漏掉某一支。5. 迭代器与遍历有序输出所有key5.1 迭代器的栈式路径记录Rax的节点不存父指针所以它设计了一个迭代器来处理遍历。raxIterator内部维护一个栈栈里保存的是从根节点到当前节点的完整路径。每次访问一个节点就把当前节点和这个节点上匹配到的字符偏移压入栈中需要回溯时从栈里弹出节点继续寻找下一个未访问的分支。这里有一个非常容易被初学者忽略的点raxNext返回的key不是从节点上直接拿字符串拼出来的而是迭代器通过对栈里所有路径片段做累加拼接得到的。因为每个节点都可能存一段多个字符的字符串你必须把栈上每一段的data内容按顺序合并。这个拼接逻辑本身不复杂但你需要保证迭代器的当前节点与栈顶状态一致否则在压缩节点上移动一步栈里的拼出来的key就会错位。5.2 迭代器上的三个常用操作迭代器通常有三个核心操作要配合使用。raxSeek负责定位它可以把迭代器移动到某个精确key上也可以移动到第一个大于等于目标key的位置。这个能力是范围遍历的基础。raxNext和raxPrev负责单调遍历。raxNext会从当前位置出发按中序找到下一个比当前key大的节点。如果你把raxSeek定位到最小key然后反复调用raxNext就能按字典序输出全树所有key。raxStop则负责回收迭代器内部的动态缓冲区。如果你是嵌入式环境或者对内存峰值敏感一定要在遍历完成后及时调用它别依赖GC。一个实用的技巧是用迭代器把整棵树遍历一遍收集所有key再和插入前的原始数组排序后的结果做一次全等对比。这个测试能同时验证迭代器正确性、插入正确性和树结构完整性比任何单元测试都高效。5.3 用迭代器写一个随机验证脚本我建议你上手之后至少跑一遍下面的流程我自己就是这么验证Rax实现的先生成10万条随机字符串作为测试集然后依次插入Rax树。插入完毕后用迭代器从头到尾把所有key收集出来做两个断言第一集合大小必须等于插入数据的总数不能有重复或丢失第二迭代器输出的key序列必须和排序后的原始数组完全一致。最后再随机删除其中3万条key再次迭代遍历确认剩下的key仍然有序且数量正确。这个脚本看起来简单但能一次性暴露出寻址错误、合并逻辑错误和迭代器状态错乱这三个最常见的实现bug。我在自己的实现里头一轮就跑出20多个assert失败几乎全集中在对齐和合并这两个地方。把这些坑填平之后整棵树的稳定性才算真正过关。6. 生产环境的应用与选型建议6.1 Rax在Redis里的具体工作Rax不是理论玩具它在Redis里有实际落地的场景。我最初就是在Streams模块里碰到它的消费者组相关的字符串元数据需要按组名做快速查找也经常需要按前缀或顺序遍历。这个需求用哈希表太散用普通Trie太碎Rax正好卡在两者之间。Rax在Redis里承担的角色本质上是一个有序字符串字典既有dict一样的点查效率又能像跳表一样顺序遍历。如果你需要给某个系统设计一个带前缀查询的KV存储Rax的实现思路可以直接抄。6.2 什么时候该用Rax什么时候别用先说适合的场景。第一key是字符串而且存在明显的公共前缀——比如URL、路径、命令行补全词表这类数据用Rax能获得极高的压缩率。第二你需要同时支持精确查找和前缀扫描比如输入foo自动联想出foo开头的全部key。第三你的数据量在千万级别以下且内存常驻——Rax是纯内存结构。不适合的场景也有。第一你的key是随机分布的前缀复用了了无Rax的压缩优势完全体现不出来这时候一个简单的哈希表加一个跳表配合效果反而更容易控制。第二数据量超大且需要落盘Rax没有就地序列化和磁盘页结构你要持久化它得自己设计格式这时候B树或LSM树更合适。第三你只需要范围数值查询而不关心字符串前缀——Rax对数值类型没有天然的压缩优势用skiplist或B树更顺手。最后说一个我最常被问到的问题Rax和B树到底哪个好如果你是在内存里做动态字符串索引Rax的结构更轻、实现更直接而且前缀遍历是天生的能力。B树强在磁盘存储上节点大小和页对齐深度绑定纯内存场景优势不明显。一些题外话我读rax.c最大的收获不是记住那些宏和指针偏移而是看到一个工程上成熟的结构如何被隔离出来。它的分裂和合并逻辑放在任何一棵树上都是一样的思路——但加上了任意节点可存值这个约束之后所有细节都微妙地变了。真正的经验不会写在教科书里只会藏在这些边界处理和一眼看不太懂的对齐宏里。如果你想动手验证我建议把Redis源码里的rax.c和rax.h拎出来写个简单的包装替换掉rax_malloc相关函数然后跑一遍我上面说的随机插入、遍历、删除测试。这个工程量不大但跑通之后你对于前缀树到底能优化到什么程度会有非常直观的体感。它值得你花上一个周末。