以太坊中運(yùn)用最多的三種樹結(jié)構(gòu)介紹

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

Trie樹

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

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

· Patricia Trie樹

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

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

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

· Merkle Tree

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

· ETH Merkle Patricia Tries 樹

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

1.交易樹

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

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

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

· 算法解釋

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

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

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

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

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

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

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

分支節(jié)點(diǎn)只有在需要的時(shí)候使用， 對(duì)于一個(gè)只有一個(gè)非空 key value對(duì)的Trie樹，可能不存在分支節(jié)點(diǎn)。如果使用公式來定義這三種節(jié)點(diǎn)， 那么公式如下：圖中的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é)點(diǎn)進(jìn)行集合切分，因?yàn)閗ey是使用HP進(jìn)行編碼的，所以可能的分支只有0-15這16個(gè)分支。可以看到u的值由n進(jìn)行遞歸定義，而如果有節(jié)點(diǎn)剛好在這里完結(jié)了，那么第17個(gè)元素v就是為這種情況準(zhǔn)備的。

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