区块头中有一个Merkle Root的字段保存了交易列表的默克尔树根的哈希，为了计算这个值需要消耗大量的计算资源，回想一下默克尔树的根哈希计算方法，当一个区块的交易达到两三千笔的时候，两两计算哈希直到默克尔树根哈希的计算量是多么的庞大。如果刚计算完成得到根哈希，这时区块中的一笔交易由于一些原因发生了变化又需要从头开始计算。比如收到了一个新区块，新区块的交易和自己打包的交易有少量重叠，这时需要替换这些重叠交易重新计算根哈希。
默克尔树还有一个缺点，叶子节点的内容没有发生改变，但是次序发生变化得到的根哈希又不一致。
如果我们用哈希表，链表，数组之类的数据结构存储默克尔树的叶子节点就不可避免的出现上面的问题，为此就需要设计一种数据结构，在存储数据发生改变的时候尽可能少的计算哈希，还要避免相同内容次序不同致导致的根哈希不一致的问题。
为此引入了一种新的数据结构字典树。
字典树（Trie）又称前缀树，是一种有序树，用于保存关联数据，存储的数据通常是字符串。与二叉查找树不同，数据不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所才有存储相关的数据。
下图是一颗典型的字典树；
图中字典树树存储了一些字符串，蓝色的是关键字，存储的字符串由关键字组成。存储了"a", "to", "tea", "ted", "ten", "i", "in", "inn"。 前缀树有这些特点；
- 根节点不包含字符，其他节点各包含一个字符；
- 关键路径节点的字符连接起来为该节点所存储的数据；
关键路径就是每个节点有一个标志位，用来标记这个节点是否作为构成数据的一部分，上图中的，t, e 节点就不是关键路径。
字典树利用了词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历，从而达到高效检索的目的。使数据的前后位置按照字典序得以保证，这对于区块链来说是一个非常重要的特性，相同的数据不同的顺序会生成不同的根哈希，会误认为数据发生了变化，实际上数据本身没有改变，只是顺序发生了改变而已。
对于区块链来说，另一个更重要的特性就是如果字典树叶上的数据发生了变化，只需要计算树叶到根路径上的哈希即可，避免了全量的哈希计算，极大的减少了生成根哈希的计算量。
字典树在带来便利的同时也付出了一些代价，由于结构需要记录更多的信息，因此字典树在实现稍显复杂，同时字典树在构建时必须对每个词和字逐一进行处理来构建关键路径，无法并行的操作无疑会减慢词典的构建速度。虽然相较于哈希表，插入和查询速度略逊一筹，但是trie的插入和查询的效率依然算是非常高效的，都是O(m)，m是插入或查询字符串的长度，因此其设计哲学是典型的“以空间换时间”。
除此之外字典树还在这些场景有广泛的应用；
- 但词频次统计。
- 字符串匹配。
- 字符串字典序排序。
- 前缀匹配，比如一些搜索框的自动提示。
在字典树中很多节点只是为了存储前缀而存在，当路径上只有一个关键字的时候，这些只为存储前缀存在的节点就显得非常冗余。压缩字典树在字典树的基础之上做了一些优化，具体可以看下图；
图中黑色的是关键路径，存储了字符串"abc"和"d"，可以明显看到压缩后的前缀树占用了更小的空间。