引言
go-etherum的包trie實現(xiàn)了Merkle Patricia Tries考榨，這里用簡稱MPT來稱呼這種數(shù)據(jù)結(jié)構(gòu)辈灼，這種數(shù)據(jù)結(jié)構(gòu)實際上是一種Trie樹變種，MPT是以太坊中一種非常重要的數(shù)據(jù)結(jié)構(gòu)纯赎，用來存儲用戶賬戶的狀態(tài)及其變更块攒、交易信息励稳、交易的收據(jù)信息。MPT實際上是三種數(shù)據(jù)結(jié)構(gòu)的組合囱井，分別是Trie樹驹尼， Patricia Trie， 和Merkle樹庞呕。
Trie樹 (引用自數(shù)據(jù)結(jié)構(gòu)之Trie樹)
Trie樹新翎，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)料祠，如英文字母的字典樹是一個26叉樹骆捧，數(shù)字的字典樹是一個10叉樹澎羞。
Trie樹可以利用字符串的公共前綴來節(jié)約存儲空間髓绽。如下圖所示，該trie樹用10個節(jié)點保存了6個字符串：tea妆绞，ten顺呕，to，in括饶，inn株茶，int:
在該trie樹中，字符串in图焰，inn和int的公共前綴是“in”启盛，因此可以只存儲一份“in”以節(jié)省空間。當然技羔，如果系統(tǒng)中存在大量字符串且這些字符串基本沒有公共前綴僵闯，則相應(yīng)的trie樹將非常消耗內(nèi)存，這也是trie樹的一個缺點藤滥。
Trie樹的基本性質(zhì)可以歸納為:
- 根節(jié)點不包含字符鳖粟，除根節(jié)點以外每個節(jié)點只包含一個字符。
- 從根節(jié)點到某一個節(jié)點拙绊，路徑上經(jīng)過的字符連接起來向图，為該節(jié)點對應(yīng)的字符串。
- 每個節(jié)點的所有子節(jié)點包含的字符串不相同标沪。
Trie樹的優(yōu)缺點:
缺點:
- 當 hash 函數(shù)很好時榄攀，Trie樹的查找效率會低于哈希搜索。
- 空間消耗比較大金句。
優(yōu)點:
- 插入和查詢的效率很高檩赢，都為O(m)，其中 m 是待插入/查詢的字符串的長度漠畜。
- Trie樹中不同的關(guān)鍵字不會產(chǎn)生沖突。
- Trie樹只有在允許一個關(guān)鍵字關(guān)聯(lián)多個值的情況下才有類似hash碰撞發(fā)生。
- Trie樹不用求 hash 值庆杜，對短字符串有更快的速度典蜕。通常钢猛，求hash值也是需要遍歷字符串的火的。
- Trie樹可以對關(guān)鍵字按字典序排序假瞬。
Patricia 樹 (引用自深入淺出以太坊)
Patricia樹，或稱Patricia trie，或crit bit tree箭券，壓縮前綴樹荆永，是一種更節(jié)省空間的Trie液兽。對于基數(shù)樹的每個節(jié)點坏匪，如果該節(jié)點是唯一的兒子的話罚屋，就和父節(jié)點合并嗅绸。
Patricia優(yōu)缺點:
優(yōu)點：Patricia Trie相比Trie優(yōu)點明顯脾猛，減少了空間的消耗。
缺點：隨著后續(xù)節(jié)點的不斷插入和刪除鱼鸠，原有節(jié)點可能會發(fā)生變化猛拴，并有可能不斷裂變或者合并出新的節(jié)點
Merkle 樹 (引用自深入淺出以太坊)
Merkle Tree，通常也被稱作Hash Tree蚀狰，顧名思義愉昆，就是存儲hash值的一棵樹。Merkle樹的葉子是數(shù)據(jù)塊(例如麻蹋，文件或者文件的集合)的hash值跛溉。非葉節(jié)點是其對應(yīng)子節(jié)點串聯(lián)字符串的hash。
要了解Merkle Tree就要先從Hash List說起:
在點對點網(wǎng)絡(luò)中作數(shù)據(jù)傳輸?shù)臅r候扮授，會同時從多個機器上下載數(shù)據(jù)芳室，而且很多機器可以認為是不穩(wěn)定或者不可信的。為了校驗數(shù)據(jù)的完整性刹勃，更好的辦法是把大的文件分割成小的數(shù)據(jù)塊（例如堪侯，把分割成2K為單位的數(shù)據(jù)塊）。這樣的好處是深夯，如果小塊數(shù)據(jù)在傳輸過程中損壞了抖格，那么只要重新下載這一快數(shù)據(jù)就行了诺苹，不用重新下載整個文件。
怎么確定小的數(shù)據(jù)塊沒有損壞哪雹拄？只需要為每個數(shù)據(jù)塊做Hash收奔。BT下載的時候，在下載到真正數(shù)據(jù)之前滓玖，我們會先下載一個Hash列表坪哄。那么問題又來了，怎么確定這個Hash列表本身是正確的呢势篡？答案是把每個小塊數(shù)據(jù)的Hash值拼到一起翩肌，然后對這個長字符串再做一次Hash運算，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)禁悠。下載數(shù)據(jù)的時候念祭，首先從可信的數(shù)據(jù)源得到正確的根Hash，就可以用它來校驗Hash列表了碍侦，然后通過校驗后的Hash列表校驗數(shù)據(jù)塊粱坤。
Merkle Tree可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree瓷产。
在最底層站玄，和哈希列表一樣，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊濒旦，有相應(yīng)地哈希和它對應(yīng)株旷。但是往上走，并不是直接去運算根哈希尔邓，而是把相鄰的兩個哈希合并成一個字符串晾剖，然后運算這個字符串的哈希，這樣每兩個哈希就結(jié)婚生子铃拇，得到了一個”子哈铣伲“。如果最底層的哈峡独螅總數(shù)是單數(shù)雕什，那到最后必然出現(xiàn)一個單身哈希，這種情況就直接對它進行哈希運算显晶，所以也能得到它的子哈希贷岸。于是往上推，依然是一樣的方式磷雇，可以得到數(shù)目更少的新一級哈希偿警，最終必然形成一棵倒掛的樹，到了樹根的這個位置唯笙，這一代就剩下一個根哈希了螟蒸，我們把它叫做 Merkle Root盒使。
在p2p網(wǎng)絡(luò)下載網(wǎng)絡(luò)之前，先從可信的源獲得文件的Merkle Tree樹根七嫌。一旦獲得了樹根少办，就可以從其他從不可信的源獲取Merkle tree。通過可信的樹根來檢查接受到的MerkleTree诵原。如果Merkle Tree是損壞的或者虛假的英妓，就從其他源獲得另一個Merkle Tree，直到獲得一個與可信樹根匹配的MerkleTree绍赛。
Merkle Tree和HashList的主要區(qū)別是蔓纠，可以直接下載并立即驗證Merkle Tree的一個分支。因為可以將文件切分成小的數(shù)據(jù)塊吗蚌，這樣如果有一塊數(shù)據(jù)損壞腿倚，僅僅重新下載這個數(shù)據(jù)塊就行了。如果文件非常大褪测，那么Merkle tree和Hash list都很到猴誊，但是Merkle tree可以一次下載一個分支，然后立即驗證這個分支侮措，如果分支驗證通過，就可以下載數(shù)據(jù)了乖杠。而Hash list只有下載整個hash list才能驗證分扎。
MPT
Trie結(jié)構(gòu)
MPT 是 Ethereum 自定義的 Trie 型數(shù)據(jù)結(jié)構(gòu)。在代碼中胧洒，trie.Trie 結(jié)構(gòu)體用來管理一個 MPT 結(jié)構(gòu)畏吓，其中每個節(jié)點都是行為接口 Node 的實現(xiàn)類。下圖是 Trie 結(jié)構(gòu)體和 node 接口族的 UML 關(guān)系圖：
在 Trie 結(jié)構(gòu)體中卫漫，成員 root 始終作為整個 MPT 的根節(jié)點;
db是后端的KV存儲菲饼，trie的結(jié)構(gòu)最終都是需要通過KV的形式存儲到數(shù)據(jù)庫里面去，然后啟動的時候是需要從數(shù)據(jù)庫里面加載的;
originalRoot 的作用是在創(chuàng)建 Trie 對象時承接入?yún)?hashNode列赎，通過這個hash值可以在數(shù)據(jù)庫里面恢復出整顆的trie樹;
-
cachegen 是 cache 次數(shù)的計數(shù)器宏悦，每次 Trie 的變動提交后cachegen 自增 1。
cachegen會被附加在node節(jié)點上面(node.nodeFlag.gen)包吝，默認等于Trie的cachegen饼煞。如果Trie每次Commit的時候node有更新，那么Trie的cachegen會重新賦值給node的cachegen诗越。否則node的cachegen將小于Trie的cachegen砖瞧。
如果當前Trie的cachegen - cachelimit大于node的cachegen，說明trie提交了cachelimit次之后嚷狞，node一直沒有更新块促。那么node會從cache里面卸載荣堰，以便節(jié)約內(nèi)存。 其實這就是緩存更新的LRU算法竭翠， 如果一個緩存在多久沒有被使用持隧，那么就從緩存里面移除，以節(jié)約內(nèi)存空間逃片。 Trie 結(jié)構(gòu)體提供包括對節(jié)點的插入屡拨、刪除、更新褥实，所有節(jié)點改動的提交呀狼，以及返回整個 MPT 的哈希值。
node
node 接口族擔當整個 MPT 中的各種節(jié)點损离，node 接口分四種實現(xiàn): fullNode哥艇，shortNode，valueNode僻澎，hashNode貌踏，其中只有 fullNode 和 shortNode 可以帶有子節(jié)點。
fullNode 是一個可以攜帶多個子節(jié)點的節(jié)點窟勃。
- 它有一個容量為 17 的 node 數(shù)組成員變量 Children
- 數(shù)組中前 16 個空位分別對應(yīng) 16 進制 (hex) 下的 0-9a-f祖乳，這樣對于每個子節(jié)點，根據(jù)其 key 值 16 進制形式下的第一位的值秉氧，就可掛載到 Children 數(shù)組的某個位置眷昆，fullNode 本身不再需要額外 key 變量；
- Children 數(shù)組的第 17 位汁咏，留給該 fullNode 的數(shù)據(jù)部分亚斋。fullNode 明顯繼承了原生 trie 的特點，而每個父節(jié)點最多擁有 16 個分支也包含了基于總體效率的考量攘滩。
shortNode 是一個僅有一個子節(jié)點的節(jié)點帅刊。
- 它的成員變量 Val 指向一個子節(jié)點，而成員 Key 是一個字節(jié)數(shù)組[]byte漂问。
- 顯然 shortNode 的設(shè)計體現(xiàn)了 PatriciaTrie 的特點赖瞒，通過合并只有一個子節(jié)點的父節(jié)點和其子節(jié)點來縮短 trie 的深度。
valueNode 承載了MPT結(jié)構(gòu)中 真正數(shù)據(jù)部分的節(jié)點级解。
- 它其實是字節(jié)數(shù)組 []byte 的一個別名冒黑，不帶子節(jié)點。
- 在使用中勤哗，valueNode 就是所攜帶數(shù)據(jù)部分的 RLP 哈希值抡爹，長度 32byte，數(shù)據(jù)的 RLP 編碼值作為 valueNode 的匹配項存儲在數(shù)據(jù)庫里芒划。
這三種類型構(gòu)成了一個完整的PatriciaTrie結(jié)構(gòu)冬竟。何一個[k,v]類型數(shù)據(jù)被插入一個MPT時欧穴，會以k字符串為路徑沿著root向下延伸，在此次插入結(jié)束時首先成為一個shortNode泵殴，k會以自頂點root起到到該節(jié)點止的key path形式存在涮帘。但之后隨著其他節(jié)點的不斷插入和刪除，根據(jù)MPT結(jié)構(gòu)的要求笑诅，原有節(jié)點可能會變化成其他node實現(xiàn)類型调缨，同時MPT中也會不斷裂變或者合并出新的節(jié)點。
注意：黃皮書中把節(jié)點類型概括為了分支節(jié)點吆你、擴展節(jié)點和葉子節(jié)點弦叶。fullNode對應(yīng)了黃皮書里面的分支節(jié)點，shortNode對應(yīng)了黃皮書里面的擴展節(jié)點和葉子節(jié)點(通過shortNode.Val的類型來對應(yīng)到底是葉子節(jié)點還是分支節(jié)點妇多，如果是valueNode伤哺，就是葉子節(jié)點，否則是分支節(jié)點)者祖。
hashNode
hashNode 跟 valueNode 一樣立莉，也是字符數(shù)組 []byte 的一個別名，同樣存放 32byte 的哈希值七问，也沒有子節(jié)點蜓耻。不同的是，hashNode 是 fullNode 或者 shortNode 對象的 RLP 哈希值烂瘫，所以它跟 valueNode 在使用上有著莫大的不同媒熊。
在 MPT 中，hashNode 幾乎不會單獨存在 (有時遍歷遇到一個 hashNode 往往因為原本的 node 被折疊了)坟比，而是以 nodeFlag 結(jié)構(gòu)體的成員(nodeFlag.hash) 的形式，被 fullNode 和 shortNode 間接持有嚷往。一旦 fullNode 或 shortNode 的成員變量 (包括子結(jié)構(gòu)) 發(fā)生任何變化葛账，它們的 hashNode 就一定需要更新。所以在 trie.Trie 結(jié)構(gòu)體的 insert()皮仁，delete()等函數(shù)實現(xiàn)中籍琳，可以看到除了新創(chuàng)建的 fullNode、shortNode贷祈，那些子結(jié)構(gòu)有所改變的 fullNode趋急、shortNode 的 nodeFlag 成員也會被重設(shè)，hashNode 會被清空势誊。在下次 trie.Hash()調(diào)用時呜达，整個 MPT 自底向上的遍歷過程中，所有清空的 hashNode 會被重新賦值粟耻。這樣 trie.Hash()結(jié)束后查近，我們可以得到一個根節(jié)點 root 的 hashNode眉踱，它就是此時此刻這個 MPT 結(jié)構(gòu)的哈希值。上文中提到的霜威，Block 的成員變量 Root谈喳、TxHash、ReceiptHash 的生成戈泼，正是源出于此婿禽。
明顯的，hashNode 體現(xiàn)了 MerkleTree 的特點：每個父節(jié)點的哈希值來源于所有子節(jié)點哈希值的組合大猛，一個頂點的哈希值能夠代表一整個樹形結(jié)構(gòu)扭倾。
hashNode 加上之前的 fullNode，shortNode胎署，valueNode吆录，構(gòu)成了一個完整的 Merkle-PatriciaTrie 結(jié)構(gòu)。
一個MPT簡單例子：
