在以太坊中，有三棵树的说法，分别是状态数、收据树和交易树。
我们要实现从账户地址到账户状态的映射。在以太坊中，账户地址为160位，表示为40个16进制数。状态包含了余额（alance）、交易次数（nonce），合约账户中还包含了code（代码）、存储（storge）。
特点：
1. trie中每个节点的分支数目取决于Key值中每个元素的取值范围(图例中最多26个英文字母分叉+一个结束标志位)。
2. trie查找效率取决于key的长度。实际应用中（以太坊地址长度为160byte）。
3. 理论上哈希会出现碰撞，而trie上面不会发生碰撞。
4. 给定输入，无论如何顺序插入，构造的trie都是一样的。
5. 更新操作局部性较好
缺点
trie的存储浪费。很多节点只存储一个key，但其“儿子”只有一个，过于浪费。
Patricia trie就是进行了路径压缩的trie。如果新插入单词，原本压缩的路径可能需要扩展开来。树中插入的键值分布较为稀疏的情况下，可见路径压缩效果较好。
在以太坊系统中，160位的地址存在2^160 种，该数实际上已经非常大了，和账户数目相比，可以认为地址这一键值非常稀疏。
因此，我们可以在以太坊账户管理种使用Patricia tree这一数据结构！但实际上，在以太坊种使用的并非简单的PT(Patricia tree),而是MPT(Merkle Patricia tree)。
下图为以太坊中使用的MPT结构示意图。右上角表示四个账户(为直观，显示较少)和其状态(只显示账户余额)。（需要注意这里的指针都是哈希指针）
每次发布新区块，状态树中部分节点状态会改变。但改变并非在原地修改，而是新建一些分支，保留原本状态。如下图中，仅仅有新发生改变的节点才需要修改，其他未修改节点直接指向前一个区块中的对应节点。
所以，系统中全节点并非维护一棵MPT，而是每次发布新区块都要新建MPT。只不过大部分节点共享。
为什么要保存原本状态？为何不直接修改？
为了便于回滚。如下1中产生分叉，而后上面节点胜出，变为2中状态。那么，下面节点中状态的修改便需要进行回滚。因此，需要维护这些历史记录。
交易树和收据树的用途：
支持较为高效查找某个元素是否在某个集合中
最笨：元素遍历，复杂度为O(n)——轻节点不能用
方法：给一个大的集合，计算出一个紧凑的“摘要”
Bloom filter特点：有可能出现误报，但不会出现漏报。
Bloom filter变种：采用一组哈希函数进行向量映射，有效避免哈希碰撞
例：如下图，给定一个数据集，其中含义元素a、b、c，通过一个哈希函数H()对其进行计算，将其映射到一个其初始全为0的128位的向量的某个位置，将该位置置为1。将所有元素处理完，就可以得到一个向量，则称该向量为原集合的“摘要”。可见该“摘要”比原集合是要小很多的。
假定想要查询一个元素d是否在集合中，假设H(d)映射到向量中的位置处为0，说明d一定不在集合中；假设H(d)映射到向量中的位置处为1，有可能集合中确实有d，也有可能因为哈希碰撞产生误报。
如果集合中删除元素该怎么操作？
无法操作。也就是说，简单的Bloom filter不支持删除操作。如果想要支持删除操作，需要将记录数不能为0和1，需要修改为一个计数器(需要考虑计数器是否会溢出)。
每个交易完成后会产生一个收据，收据包含一个Bloom filter记录交易类型、地址等信息。在区块block header中也包含一个Bloom filter，其为该区块中所有交易的Bloom filter的一个并集。
所以，查找时候先查找块头中的Bloom filter，如果块头中包含。再查看区块中包含的交易的Bloom filter，如果存在，再查看交易进行确认；如果不存在，则说明发生了“碰撞”。
好处是通过Bloom filter这样一个结构，快速大量过滤掉大量无关区块，从而提高了查找效率。
以太坊的运行过程，可以视为交易驱动的状态机，通过执行当前区块中包含的交易，驱动系统从当前状态转移到下一状态。当然，BTC我们也可以视为交易驱动的状态机，其状态为UTXO。
对于给定的当前状态和给定一组交易，可以确定性的转移到下一状态(保证系统一致性)。
