一、MPT
默克尔帕特里夏树(Merkle Patricia tree/trie),由Alan Reiner提出设想，并在瑞波协议中得到实现，是以太坊的主要数据结构，用于存储所有账户状态，以及每个区块中的交易和收据数据。
MPT是结合了Merkle Tree（默克尔树）和 Patricia Tree（帕特里夏树）的一种数据结构。
1、MT
Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash值。
在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。
采用默克尔树的好处是可以方便的判断一个交易是否在区块中，比如我们将数据块L4下载下来了，那么我们如何验证L4是否是合法且完整的数据块？
我们只需要三个步骤：
第一、算出L4的哈希值（hash 1-1）。
第二、将L4的哈希值和已知的L3（hash 1-0）的哈希值做运算得到哈希值hash1
第三、将已知的hash0和hash1做运算得到Tophash。
最后我们用计算得到的tophash和已知的tophash做比较，如果一样则L4合法且完整。
这样的一个校验过程比起将所有的数据块的哈希值重新运算一遍还是显得优化了很多。
2、PT
帕特里夏树可称为压缩前缀树，解决的是存储效率的问题，如上图，有相同的前缀的字符串在同一分支中，再将不同的部分分叉出来，如test和toast，都有相同的t，再分叉出est和oast两个部分。这个结构的好处是节省空间，因为每一级的键值可以是多个字符。
比如有一棵存储键值对的树，但其中的键长度有几百字符长，那么每个字符的那个层级你都需要大量的额外空间。每次查找和删除都会有上百个步骤。在这里我们引入Patricia树就让这个问题便的简单了。
3、MPT
在以太坊（ethereum）中，使用了一种特殊的十六进制前缀(hex-prefix, HP)编码，所以在字母表中就有16个字符。这其中的一个字符为一个nibble。
MPT树中的节点有四种类型：空节点、叶子节点、扩展节点和分支节点。
空节点，简单的表示空，在代码中是一个空串。
叶子节点（leaf），表示为[key,value]的一个键值对，其中key是key的一种特殊十六进制编码，value是value的RLP编码。
扩展节点（extension），也是[key，value]的一个键值对，但是这里的value是其他节点的hash值，这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。
分支节点（branch），因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。
MPT树中另外一个重要的概念是一个特殊的十六进制前缀(hex-prefix, HP)编码，用来对key进行编码。因为字母表是16进制的，所以每个节点可能有16个孩子。因为有两种[key,value]节点(叶节点和扩展节点)，引进一种特殊的终止符标识来标识key所对应的是值是真实的值，还是其他节点的hash。如果终止符标记被打开，那么key对应的是叶节点，对应的值是真实的value。如果终止符标记被关闭，那么值就是用于在数据块中查询对应的节点的hash。无论key奇数长度还是偶数长度，HP都可以对其进行编码。最后我们注意到一个单独的hex字符或者4bit二进制数字，即一个nibble。
HP编码很简单。一个nibble被加到key前（下图中的prefix），对终止符的状态和奇偶性进行编码。最低位表示奇偶性，第二低位编码终止符状态。如果key是偶数长度，那么加上另外一个nibble，值为0来保持整体的偶特性。
十六进制前缀(Hex-Prefix)编码如图所示：
下面是MPT的一个示例。
下面挨个节点进行解析。
1.、根节点
因为4组数据都有公共的6，所以这个节点的值为6，长度为1，奇数；节点类型：扩展节点；所以前缀就是0001，即1。
这是个扩展节点，它的值是一个Hashvalue，它指向一个分支节点。Hashvalue，具体指的是分支节点RLP编码的结果的散列值。
2、分支节点
上面4组数据的第2位是4和8两种情况。在4的位置上存的是下面的扩展节点的散列值，在8的位置上存的是下面的叶子节点的散列值。
3.、叶子节点
以68开头的只有一个了。所以这个节点上的四元组就是68后面的数字6f727365了。长度为8，为偶数。前缀是0x20。这个叶子节点的value存储了'stallion'。
4.、扩展节点
在64之后，公共的部分是6f，这个扩展节点的key即为6f，前缀为0000，即00。这个扩展节点的value存放的是一个hashvalue，指向下一个节点，一个分支节点。
5.、分支节点
646f已经表达完，这个节点的value值就是646f对应的值，'verb'。
除此之外，646f之后就是6，所以在这个分支节点的6位置上有一个散列值，指向下一个节点。
6、扩展节点
在646f6之后，公共的部分是7，其长度为1，奇数。所以前缀为0001。这个节点的value是一个散列值，指向下一个节点。
7、分支节点
646f67已经表达完，这个节点的value值就是646f67对应的值，'puppy'。
除此之外，646f67之后就是6，所以在这个分支节点的6位置上有一个散列值，指向下一个节点。
8、叶子节点
key为5，value为'coin'。长度为1，奇数，前缀0011，即3。
整个分析过程结束。
这个小节呈现了MPT的整体轮廓，下一小节专门讲解PLP编码，看它是如何对字符串及其列表进行序列化的。
