rax

Rax 是一个 radix 树实现，最初是为 Redis 中特定位置而编写的，以解决性能问题，但立即被转换为一个独立项目，使其可在 Redis 本身以及其他项目中重复使用，而不再局限于最初的应用场景。主要目标是寻找一个合适的性能和内存使用之间的平衡，同时提供一个功能齐全的 radix 树实现，可满足多种不同的需求。

在开发此库的过程中,我越来越兴奋地发现基数树是多么实用和适用,但我却非常惊讶地发现,要编写一个可靠的实现,尤其是一个具有灵活迭代器的全功能基数树,是多么困难。在节点分割、合并和各种边缘情况中,会出现很多问题。因此,项目的一个主要目标是为人们提供一个稳定且经过检验的实现,以供使用,并分享错误修复。该项目非常依赖漏洞测试技术,不仅要探索项目所包含的所有代码行,还要探索大量可能的状态。

Rax 是一个 开源 项目, 以 BSD 两项许可协议发布。

• 省内存:
  • 使用封装节点表示法。
  • 如果键设置为 NULL，则可以避免在节点中存储 NULL 指针（节点头中有一个 isnull 位）。
  • 没有父节点引用。如果需要，则使用栈代替。
• 快速查找:
  • 边被直接存储在父节点中，无需在尝试找到匹配项时访问不必要的子节点。这意味着相比其他实现，缓存失效的情况更少。
  • 使用两个分离的数组存储边，以便对正确的子节点进行缓存行友好的扫描：一个边字符数组和一个边指针数组。
• 完整实现:
  • 删除节点并根据需要重新压缩。
  • 迭代器（包括在树被修改时使用迭代器的方法）。
  • 随机漫步迭代。
  • 能够报告和抵御内存不足：如果 malloc() 返回 NULL，则程序会退出。