Radix Tree

定义 Definition

Radix tree（基数树/压缩前缀树）是一种用于高效存储与检索字符串或二进制键的树形数据结构。它是 trie（前缀树）的压缩版本：把只有一个子节点的连续路径合并成一条边，从而节省空间并加快查找（常用于路由表、字典索引、前缀匹配等）。
注：在不同语境中也常与 Patricia trie 相关联。

发音 Pronunciation (IPA)

/ˈreɪdɪks triː/

例句 Examples

We store URL paths in a radix tree.
我们把 URL 路径存储在基数树中。

To speed up prefix searches and reduce memory, the system uses a radix tree that compresses chains of single-child nodes into longer edge labels.
为了加速前缀检索并降低内存占用，该系统使用基数树，把只有一个子节点的链压缩为更长的边标签。

词源 Etymology

radix 源自拉丁语 rādīx，意为“根”；tree 来自古英语 trēow，意为“树”。“radix tree”字面含义可理解为“按根/基数组织的树”，在计算机科学中指一种以“共享前缀”为核心组织方式、并通过路径压缩来提高效率的树结构。

相关词 Related Words

• Trie
• Patricia
• Prefix
• Suffix
• String
• Index
• Hash
• Search

文献与作品 Literary / Notable Works

• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）：在检索与树结构相关主题中涉及前缀树及其变体思想。
• Algorithms on Strings, Trees, and Sequences（Dan Gusfield）：字符串算法中讨论前缀相关结构，常与压缩 trie / radix tree 的应用背景相连。
• “PATRICIA—Practical Algorithm To Retrieve Information Coded In Alphanumeric”（D. R. Morrison, 1968）：经典论文，提出与 radix tree 密切相关的 PATRICIA（压缩 trie）结构。