字典树
字典树 (Trie) 这一概念有时候会跟基数树 (Radix Tree)、前缀树(Prefix Tree) 等混用。其中前缀树、字典树是从字符串存储角度的称呼，基数树更多是从数值 (多为二进制) 角度的称呼，可以看作广义的字典树。以下以字典树来统称字典树和基数树。
关于字典树的介绍，前面的文章 有一个直观的介绍，也不多赘述。
功能对比
| 数据结构 | 增加 | 删除 | 精确查找 | 极值查找 | 顺序遍历 | 前缀遍历 | 数据约束 |
|---|---|---|---|---|---|---|---|
| 哈希表 | √ | √ | √ | 哈希函数; 等于比较 | |||
| 堆 | √ | √ | √ | 小于比较 | |||
| 平衡树 | √ | √ | √ | √ | √ | √ | 小于比较 |
| 字典树 | √ | √ | √ | √ | √ | √ | 二进制比较(字符比较) |
基础版本字典树的特点：
- 查询时间只和 key 长度有关，和树中的节点数量无关
- 设每个字符长度是 s bits，一个 key 长度是 k bits，最多只需要比较 k / s 个 node
不足：
- 基本只适用于基本数据(整数，字符串、二进制串)
- 很难像哈希表或者平衡树那样，通过自定义哈希函数或者比较函数来存储自定义类型
字典树的优化方向：
- 减少内存 overhead(减少节点大小、分支数量、节点层数)
- 缓存友好
常规优化
还是主要参见前面介绍 HAT 的文章。主要有:
- 字母表缩减。可以看作基数树换用更小的基数。代价是树的深度变大，速度慢。
- 使用关联容器。代价是每次索引运算量增大。
- 压缩字典树。把只有一个分叉的节点，连同其唯一的孩子，结合成一个节点。可以通过插入过程中分裂节点来实现：
PATRICIA trie 及其变体
PATRICIA trie，是一种特殊的字典树，每个中间节点记录 key 之间公共前缀的位置。从此位置之后，key 之间产生不同，根据接下来的不同字符，转到不同的子分支。
Critial Bit trie
从基数树的角度看，PATRICIA trie 最简单的一个实现是二进制的，即 Critial Bit trie(cb trie)。critical bit 的意思是两个串共同前缀分叉之处的比特。参见: https://cr.yp.to/critbit.html (这个作者对 cb trie 的吹捧，说实话有点过了)。
两种节点类型：
- 中间节点：存储 critical-bit 的位置，以及左右两个子树
- 叶子结点：存储整个串
构造流程（采用网上某个介绍进行了修改）：
empty -- initial state
---------------------------------------------------
01234 -- number bit positions
insert 01011 -- the key
result root ----> 01011
---------------------------------------------------
insert 01010
search ends at 01011~=01010;
1st difference is at position 4, so...
result root ----> [4] -- i.e. test position #4
. .
0. .1
. .
01010 01001
---------------------------------------------------
insert 10
has no position #4;
can skip key positions but must test in order, so...
result root ----> [0] -- i.e. test position #0
. .
0. .1
. .
[4] 10
. .
0. .1
. .
01010 01011
---------------------------------------------------
insert 000110;
search ends at 01011~=000110;
can skip key positions but must test in order, so...
result root ----> [0]
. .
0. .1
. .
[1] 10
. .
0. .1
. .
000110 [4]
. .
0. .1
. .
01010 01011
---------------------------------------------------
insert 01;
01 is also a prefix of 01010 and 01011;
must have ability to terminate at an intermediate node, as with Tries.
result root ----> [0]
. .
0. .1
. .
[1] 10
. .
0. .1
. .
000110 [2] ---> 01
.
0.
.
[4]
. .
0. .1
. .
01010 01011
quelques-bits popcount trie
为了减少 cb trie 的深度，采用 4 比特一组进行比较。即，基数树以 2 的 4 次方等于 16 为基数。二叉树 ->16 叉树。同时，采用了位运算来压缩数组，减少了节点大小。quelques-bits popcount trie 简写为 QP Trie. 参见：https://dotat.at/prog/qp/README.html
构造过程和 CB Trie 类似：
insert keys:
"foo" -> hex str: "6 6 6 f 6 f"
"bar" -> hex str: "6 2 6 1 7 2"
"baz" -> hex str: "6 2 6 1 7 a"
"hax" -> hex str: "6 8 6 1 7 8"
result root ----> [1]
. . .
2. 6. 8. ---> "hax"
. .
[5] . ---> "foo"
. .
2. .a
"bar" <--- . .---> "baz"
减少空间占用：用位图压缩子树数组
以此为例：[1]
. . .
2. 6. 8. ---> "hax"
该节点保存有位图:
bitmap: 0000000101000100
index: fedcba9876543210
正常情况我们需要一个大小为 16 的数组，其下标 2、6、8 分别指向对应的子数。我们压缩子树数组为：vector[3]
映射：vector[0] -> '2' 所在子树
vector[1] -> '6' 所在子树
vector[2] -> '8' 所在子树
查询算法：设要查询 i 位置的子树，mask = 1 << i;
if(bitmap & mask)
member = vector[popcount(bitmap & mask-1)]
例如 i = 8,
popcount(bitmap & mask - 1) = popcount(0000000101000100 & 0000000001111111)
= popcount(0000000001000100)
= 2
因此 vector[2]就是 '8' 所在的子树
HAT trie
参见前面关于 HAT trie 的文章。
Adaptive Radix Tree
自适应的基数树。Adaptive Radix Tree。参见: https://db.in.tum.de/~leis/papers/ART.pdf
存在 4 种不同类型和大小的节点。根据实际某个节点的子树数量，自适应的改变 node 类型：
union Node {
Node4* n4;
Node16* n16;
Node48* n48;
Node256* n256;
}
关于其如何存储 k -v，这里不作介绍。
Node4
因为子树数量较少，直接 for 循环比较查找子树：
struct Node4 {char child_keys[4];
Node* child_pointers[4];
}
Node* find_child(char c, Node4* node) {
Node* ret = NULL;
for (int i = 0; i < 4; ++i) {if (child_keys[i] == c) ret = node->child_pointers[i];
}
return ret;
}
Node16
struct Node16 {char child_keys[16];
Node* child_pointers[16];
byte num_children;
}
可以采用 SIMD 进行并行加速查找：
// Find the child in `node` that matches `c` by examining all child nodes, in parallel.
Node* find_child(char c, Node16* node) {
// key_vec is 16 repeated copies of the searched-for byte, one for every possible position
// in child_keys that needs to be searched.
__mm128i key_vec = _mm_set1_epi8(c);
// Compare all child_keys to 'c' in parallel. Don't worry if some of the keys aren't valid,
// we'll mask the results to only consider the valid ones below.
__mm128i results = _mm_cmpeq_epi8(key_vec, node->child_keys);
// Build a mask to select only the first node->num_children values from the comparison
// (because the other values are meaningless)
int mask = (1 << node->num_children) - 1;
// Change the results of the comparison into a bitfield, masking off any invalid comparisons.
int bitfield = _mm_movemask_epi8(results) & mask;
// No match if there are no '1's in the bitfield.
if (bitfield == 0) return NULL;
// Find the index of the first '1' in the bitfield by counting the leading zeros.
int idx = ctz(bitfield);
return node->child_pointers[idx];
}
Node48
struct Node48 {
// Indexed by the key value, i.e. the child pointer for 'f'
// is at child_ptrs[child_ptr_indexes['f']]
char child_ptr_indexes[256];
Node* child_ptrs[48];
char num_children;
}
48 个子树的数量，遍历等查找较慢，此时做了一个空间和查找速度的折中（可以对比 Node256）。
Node* find_child(char c, Node48* node) {int idx = node->child_ptr_indexes[c];
if (idx == -1) return NULL;
return node->child_ptrs[idx];
}
Node256
这个就是最原始的做法
struct Node256 {Node* child_ptrs[256];
}
Node* find_child(char c, Node256* node) {return child_ptrs[c];
}
两种优化措施
两种优化：延迟展开、路径压缩，基本类似于最前面讲到的压缩字典树。
字典树的应用
字典树的应用也是非常广泛，这里举几个有代表性的例子，以后有时间会增加更多例子，以及对某些场景做进一步分析学习。
DNS(域名数据库、IP 地址库)
DNS 服务器中，通常有两个地方用到字典树：域名数据库和 IP 地址库。
互联网中的域名是一个层级结构的字符串，天生适合用字典树存储：
在 Knot DNS Server 中，采用了 QP Trie 作为域名的存储方案：https://github.com/CZ-NIC/knot/tree/master/src/contrib/qp-trie (早些时候的版本采用的是 HAT trie)。
IP 地址库，一般由许多条 IP 地址段(CIDR), 位置(地理区域，服务商) 的记录组成。在权威 DNS 服务器中，用作 EDNS 进行基于地理位置的解析(geoip); 在 Cache DNS 中，用于缓存各权威服务的地址段。
在 Knot 中采用的 QP trie 实现了权威服务的 geoip:(https://github.com/CZ-NIC/knot/blob/master/src/knot/modules/geoip/geoip.c)、在 Unbound 中，采用类似 CB trie 做了 EDNS 缓存(https://github.com/NLnetLabs/unbound/blob/master/edns-subnet/addrtree.c)
路由表
路由表的存储、查找算法，经过持续不断的优化，目前可以说五花八门。由于路由表的特性，基于字典树的实现是其中有代表性的一大类。目前 linux 系统可以查看到按字典树组织路由表：
$ cat /proc/net/fib_trie
Main:
+-- 0.0.0.0/0 3 0 5
|-- 0.0.0.0
/0 universe UNICAST
+-- 127.0.0.0/8 2 0 2
+-- 127.0.0.0/31 1 0 0
|-- 127.0.0.0
/32 link BROADCAST
/8 host LOCAL
|-- 127.0.0.1
/32 host LOCAL
|-- 127.255.255.255
/32 link BROADCAST
+-- 192.168.2.0/24 2 0 1
|-- 192.168.2.0
/32 link BROADCAST
/24 link UNICAST
|-- 192.168.2.110
/32 host LOCAL
|-- 192.168.2.255
/32 link BROADCAST
Local:
+-- 0.0.0.0/0 3 0 5
|-- 0.0.0.0
/0 universe UNICAST
+-- 127.0.0.0/8 2 0 2
+-- 127.0.0.0/31 1 0 0
|-- 127.0.0.0
/32 link BROADCAST
/8 host LOCAL
|-- 127.0.0.1
/32 host LOCAL
|-- 127.255.255.255
/32 link BROADCAST
+-- 192.168.2.0/24 2 0 1
|-- 192.168.2.0
/32 link BROADCAST
/24 link UNICAST
|-- 192.168.2.110
/32 host LOCAL
|-- 192.168.2.255
/32 link BROADCAST
linux IDR
使用字典树，维护整数 id 到指针的映射。
IDR 把每一个 ID 分级数据进行管理，每一级维护着 ID 的 5 位数据，这样就可以把 IDR 分为 7 级进行管理（5*7=35，维 护的数据大于 32 位），如下所示：
31 30 | 29 28 27 26 25 | 24 23 22 21 20 | 19 18 17 16 15 | 14 13 12 11 10 | 9 8 7 6 5 | 4 3 2 1 0
例如数据 ID 为0B 10 11111 10011 00111 11001 100001 00001，寻址如下
第一级寻址 ary1[0b10]得到第二级地址 ary2[]
ary3 = ary2[0b11111]
ary4 = ary3[0b10011]
ary5 = ary4[0b00111]
ary6 = ary5[0b11001]
ary7 = ary6[0b100001]
ary8 = ary7[0b00001]