简介

Radix树的设计思想来自于DonaldR.Morrison于1968年提出的Patricia树（Practical Algorithm To Retrieve Information Coded In Alphanumeric），这是一种基于二进制表示的键值的查找树，尤其适合处理非常长的、可变长度的键值。

Patricia的基本思想是构建一个二叉树，在每个节点中都存储有在进行下一次bit测试之前需要跳过的bit数目，以此来避免单路分支。Patricia树一般由内部节点和外部节点组成，内部节点指示需要进行bit测试的位置，并根据bit测试结果决定查找操作前进的方向；外部节点用于存储键值，查找操作将于外部节点处终结。

BSD路由表使用的是Radix树。

操作步骤

BSD的Radix树中的路由查找操作分为3步：

第一步：Patricia查找，终结于某个叶子节点，判断该叶子节点是否与查找键相同。

第二步：如果找到的叶子节点无法与查找键匹配，则在这个叶子节点的重复键链表中寻找网络匹配的可能。

第三步：如果找到的叶子节点及其重复键与查找键不满足网络匹配条件，则向树顶回溯，继续寻找网络匹配的可能。