Adaptive Trie Tree

Adaptive包括三个优化：

• 内部节点的自动伸缩

默认Trie树每个内部节点都有 \(2^{Layerbits}\) 个元素。自动伸缩的分配方式是指不按照每层的位宽分配，而是实现一个自动调整大小的内部节点。如果内部节点的使用率较低，这种策略能节省大量内存。对于比较长的Key(例如16字节的UUID)，大部分内部节点的使用率都很低。假定保存60亿个元素，裸的Key需要占用内存90GB 左右，这在当前系统上已经是很可观的了(现有计算机系统内存128GB~256GB是比较常见的)。60亿元素只需要33个位宽就可以构建唯一编址，相对于16字节(128位)的 Key，这个数据太小，因此内部节点使用率相当低。

• 内部节点折叠；

当Key的前缀(prefix)可以唯一描述Key时(没有相同的Prefix)，则不用继续伸展，而是在内部节点的对应位置标记Leaf，同时保存完整的Key。当后续有相同前缀的另一个Key插入时，检测到Leaf标记，则从这里拿到已经保存的KeyExist，与要插入的Key对比。如果两者相等则结束，否则扩展层级，直到两者的前缀不等，分别保存两个Key。我使用 KeyLen=16Byte, LayerBits=4 ，使用 /dev/urandom 作为随机源，插入3亿元素时树的高度为12或13(更大量的数据我的内存不足无法测试了)。

• 路径压缩

如果一个内部节点只有一个子节点，则可以移除这个内部节点。例如下面这个图示，可以移除内部节点A。

A              B              C
| |            | |     |----->|0| Leaf0
|1|-----|      | |            | |
| |     |      | |     |----->|2| Leaf1
| |     |----->|3|-----|      | |

论文测试数据证明每个节点平均耗费8.1字节空间。这个非常高效了。我目前版本只做了优化2内部节点折叠，Key是16字节UUID，每层4位，测试结果是每个节点耗费22字节。

16字节Key，每层4位，32层。