Radix Tree

张开发
• 2026/4/9 18:49:35 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

Radix Tree
Radix 树基数树是一种空间优化的前缀树Trie数据结构。它的核心思想是合并只有一个子节点的节点从而显著减少树的高度和节点总数。计算机对于Radix树的处理是以bit或二进制数字来读取的。一次被对比r个bit2的r次方是radix树的基数。这也是基数树的这个名字的由来。作为Key—Value 存储的模型的数据路由采用Hash表来达到目的。如何解决Hash冲突和Hash表大小的设计是一个很头疼的问题。借助于Radix树可以达到对于uint32_t 的数据类型的路由。Linux radix tree是将指针与long整数键值相关联的机制它存储有效率并且可快速查询用于指针与整数值的映射如IDR机制、内存管理等。IDRID Radix机制是将对象的身份鉴别号整数值ID与对象指针建立关联表完成从ID与指针之间的相互转换。IDR机制使用radix树状结构作为由id进行索引获取指针的稀疏数组通过使用位图可以快速分配新的IDIDR机制避免了使用固定尺寸的数组存放指针。IDR机制的API函数在lib/idr.c中实现。Linux radix树最广泛的用途是用于内存管理结构address_space通过radix树跟踪绑定到地址映射上的核心页该radix树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在lib/radix-tree.c中实现。radix树是通用的字典类型数据结构radix树又称为PAT位树Patricia Trie or crit bit tree。为什么需要 Radix 树标准 Trie每个字符一个节点可能产生大量“单链”节点浪费内存。Radix 树将单链压缩为边上的字符串片段每个节点至少有两个孩子叶子节点除外从而更加紧凑。基本操作插入沿树向下匹配边的字符串片段若部分匹配则分裂边。查找逐段比较若完全匹配且对应节点有结束标记则成功。删除反向操作可能合并节点。复杂度时间复杂度O(k)k 为键的长度与树节点数无关。空间复杂度比标准 Trie节省大量内存尤其是键有长公共前缀时。应用场景IP 路由表最著名的应用最长前缀匹配Linux 内核的struct fib_table自动补全 / 拼写检查特别是字典很大时键值存储Redis 的Rax模块一些嵌入式数据库HTTP 路由器如httprouter中使用的压缩动态路由树

更多文章