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

Trie樹

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

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

· Patricia Trie樹

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

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

最終的8個key對應(yīng)的Value 如下表：

· Merkle Tree

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

· ETH Merkle Patricia Tries 樹

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

1.交易樹

2.收據(jù)樹（交易執(zhí)行過程中的一些數(shù)據(jù)）

3.狀態(tài)樹（賬號信息， 合約賬戶和用戶賬戶）

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

· 算法解釋

假設(shè)輸入值J，包含Key Value對的集合（Key Value都是字節(jié)數(shù)組）：

當(dāng)使用這個集合的時候，我們將集合表示如下：

對應(yīng)特定字節(jié)，我們表示為對應(yīng)的半字節(jié)（nibble），其中Y集合在Hex-Prefix Encoding中有說明，意為半字節(jié)（4bit）集合（之所以采用半字節(jié)，其與后續(xù)說明的分支節(jié)點branch node結(jié)構(gòu)以及key中編碼flag有關(guān)），公式如下：

在Tries樹中有三種節(jié)點：

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

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

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

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

如果當(dāng)前需要編碼的KV集合只剩下一條數(shù)據(jù)，那么這條數(shù)據(jù)按照第一條規(guī)則進(jìn)行編碼。

如果當(dāng)前需要編碼的KV集合有公共前綴，那么提取最大公共前綴并使用第二條規(guī)則進(jìn)行處理。

如果不是上面兩種情況，那么使用分支節(jié)點進(jìn)行集合切分，因為key是使用HP進(jìn)行編碼的，所以可能的分支只有0-15這16個分支?？梢钥吹絬的值由n進(jìn)行遞歸定義，而如果有節(jié)點剛好在這里完結(jié)了，那么第17個元素v就是為這種情況準(zhǔn)備的。

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