1. Trie/Radix樹(shù)
Trie樹(shù)，又稱 前綴樹(shù)或字典樹(shù) ，是一種有序樹(shù)，用于保存關(guān)聯(lián)數(shù)組. 其中的鍵通常是字符串 。與二叉查找樹(shù)不同， 鍵不是直接保存在節(jié)點(diǎn)中，而是由節(jié)點(diǎn)在樹(shù)中的位置決定 。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串，而 根節(jié)點(diǎn)對(duì)應(yīng)空字符串 。
一般情況下，不是所有的節(jié)點(diǎn)都有對(duì)應(yīng)的值， 只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的鍵才有相關(guān)的值 。 實(shí)際上trie每個(gè)節(jié)點(diǎn)是一個(gè) 確定長(zhǎng)度的數(shù)組 ，數(shù)組中每個(gè)節(jié)點(diǎn)的值是一個(gè)指向子節(jié)點(diǎn)的指針，最后有個(gè)標(biāo)志域， 標(biāo)識(shí)這個(gè)位置為止是否是一個(gè)完整的字符串.
常見(jiàn)的用來(lái)存英文單詞的trie每個(gè)節(jié)點(diǎn)是一個(gè) 長(zhǎng)度為27的指針數(shù)組，index0-25代表a-z字符，26為標(biāo)志域 。如圖：
2. Patricia 帕特里夏樹(shù)
Patricia樹(shù)，或稱Patricia trie，或crit bit tree，壓縮前綴樹(shù)，是一種更節(jié)省空間的Trie。對(duì)于基數(shù)樹(shù)的每個(gè)節(jié)點(diǎn)，如果 該節(jié)點(diǎn)是唯一的兒子的話，就和父節(jié)點(diǎn)合并 。
3. Merkle 默克爾樹(shù)
- MT是一種樹(shù)，大多數(shù)是 二叉樹(shù) ，也可以多叉樹(shù)，無(wú)論是幾叉樹(shù)，它都具有樹(shù)結(jié)構(gòu)的所有特點(diǎn)；
- Merkle Tree的 葉子節(jié)點(diǎn)的value是數(shù)據(jù)集合的單元數(shù)據(jù)或者單元數(shù)據(jù)HASH 。
- 非葉子節(jié)點(diǎn)的value是根據(jù)它下面所有的葉子節(jié)點(diǎn)值 ，然后按照Hash算法計(jì)算而得出的。
4. MPT(Merkle Patricia Trees)
知道了Merkle Tree，知道了Patricia Tree，顧名思義，MPT（Merkle Patricia Tree）就是這兩者混合后的產(chǎn)物。
在以太坊中, 對(duì)于交易樹(shù)來(lái)說(shuō)，二叉Merkle Tree是非常好的數(shù)據(jù)結(jié)構(gòu)。因?yàn)橐坏?shù)已經(jīng)建立，花多少時(shí)間來(lái)編輯這棵樹(shù)并不重要，它就會(huì) 永遠(yuǎn)存在并且不會(huì)改變 。
但是，對(duì)于狀態(tài)樹(shù)，情況會(huì)更復(fù)雜些。
- 以太坊中的狀態(tài)樹(shù)基本上包含了一個(gè) 鍵值映射 ，其中的 鍵是地址 ，而值包括賬戶的 聲明、余額、隨機(jī)數(shù)nonce、代碼以及每一個(gè)賬戶的存儲(chǔ) （其中存儲(chǔ)本身就是一顆樹(shù)）。
- 狀態(tài)樹(shù)需要經(jīng)常地進(jìn)行更新：
- 賬戶余額和賬戶的隨機(jī)數(shù)nonce經(jīng)常會(huì)更變
- 新的賬戶會(huì)頻繁地插入，存儲(chǔ)的鍵（ key）也會(huì)經(jīng)常被插入以及刪除。
我們需要這樣的數(shù)據(jù)結(jié)構(gòu):
- 它能 在一次插入、更新、刪除操作后快速計(jì)算到樹(shù)根 ，而不需要重新計(jì)算整個(gè)樹(shù)的Hash。
- 樹(shù)的 深度是有限制 的，即使考慮攻擊者會(huì)故意地制造一些交易，使得這顆樹(shù)盡可能地深。不然，攻擊者可以通過(guò)操縱樹(shù)的深度，執(zhí)行拒絕服務(wù)攻擊（DOS attack），使得更新變得極其緩慢。
- 樹(shù)的根只取決于數(shù)據(jù) ，和其中的更新順序無(wú)關(guān)。換個(gè)順序進(jìn)行更新，甚至重新從頭計(jì)算樹(shù)，并不會(huì)改變根。
MPT是最接近同時(shí)滿足上面的性質(zhì)的的數(shù)據(jù)結(jié)構(gòu)。MPT的工作原理的最簡(jiǎn)單的解釋是:
- 值通過(guò)鍵來(lái)存儲(chǔ)
- 鍵被編碼到搜索樹(shù)必須要經(jīng)過(guò)的路徑中
- 每個(gè)節(jié)點(diǎn)有 16個(gè)孩子 ，因此路徑由16進(jìn)制的編碼決定：例如，鍵‘dog’的16進(jìn)制編碼是6 4 6 15 6 7，所以從root開(kāi)始到第六個(gè)分支，然后到第四個(gè)，再到第六個(gè)，再到第十五個(gè)，這樣依次進(jìn)行到達(dá)樹(shù)的葉子。
- 當(dāng)樹(shù)稀少時(shí)需要一些額外的優(yōu)化。
