无论是比特币还是以太坊，它们都是完全由代码创造出来的，它们的几乎所有一切都是程序执行的结果。对计算机程序有些了解的朋友应该都知道，计算机程序离不开数据结构和算法。
顺便提一下，有部分人不认为比特币和以太饭具有价值的很大原因就是它们都是虚拟的，没有实体支撑。这是一种偏见，比特币和以太坊都因为解决了现实中的问题而应该具有价值，至于价值究竟有多大，最终市场会给出自己的答案。
在以太坊系统中，有三种主要的数据结构：状态树、交易树和收据树。
深刻理解这三种“树”对于以太坊的运行机制将会有非常清晰的认识，下面我们先入个门，更多深入的知识需要我们一起不断努力去学习。
状态树
我在《你了解每天使用地数字资产账户么？》中提到：
以太坊采用地是基于账户的账本，在这种模式下，系统需要显示地记录账户上有多少余额。
而要实现以太坊系统中能够显示记录账户余额，就需要把账户地址和账户状态做一个映射。那么问题来了，我们需要什么样的数据结构才能实现这样的映射呢？
在回答这个问题之前，我们需要了解一下什么是trie？
请先看一张图：
我们假设右边的几个单词通过这样一个树组织起来了，其实这样组织起来的查找效率已经比单纯把这些单词放在内存中要提高很多了。
trie这种数据结构具有以下特点：
trie中每个节点的分支数目取决于每个元素中key值的取值范围，以太坊系统中的分支数目为0～f
trie的查找效率取决于键值对儿中key的长度，长度越长，访问内存的次数就越多
trie不会出现元素碰撞，从图中就可以看出来
只要输入内容不变，最终构成的trie这颗树是一样的
更新的局部性非常好，只要更新分支内容就行了
trie也有自己的缺点：
存储比较浪费，如果元素内容很长，那么占用的内存是非常大的，而且会出现很多单个分支的情况。
我们之前提过，以太坊不是比拼算力的，它是比拼内存的，根因就在于以太坊使用的是基于这样的数据结构。注意我的表述是“以太坊使用的是基于这样的数据结构”，也就是说，以太坊并不是直接使用的trie，而是引入了patricia trie（压缩前缀树）。
patricia trie对于trie做了优化，它把在trie中一脉相承的节点进行合并，这样就节省了空间，同时也提高了查找效率。
上面那个例子，优化后就变成了
我们可以很明显地看到整体的树高减小了很多，这对于优化以太坊的复杂查找是有利的。
除此之外，以太坊基于账户的账本模式还要求整个以太坊的账户状态是可追溯的，所以以太坊实际使用的数据结构是 markle patricia tree（MPT）状态树，它在patricia trie的基础上把普通指针换成了哈希指针。
我们来看一下 MPT 的实例图：
我们可以很清晰地看到，图中展示了4个以太坊账户，并且每个账户的余额都是在某个分支节点中找到，而每个节点之间都是通过哈希指针连接起来，最终计算出一个根哈希值保存起来（对于以太坊状态树结构感兴趣的话，可以深入研究一下这张图，这里限于篇幅，就不做过多介绍了）。
最终，这就是我们可以看到地以太坊中使用地MPT状态树了，它具有以下特点：
防止篡改，注意：这里说的是每个账户的状态是无法篡改的
merkle proof 能够证明余额，因为以太坊的每个全节点都会保存整个共链上所有账户的状态
验证账户是否存在
MPT状态树的不足之处在于他很难处理出现哈希碰撞之后的情况，这是MPT这种数据结构天然的硬伤。
为此，以太坊在设计之处就把账户的输入空间设置成2^160，这是一个无限大的空间，在这个空间中 ，出现账户碰撞比地球爆炸显得更加不可能发生。
交易树和收据树
以太坊系统中，每次发布一个区块时，区块中所包含的交易都会组织成一颗交易树，这和比特币中的交易树是非常类似的；同时，伴随着这些交易的产生，每笔交易的相关信息又会组织成一颗收据树。为什么以太坊系统中需要收据树呢？
因为以太坊中智能合约的执行过程内容是比较复杂的，所以增加收据树的结构有利于我们快速查询一些执行的结果。
从数据结构来看，以太坊中的交易树和收据树都是MPT，这就和比特币中的交易树有所区别了。比特币中的交易树只是一个普通的merkle tree，它仅仅只是记录了当前区块中的交易信息，交易的顺序是由当前发布的区块决定的。
以太坊中的交易树和收据树与状态树的共同点：
那就是这三颗树都是MPT结构，三颗树都采取同样的数据结构有可能只是为了方便，因为这样代码就可以大量复用。
三颗树也有一个非常重要的区别：
系统中的交易树和收据树只把当前区块所包含交易的信息和内容组织成MPT，而状态树是把整个系统中账户的状态组织成MPT，并不管当前区块中具体有哪些交易。
交易树和收据树有什么用？
提供market proof，交易树可以用来证明某个交易被打包到某个区块里面了，收据树可以证明某个交易执行的结果
交易树和收据树还实现了以太坊中需要的复杂查询功能，比如：过去十天的交易内容
值得一提的是，为了实现高效地查询某些复杂的类型信息，以太坊系统中还引入了 bloom filter （布隆过滤器）这种数据结构。bloom filter 可以支持高效查找某个元素不在一个比较大的集合中，bloom filter 的局限性在于它不支持删除操作。
下面我们通过一张图一起来简单看下 bloom filter 的原理：
bloom filter 简单来说就是将一个非常大的集合计算出一个很紧凑的摘要（digest），比如一个128位的向量。
我们假设元素a、b、c、d、e都在同一个集合中，下面那个长条就假设是一个128位的向量；在这个向量中，每个位置的初始值都是0。bloom filter 就会通过某个哈希函数（H）映射到下面那个向量中如图所示的位置，那么这个位置的值就会变成1。
这样做有什么好处呢？
bloom filter 成功把一个非常大的集合变成了一个只有128 bit 的概要
我们可以快速地知道元素f一定不在这个集合当中，因为f取哈希之后不能够在这个向量中找到相应的映射位置
bloom filter 的缺点在于它无法确切地告诉我们某个元素在这个集合当中，因为有可能出现哈希碰撞。比如，我们看到a映射到了第一个位置，但是可能会有一个g元素也可能会映射到这个位置，这样以来我们就不能断定元素g一定在这个集合当中。
所以，实际上在大多数bloom filter中使用的并不是某个单一的哈希函数，而是一组哈希函数，目的就是为了减少哈希碰撞带来的误判。
写到这里，大家应该能够看出来我为什么要花较大的篇幅介绍数据结构MPT。因为以太坊中的状态树、交易树和收据树的数据结构本质都是MPT。感兴趣地朋友可以深入了解一下MPT，以太坊能够成功运行的底层数据结构就在于此了。