以太坊 Radix树
树（Trie） 是计算机科学领域的专有名词 [1] ，有时候也是用 Tree 来替代，这两者基本是同义词。
换句话说，树是有组织的数据结构，用来存储经常动态变化的数据，单条数据是一个键值对（key-value pairs），键的构成是一个字符串。
树由树根，树内节点与叶子节点组成
树的结构中常见的名词解释如下。
- node 节点：用圆圈表示，节点包含键、值、与指向后继节点的路径。
- root 树根：树的起始节点，一棵树有且仅有一个树根。
- leaf 树叶：树的最下层末梢节点，再无后继节点。
- internal node 内部节点: 树中间的节点，承上启下，在上层与后继都有节点。
- Path 路径：连结两个节点之间的直线，可以是双向箭头，也可以是单向箭头。
最常见的树结构就是 二叉树 ，每个节点最多两个后继节点，称为左右“孩子”。 从上往下层层遍历可以快速找到需要的值，一般在 N 个值中查找的复杂度在 log2(N) 范围内，相比于列表的 N 线性查找速度快很多。 二叉树有很多变种，其中有名的 MySQL 数据库采用了改良后的 B+树 结构，查找百万级的数据规模仅需最多遍历三层就能命中，将读取效率发挥到极致。
那什么是 Radix树呢？
首先，我们构造一个JSON数据集如下：
{
"do": 0,
"dog": 1,
"dax": 2,
"dogu": 3,
"dodo": 4,
"house": 5,
"houses": 6
}
如何高效地搜索一个字符串在数据集中所对应的最终值？我们可以构建一棵树来表示该数据集。Radix树 (Radix Trie)是利用树状结构对于搜索进行优化的树。
将这个数据集的键(例如 dog)和值(例如 0)按照 Radix 树状结构组织起来，如图所示的结构， 值存储于节点中，键的存储拆分开存在树的路径中。 当查找 dodo 的值时候，仅需要从根节点开始，向下遍历三层，依次找到 d-o-d-o 四个字母即可，它对应的值是 4 。 这棵树中间键无对应值的节点的存储空间里是 null 。
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，如图所示。
改进后的Radix树，house路径缩短
至此，Radix树已经介绍完毕。
| [1] | 笔者注：Trie和 Tree 是同音，在计算机学中特指带搜索性质的树状结构 |
数据完整性是通信协议需要考虑的基本问题之一。 数据存储于硬盘中、将在网络中传输，应时时刻刻保证数据的完整性。区块链程序更是如此。如果一组数据量不大的话，例如我们有 a_1、 a_2、 a_3 三个 ...