Trie、Radix Trie、Patricia 和 Merkle Patricia Trie
您能向我解釋這 4 次嘗試之間的主要區別嗎？
謝謝
一個 trie 只是一個 trie 資訊，例如儲存單詞 dog 然後從上到下儲存為 dog。維基百科頁面在這張圖片中顯示了它：
如您所見，它儲存了幾個單詞，例如“to”、“tea”、“ted”、“ten”、“A”、“inn”。這些詞中的每一個都是這個資料結構中的一個鍵。所以我用“to”查詢一個trie數據庫，它會返回7。它的遍歷會先到t然後再到。它節省了搜尋數據庫中每個單詞的時間。可以把它想像成簡單地通過迭代每個字元來創建一個越來越小的組。所以假設你查詢“十”，數據庫會首先說讓我們看看所有以“t”開頭的單詞，然後是“te”，然後是“十”，它只返回一個條目。
Radix trie 包括對此結構的改進。在我之前儲存 dog 和 dot 的範例中。它不是將 d 和 o 作為節點儲存在 trie 中，而是將“do”儲存為節點，將“dog”和“dot”儲存為該節點的子節點。這意味著更少的遍歷，但是如果 dam 出現，它必須創建 dam 和 dog，因為現在有 da 和 do 的組合，而不僅僅是 do 詞。
我相信這張照片很容易解釋。它只是不將每個字元儲存為特里樹的一個節點，而是將節點下所有單詞中使用的字元連接到一個節點中。如果您查看 Ruber，之前您可能已經想像到 rubens 在 e 節點之外只有 1 個節點。但是由於我們添加了 Ruber，我們必須創建 2 個節點。
這就是嘗試的基礎知識，現在進入 merkle patricia 嘗試。現在，在我們討論 merkle patricia trie 的工作原理時，這裡有一張圖片可以幫助理解：
現在這很複雜，但它可以幫助您了解這個 trie 是如何工作的。如您所見，現在有 3 種不同類型的節點，我們不再只是在氣泡中查看“e”或“ear”，而是一些更複雜的資訊，但它遵循類似的步驟。您可以看到頂部的一些鍵。查看“a711355”，它的值為 45.0 ETH。現在嘗試從頂部開始遍歷 trie。首先，我們有一個共享半字節 a7 的擴展節點，然後下一個節點是一個分支節點，它有 16 種不同的下一次遍歷可能性，所以我們選擇 1，因為我們遵循我們的密鑰。然後從那裡的節點有一個 1355 的 key-end 完成了 trie 的遍歷，我們現在收到 45.0 ETH 的值。
您可能注意到每個節點都有字元串的一部分，擴展節點有一個共享的半字節，這是我們用於遍歷的字元串的一部分，分支節點包含十六進制的 0-f，表示字元串中的 1 個字元，那麼葉子節點中的key-end代表剩餘的遍歷。前綴在構造時有助於 trie。
除了遍歷之外，這些嘗試並沒有添加太多內容，它只是針對大量數據進行了優化。例如，Branch 節點的替代方案是 radix trie 中的每個單獨字元有 2-16 個不同的節點。
有關 merkle patricia trie 如何成為優化的 radix trie 的更多技術資訊，您可以查看wiki。我想我很好地簡化了他們的工作。
現在我可以了解 levelDB 將如何儲存這些值，但這已經超出了問題的範圍。帕特里夏嘗試只是基數嘗試，所以我沒有為帕特里夏嘗試包括單獨的部分。
