為什麼 Merkle-Patricia Trie 有三種類型的節點？

我一直在閱讀有關 Merkel Patricia Trie 的文章，我認為我了解它的工作原理，但對我來說它看起來有點過於復雜，這表明我並不完全理解它。

這是 Merkle Patricia Trie 的樣子：

Merkel Patricia Trie 類似於正常的Trie 資料結構，但具有三種類型的節點

• 擴展節點- 包含多個節點通用的鍵的一部分，並包含對下一個節點的引用
• 分支節點- 包含指向具有相同鍵前綴的不同節點的指針
• 葉節點- 包含一個值和鍵的剩餘部分（稱為key-end）。葉節點的鍵是來自其所有父節點的前綴和葉節點中的前綴的串聯key-end。

由於擴展節點只有一個指向另一個節點的指針，它似乎總是指向一個分支節點。如果它指向一個葉節點，這些節點可以組合成一個葉節點。如果它指向另一個擴展節點，那麼這兩個擴展節點可以組合成一個擴展節點。

為什麼我們需要分離擴展節點和分支節點？分支節點的所有分支都可以直接嵌入到擴展節點中嗎？在這種情況下，我們只需：

• 擴展節點- 將包含兩個或多個其他節點的公共前綴，並具有指向其他節點的指針
• 葉節點- 將包含值和密鑰的剩餘部分

如果我理解正確，這將：

• 刪除一級間接
• 提高性能，因為 LevelDB 數據庫中的查找次數會更少

我錯過了什麼嗎？

我想，我有個主意。Modified Merkle Patricia Tree 的一個重要特性是它是版本化的。您可以使用帶有根雜湊的樹版本 1 H1，將新的鍵值對插入樹中，您將獲得帶有根雜湊的新樹版本 2 H2。但是，H1仍將在數據庫中，仍可訪問，並且仍表示完整的樹版本 1。這種限制也非常節省空間，因為大多數節點將保持不變並在樹版本之間共享。只有添加的鍵值對路徑上的節點才會是新的。

現在，分支節點（17 個元素）比擴展節點（2 個元素）大得多。（據我所知，這是區分彼此的唯一方法。）因此，我們希望在將樹更新到新版本時盡可能保持它們不被修改。

現在想像一下，您有一個組合的擴展分支節點 N1，其前綴為12345。我們正在使用 key 插入一個新值123ffaaee。我們必須：

• 將 N1 替換為帶有前綴的新分支節點 N2123
• 為 N2 分支插入一個新的葉節點 N3 f（帶前綴faaee）
• 將 N1 複製到 N4，僅修改其前綴 from 12345to5並將其附加到 N2 分支4。

現在我們有兩個大的擴展分支節點 N1 和 N4，它們具有相同的分支部分，只是前綴不同。如果我們使用單獨的擴展節點和分支節點，我們就不必複製分支節點，只需將其擴展父節點分成兩部分。

這裡的一個重要的架構決策是，我們更關心樹的性能而不是它的足跡（它只會隨著每筆交易而增長，必須保留在每個完整的乙太坊節點上，因此構成威脅乙太坊的可擴展性）。

但是，我也看到了我的邏輯中的一個缺陷：如果有一個帶有前綴的分支節點，那麼它很可能沒有很多分支。在這種情況下，它不會佔用很大的空間，因為RLP編碼將null使用單個字節對每個分支進行編碼。

可能是一個虎頭蛇尾的答案，但問題是黃皮書似乎將 trie 的工作原理作為實現細節。它在附錄 D 中說：

trie 的核心，以及它在協議規範方面的唯一要求是提供一個單一的值來標識一組給定的鍵值對，它可以是 32 字節序列或空字節序列。以允許有效和高效地實現協議的方式儲存和維護 trie 的結構，作為實現的考慮因素。

……雖然剛剛說它繼續談論像這3種節點這樣的實現優化。

所以你的想法可能是另一種可能的實現。哪一個最好？可能只有一些研究會決定。

乙太坊中的一些設計決策可能會更好，尤其是在事後諸葛亮的情況下。這可能是其中之一（或不是）。

引用自：https://ethereum.stackexchange.com/questions/57486