樹這種數據結構，在區塊鏈中扮演著重要的角色，交易的數據，賬號的管理，交易的收據信息等都是一樹為基礎。本文主要介紹三種樹，也是在以太坊的中運用最多的三種樹結構：Trie樹， Patricia Trie和Merkle樹。

Trie樹

Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹。舉個例子，用trie樹保存10個節點的6個字符串：tea，ten，to，in，inn，int。具體圖如下：

可以看到字符串in，inn和int的公共前綴是“in”，這樣的效果就是壓縮了數據，減少空間的存儲。那么如果沒有公共的前綴，那么問題就來了，占用大量的空間，這樣的檢索的速度將會減慢。

· Patricia Trie樹

Patricia Trie樹的不同之處在于Trie樹給每一個字符串分配一個節點，這樣將使那些很長但又沒有公共節點的字符串的Trie樹退化成數組。在以太坊里面會由黑客構造很多這種節點造成拒絕服務攻擊。前綴樹的不同之處在于如果節點公共前綴，那么就使用公共前綴，否則就把剩下的所有節點插入同一個節點。Patricia相對Tire的優化正如下圖：

我們可以舉個例子來總結Patricia Trie樹，如下圖：

最終的8個key對應的Value 如下表：

· Merkle Tree

稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹。Merkle樹的葉子是數據塊（例如，文件或者文件的集合）的hash值。非葉節點是其對應子節點串聯字符串的hash。這個樹結構是比特幣采用的數據結構。Merkle Tree的主要作用是當我拿到Top Hash的時候，這個hash值代表了整顆樹的信息摘要，當樹里面任何一個數據發生了變動，都會導致Top Hash的值發生變化。而Top Hash的值是會存儲到區塊鏈的區塊頭里面去的， 區塊頭是必須經過工作量證明。這也就是說我只要拿到一個區塊頭，就可以對區塊信息進行驗證。

· ETH Merkle Patricia Tries 樹

以太坊的每個區塊頭包含三個重要的樹：

1.交易樹

2.收據樹（交易執行過程中的一些數據）

3.狀態樹（賬號信息， 合約賬戶和用戶賬戶）

如下通過例子來介紹，例如，兩個區塊頭，其中state root，tx root receipt root分別存儲了這三棵樹的樹根，第二個區塊顯示了當賬號 175的數據變更（27 -》 45）的時候，只需要存儲跟這個賬號相關的部分數據，而且老的區塊中的數據還是可以正常訪問。如下圖：

· 算法解釋

假設輸入值J，包含Key Value對的集合（Key Value都是字節數組）：

當使用這個集合的時候，我們將集合表示如下：

對應特定字節，我們表示為對應的半字節（nibble），其中Y集合在Hex-Prefix Encoding中有說明，意為半字節（4bit）集合（之所以采用半字節，其與后續說明的分支節點branch node結構以及key中編碼flag有關），公式如下：

在Tries樹中有三種節點：

1.葉子節點（Leaf）： 葉子節點包含兩個字段， 第一個字段是剩下的Key的半字節編碼，而且半字節編碼方法的第二個參數為true， 第二個字段是Value

2.擴展節點（Extention）： 擴展節點也包含兩個字段， 第一個字段是剩下的Key的可以至少被兩個剩下節點共享的部分的半字節編碼，第二個字段是n（J，j）

3.分支節點（Branch）： 分支節點包含了17個字段，其前16個項目對應于這些點在其遍歷中的鍵的十六個可能的半字節值中的每一個。第17個字段是存儲那些在當前結點結束了的節點（例如， 有三個key，分別是 （abc ，abd， ab） 第17個字段儲存了ab節點的值）

分支節點只有在需要的時候使用， 對于一個只有一個非空 key value對的Trie樹，可能不存在分支節點。如果使用公式來定義這三種節點， 那么公式如下：圖中的HP函數代表Hex-Prefix Encoding，是一種半字節編碼格式，RLP是使用RLP進行序列化的函數。

如果當前需要編碼的KV集合只剩下一條數據，那么這條數據按照第一條規則進行編碼。

如果當前需要編碼的KV集合有公共前綴，那么提取最大公共前綴并使用第二條規則進行處理。

如果不是上面兩種情況，那么使用分支節點進行集合切分，因為key是使用HP進行編碼的，所以可能的分支只有0-15這16個分支。可以看到u的值由n進行遞歸定義，而如果有節點剛好在這里完結了，那么第17個元素v就是為這種情況準備的。

對于數據應該如何存儲和不應該如何存儲， 黃皮書中說明沒有顯示的定義。所以這是一個實現上的問題。我們簡單的定義了一個函數來把J映射為一個Hash。 我們認為對于任意一個J，只存在唯一一個Hash值。