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值。
