摘要：是以太坊存儲(chǔ)數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)，它是由和結(jié)合的一種樹(shù)形結(jié)構(gòu)，理解有助于我們更好的理解以太坊的數(shù)據(jù)存儲(chǔ)。所以就有了樹(shù)壓縮前綴樹(shù)，后面會(huì)介紹到，也被稱為，中文名稱默克爾樹(shù)，主要用于數(shù)據(jù)集較大時(shí)的文件校驗(yàn)。

??MPT(Merkle Patricia Tries)是以太坊存儲(chǔ)數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)，它是由Merkle Tree和Patricia Tree結(jié)合的一種樹(shù)形結(jié)構(gòu)，理解MPT有助于我們更好的理解以太坊的數(shù)據(jù)存儲(chǔ)。在了解MPT數(shù)據(jù)結(jié)構(gòu)之前，我們需要先來(lái)看看基本的Tree結(jié)構(gòu)和Merkle Tree、Patricia Tree。

??Trie樹(shù)，又稱前綴樹(shù)或字典樹(shù)，是一種有序樹(shù)，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串。

上圖是一棵Trie樹(shù)，表示了字符串集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ，從上圖中我們可以看出Trie樹(shù)的特點(diǎn)：

根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符。

從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符互不相同。

但是從上面的結(jié)構(gòu)也可以看出一個(gè)問(wèn)題：高度不可控，如下圖所示。所以就有了Patricia樹(shù)（壓縮前綴樹(shù)），后面會(huì)介紹到

Merkle Tree，也被稱為Hash Tree，中文名稱：默克爾樹(shù)，主要用于數(shù)據(jù)集較大時(shí)的文件校驗(yàn)。其主要特點(diǎn)為：

葉節(jié)點(diǎn)存儲(chǔ)著數(shù)據(jù)塊的Hash（如：文件塊、一段數(shù)據(jù)集）

非葉子節(jié)點(diǎn)（包括中間節(jié)點(diǎn)和根節(jié)點(diǎn)）存儲(chǔ)著對(duì)應(yīng)子節(jié)點(diǎn)Hash值串聯(lián)字符串之后的Hash值。

解釋：
1、在最底層，和哈希列表一樣，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊，有相應(yīng)地哈希和它對(duì)應(yīng)；
2、往上走，并不是直接去運(yùn)算根哈希，而是把相鄰的兩個(gè)哈希合并成一個(gè)字符串，然后運(yùn)算這個(gè)字符串的哈希，這樣每?jī)蓚€(gè)哈希就結(jié)婚生子，得到了一個(gè)”子哈?！?。如果最底層的哈希總數(shù)是單數(shù)，那到最后必然出現(xiàn)一個(gè)單身哈希，這種情況就直接對(duì)它進(jìn)行哈希運(yùn)算，所以也能得到它的子哈希再往上推，依然是一樣的方式，可以得到數(shù)目更少的新一級(jí)哈希，
3、最終必然形成一棵倒掛的樹(shù)，到了樹(shù)根的這個(gè)位置，這一代就剩下一個(gè)根哈希了，我們把它叫做 Merkle Root。

??對(duì)于這種數(shù)據(jù)結(jié)構(gòu)，在實(shí)際應(yīng)用中會(huì)有哪些應(yīng)用場(chǎng)景了，舉個(gè)例子，我們知道現(xiàn)在從網(wǎng)上下載文件，很多都是P2P下載，文件會(huì)切分成很多小的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊從不同的來(lái)源上下載，這些機(jī)器可以認(rèn)為是不穩(wěn)定或不可信的，文件下載完之后我們需要校驗(yàn)文件的完整性，這時(shí)我們總不能把文件再次切分然后分別計(jì)算它的Hash和下載前的Hash做對(duì)比吧，這時(shí)就需要用到Merkle Tree。
??在下載前，先從可靠的源獲得文件的Merkle Tree樹(shù)根，下載后，在合并文件之前先對(duì)比小文件的Hash是否一樣，如果一樣就認(rèn)為是可靠的，如果不一樣，就判定文件被損壞，從新的來(lái)源重新下載，文件合并之后，計(jì)算小數(shù)據(jù)塊的Hash并最終計(jì)算根Hash，也成為Merkle Root，然后對(duì)比根Hash是否一致。這樣就避免了對(duì)整個(gè)文件進(jìn)行Hash計(jì)算，因?yàn)楫?dāng)文件太大時(shí)，這種計(jì)算是很耗時(shí)。

??Patricia樹(shù)，或稱Patricia trie，或crit bit tree，壓縮前綴樹(shù)，是一種更節(jié)省空間的Trie。對(duì)于基數(shù)樹(shù)的每個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)是唯一的兒子的話，就和父節(jié)點(diǎn)合并。

??上面我們介紹了Merkle Tree和Patricia Tree，而MPT（Merkle Patricia Tree），顧名思義就是這兩者的結(jié)合。MTP樹(shù)種的節(jié)點(diǎn)包含空節(jié)點(diǎn)、葉子節(jié)點(diǎn)、擴(kuò)展節(jié)點(diǎn)和分支節(jié)點(diǎn)。

Nibble：它是key的基本單元，是一個(gè)四元組（四個(gè)bit位的組合例如二進(jìn)制表達(dá)的0010就是一個(gè)四元組）
空節(jié)點(diǎn)**：簡(jiǎn)單的表示空，在代碼中是一個(gè)空串。
葉子節(jié)點(diǎn)（leaf）：只有兩個(gè)元素，分別為key和value，表示為[key,value]的一個(gè)鍵值對(duì)，其中key是key的一種特殊十六進(jìn)制編碼，value是value的RLP編碼。
擴(kuò)展節(jié)點(diǎn)（extension）：也是[key，value]的一個(gè)鍵值對(duì)，但是這里的value是其他節(jié)點(diǎn)的hash值，這個(gè)hash可以被用來(lái)查詢數(shù)據(jù)庫(kù)中的節(jié)點(diǎn)。也就是說(shuō)通過(guò)hash鏈接到其他節(jié)點(diǎn)。
分支節(jié)點(diǎn)（branch）：分支節(jié)點(diǎn)有17個(gè)元素，回到Nibble，四元組是key的基本單元，四元組最多有16個(gè)值。所以前16個(gè)必將落入到在其遍歷中的鍵的十六個(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)的值)

這里還有一些知識(shí)點(diǎn)需要了解的，為了將MPT樹(shù)存儲(chǔ)到數(shù)據(jù)庫(kù)中，同時(shí)還可以把MPT樹(shù)從數(shù)據(jù)庫(kù)中恢復(fù)出來(lái)，對(duì)于Extension和Leaf的節(jié)點(diǎn)類型做了特殊的定義：如果是一個(gè)擴(kuò)展節(jié)點(diǎn)，那么前綴為0，這個(gè)0加在key前面。如果是一個(gè)葉子節(jié)點(diǎn)，那么前綴就是1。同時(shí)對(duì)key的長(zhǎng)度就奇偶類型也做了設(shè)定，如果是奇數(shù)長(zhǎng)度則標(biāo)示1，如果是偶數(shù)長(zhǎng)度則標(biāo)示0。

以太坊的每一個(gè)區(qū)塊頭，并非只包含一棵MPT樹(shù)，而是包含了三棵MPT樹(shù)，分別對(duì)應(yīng)了四種對(duì)象：

State Trie 區(qū)塊頭中的狀態(tài)樹(shù)

key => sha3(以太坊賬戶地址address)

value => rlp(賬號(hào)內(nèi)容信息account)

Transactions Trie 區(qū)塊頭中的交易樹(shù)

key => rlp(交易的偏移量 transaction index)

每個(gè)塊都有各自的交易樹(shù)，且不可更改

Receipts Trie 區(qū)塊頭中的收據(jù)樹(shù)

key = rlp(交易的偏移量 transaction index)

每個(gè)塊都有各自的交易樹(shù)，且不可更改

Storage Trie 存儲(chǔ)樹(shù)

存儲(chǔ)只能合約狀態(tài)

每個(gè)賬號(hào)有自己的Storage Trie

MPT樹(shù)種還有一個(gè)重要的概念：特殊的十六進(jìn)制前綴(hex-prefix, HP)編碼來(lái)對(duì)key編碼，我們先來(lái)了解一下編碼定義規(guī)則：

RAW 原始編碼，對(duì)輸入不做任何變更

HEX 十六進(jìn)制編碼

RAW編碼輸入的每個(gè)字符分解為高4位和低4位。比如key=>"bob",b的ASCII十六進(jìn)制編碼為0x62，o的ASCII十六進(jìn)制編碼為0x6f，分解成高四位和第四位，16表示終結(jié) 0x10，最終編碼結(jié)果為[6 2 6 15 6 2 16]，

如果是葉子節(jié)點(diǎn)，則在最后加上Hex值0x10表示結(jié)束

如果是分支節(jié)點(diǎn)不附加任何Hex值

HEX-Prefix 十六進(jìn)制前綴編碼

輸入key結(jié)尾為0x10，則去掉這個(gè)終止符

key之前補(bǔ)一個(gè)四元組這個(gè)Byte第0位區(qū)分奇偶信息，第1位區(qū)分節(jié)點(diǎn)類型

如果輸入key的長(zhǎng)度是偶數(shù)，則再添加一個(gè)四元組0x0在flag四元組后

將原來(lái)的key內(nèi)容壓縮，將分離的兩個(gè)byte以高四位低四位進(jìn)行合并

十六進(jìn)制前綴編碼相當(dāng)于一個(gè)逆向的過(guò)程，比如輸入的是[6 2 6 15 6 2 16]，根據(jù)第一個(gè)規(guī)則去掉終止符16。根據(jù)第二個(gè)規(guī)則key前補(bǔ)一個(gè)四元組，從右往左第一位為1表示葉子節(jié)點(diǎn)，從右往左第0位如果后面key的長(zhǎng)度為偶數(shù)設(shè)置為0，奇數(shù)長(zhǎng)度設(shè)置為1，那么四元組0010就是2。根據(jù)第三個(gè)規(guī)則，添加一個(gè)全0的補(bǔ)在后面，那么就是20.根據(jù)第三個(gè)規(guī)則內(nèi)容壓縮合并，那么結(jié)果就是[0x20 0x62 0x6f 0x62]

官方有一個(gè)詳細(xì)的結(jié)構(gòu)的示例：