1. Trie/Radix樹
Trie樹，又稱 前綴樹或字典樹 拖叙，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組. 其中的鍵通常是字符串 夺艰。與二叉查找樹不同捍岳， 鍵不是直接保存在節(jié)點(diǎn)中富寿，而是由節(jié)點(diǎn)在樹中的位置決定 。一個(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è)完整的字符串.
常見的用來存英文單詞的trie每個(gè)節(jié)點(diǎn)是一個(gè) 長(zhǎng)度為27的指針數(shù)組戳气，index0-25代表a-z字符链患，26為標(biāo)志域 。如圖：
2. Patricia 帕特里夏樹
Patricia樹瓶您，或稱Patricia trie锣险，或crit bit tree蹄皱，壓縮前綴樹，是一種更節(jié)省空間的Trie芯肤。對(duì)于基數(shù)樹的每個(gè)節(jié)點(diǎn)巷折，如果 該節(jié)點(diǎn)是唯一的兒子的話，就和父節(jié)點(diǎn)合并 崖咨。
3. Merkle 默克爾樹
- MT是一種樹锻拘，大多數(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ì)于交易樹來說区宇，二叉Merkle Tree是非常好的數(shù)據(jù)結(jié)構(gòu)。因?yàn)橐坏湟呀?jīng)建立值戳，花多少時(shí)間來編輯這棵樹并不重要议谷，它就會(huì) 永遠(yuǎn)存在并且不會(huì)改變 。
但是堕虹，對(duì)于狀態(tài)樹卧晓，情況會(huì)更復(fù)雜些。
- 以太坊中的狀態(tài)樹基本上包含了一個(gè) 鍵值映射 赴捞，其中的 鍵是地址 禀崖，而值包括賬戶的 聲明、余額螟炫、隨機(jī)數(shù)nonce波附、代碼以及每一個(gè)賬戶的存儲(chǔ) （其中存儲(chǔ)本身就是一顆樹）。
- 狀態(tài)樹需要經(jīng)常地進(jìn)行更新：
- 賬戶余額和賬戶的隨機(jī)數(shù)nonce經(jīng)常會(huì)更變
- 新的賬戶會(huì)頻繁地插入昼钻，存儲(chǔ)的鍵（ key）也會(huì)經(jīng)常被插入以及刪除掸屡。
我們需要這樣的數(shù)據(jù)結(jié)構(gòu):
- 它能 在一次插入、更新然评、刪除操作后快速計(jì)算到樹根 仅财，而不需要重新計(jì)算整個(gè)樹的Hash。
- 樹的 深度是有限制 的碗淌，即使考慮攻擊者會(huì)故意地制造一些交易盏求，使得這顆樹盡可能地深抖锥。不然，攻擊者可以通過操縱樹的深度碎罚，執(zhí)行拒絕服務(wù)攻擊（DOS attack）磅废，使得更新變得極其緩慢。
- 樹的根只取決于數(shù)據(jù) 荆烈，和其中的更新順序無關(guān)拯勉。換個(gè)順序進(jìn)行更新，甚至重新從頭計(jì)算樹憔购，并不會(huì)改變根宫峦。
MPT是最接近同時(shí)滿足上面的性質(zhì)的的數(shù)據(jù)結(jié)構(gòu)。MPT的工作原理的最簡(jiǎn)單的解釋是:
- 值通過鍵來存儲(chǔ)
- 鍵被編碼到搜索樹必須要經(jīng)過的路徑中
- 每個(gè)節(jié)點(diǎn)有 16個(gè)孩子 玫鸟，因此路徑由16進(jìn)制的編碼決定：例如导绷，鍵‘dog’的16進(jìn)制編碼是6 4 6 15 6 7，所以從root開始到第六個(gè)分支屎飘，然后到第四個(gè)妥曲，再到第六個(gè)，再到第十五個(gè)枚碗，這樣依次進(jìn)行到達(dá)樹的葉子逾一。
- 當(dāng)樹稀少時(shí)需要一些額外的優(yōu)化铸本。
