梅克爾-帕特裡夏樹 Merkel-Patricia Tree（MPT）
MPT是什麼
- Merkel Patricia Tree (MPT)，翻譯為梅克爾-帕特裡夏樹
- MPT 提供了一個基于密碼學驗證的底層資料結構，用來存儲鍵值對（key-value）關系
- MPT 是完全确定性的，這是指在一顆 MPT 上一組鍵值對是唯一确定的，相同内容的鍵可以保證找到同樣的值，并且有同樣的根哈希（root hash）
- MPT 的插入、查找、删除操作的時間複雜度都是O(log(n))，相對于其它基于複雜比較的樹結構（比如紅黑樹），MPT 更容易了解，也更易于編碼實作
從字典樹（Trie）說起
- 字典樹（Trie）也稱字首樹（prefix tree），屬于搜尋樹，是一種有序的樹資料結構
- 字典樹用于存儲動态的集合或映射，其中的鍵通常是字元串
快速學習-梅克爾-帕特裡夏樹
基數樹（Radix Tree）
基數樹節點
- 這裡的 i0,i1,…,in 表示定義好的字母表中的字元，字母表中一共有n+1個字元，這顆樹的基數（radix）就是 n+1
- value 表示這個節點中最終存儲的值
- 每一個 i0 到 in 的“槽位”，存儲的或者是null，或者是指向另一節點的指針
- 用節點的通路路徑表示 key，用節點的最末位置存儲value，這就實作了一個基本的鍵值對存儲
示例
- 我們有一個鍵值對{ “dog”: “puppy” }，現在希望通過鍵 dog 通路它的值；我們采用16進制的 Hex 字元作為字元集
- 首先我們将 “dog” 轉換成 ASCII 碼，這樣就得到了字元集中的表示 64 6f 67，這就是樹結構中對應的鍵
- 按照鍵的字母序，即 6->4->6->f->6->7，建構樹中的通路路徑
- 從樹的根節點（root）出發，首先讀取索引值（index）為 6 的插槽中存儲的值，以它為鍵通路到對應的子節點
- 然後取出子節點索引值為 4 的插槽中的值，以它為鍵通路下一層節點，直到通路完所需要的路徑
- 最終通路到的葉子節點，就存儲了我們想要查找的值，即“puppy”
快速學習-梅克爾-帕特裡夏樹
基數樹的問題
資料校驗
- 基數樹節點之間的連接配接方式是指針，一般是用32位或64位的記憶體位址作為指針的值，比如C語言就是這麼做的。但這種直接存位址的方式無法提供對資料内容的校驗，而這在區塊鍊這樣的分布式系統中非常重要。
通路效率
-
基數樹的另一個問題是低效。如果我們隻想存一個 bytes32 類型的鍵值對，通路路徑長度就是64（在以太坊定義的 Hex 字元
集下）；每一級通路的節點都至少需要存儲 16 個位元組，這樣就需要至少 1k 位元組的額外空間，而且每次查找和删除都必須完整
地執行 64 次下探通路。