Radix树

树(Trie) 是计算机科学领域的专有名词 [1] ,有时候也是用 Tree 来替代,这两者基本是同义词。

换句话说,树是有组织的数据结构,用来存储经常动态变化的数据,单条数据是一个键值对(key-value pairs),键的构成是一个字符串,见图 4-1

../_images/Picture27.png

树由树根,树内节点与叶子节点组成

树的结构中常见的名词解释如下。

  • node 节点:用圆圈表示,节点包含键、值、与指向后继节点的路径。
  • root 树根:树的起始节点,一棵树有且仅有一个树根。
  • leaf 树叶:树的最下层末梢节点,再无后继节点。
  • internal node 内部节点: 树中间的节点,承上启下,在上层与后继都有节点。
  • Path 路径:连结两个节点之间的直线,可以是双向箭头,也可以是单向箭头。

最常见的树结构就是 二叉树 ,每个节点最多两个后继节点,称为左右“孩子”。 从上往下层层遍历可以快速找到需要的值,一般在 N 个值中查找的复杂度在 log2(N) 范围内,相比于列表的 N 线性查找速度快很多。 二叉树有很多变种,其中有名的 MySQL 数据库采用了改良后的 B+树 结构,查找百万级的数据规模仅需最多遍历三层就能命中,将读取效率发挥到极致。

那什么是 Radix树呢?

首先,我们构造一个JSON数据集如下:

一个样板JSON数据集
{
  "do": 0,
  "dog": 1,
  "dax": 2,
  "dogu": 3,
  "dodo": 4,
  "house": 5,
  "houses": 6
}

如何高效地搜索一个字符串在数据集中所对应的最终值?我们可以构建一棵树来表示该数据集。Radix树 (Radix Trie)是利用树状结构对于搜索进行优化的树。

将这个数据集的键(例如 dog)和值(例如 0)按照 Radix 树状结构组织起来,就是图 4-2 所示的结构, 值存储于节点中,键的存储拆分开存在树的路径中。 当查找 dodo 的值时候,仅需要从根节点开始,向下遍历三层,依次找到 d-o-d-o 四个字母即可,它对应的值是 4 。 这棵树中间键无对应值的节点的存储空间里是 null

../_images/Picture28.png

Radix Trie树存储简单的键值对数据集

如果我们仔细观察上述的树结构,发现右边有一个特别长的键链条 h-o-u-s-e-s ,它并不分叉,而是一条直线,从上到下连接节点。 这时候我们说树的性能产生了 “退化” ,变成了一维数组的遍历(性能从log2(N)变成了N)。

在遍历的路上,树中节点的值都是 null ,直到 e-s 位置才有了值 5 和 6 。 这不但是搜索效率的下降,从 log2(N) 退化到了 O(N),而且无值中间节点的堆积也是对存储空间的浪费。 所以我们对它进行改进,让有且仅有一个孩子节点的中间节点“合并路径”,这样搜索起来就快很多了,仅需两次向下搜索就可以找到 h-o-u-s-e-s,如图 4-3 所示。

../_images/Picture29.png

改进后的Radix树,house路径缩短

至此,Radix树已经介绍完毕。

[1]笔者注:Trie和 Tree 是同音,在计算机学中特指带搜索性质的树状结构