使用覆蓋層改變以太坊狀態樹的格式
編者按：本文來自以太坊愛好者（ID：ethfans）編者按：本文來自
以太坊愛好者（ID：ethfans）
以太坊愛好者（ID：ethfans）
背景
賬戶和合約存儲數據的方式是影響以太坊的眾多問題之一。以太坊協議選用了Merkle Patricia Tree（MPT，默克爾帕特里夏樹）來組織賬戶及合約數據。儘管這種數據結構在理論上效果很好，但在實際應用中，它帶來的問題卻比它能夠解決的問題多。核心開發者們已經討論多年，想要把這種數據結構換為二叉樹，我將在這篇文章中闡述我對這個問題的看法以及如何實現這種轉變。
背景
我所提議的處理方法包括一段時間的過渡期，在這段時間內，網絡要同時維護兩種樹結構。這樣做的好處是，轉換樹結構的過程不會影響鏈的運行，並且可以確保所有的賬戶都被轉換成了二進制格式。
圖片描述
背景
目前，以太坊的狀態樹是十六叉制的。十六叉製表示每個節點有16 個孩子節點。理論上講，這種方式挺好的，因為孩子節點多意味著只需要更少的“層” （即樹高）便可存儲所有數據。
圖片描述
圖片描述
- 圖1. 十六叉樹的例子，展示了值v 是如何在在對應鍵0xaa 處是存儲的。這棵樹的鍵長度只有2 個字節，只有沿著0xaa 的子樹被表現出來了。為了簡潔，不相關的子樹替換為“...” -
圖片描述
圖片描述
圖片描述
以太坊中，每個區塊包含一個stateRoot 字段，這是該塊處理完成後表示以太坊全局狀態的MPT 的樹根哈希值。總的來說，這個哈希值是對根節點的16 個孩子節點的哈希值所組成的列表作哈希運算得到的。這些孩子節點的哈希值又是孩子的16 個孩子節點的哈希值所組成的列表做哈希運算得到的，以此類推。
圖片描述
一級標題
一級標題
一級標題
二級標題
不幸的是，轉換為二叉樹並不簡單。需要轉換的數據太多了，執行轉換花費的時間將多於15 秒的區塊生成時間。
除此以外，設想你要翻譯一本5000 頁的書，作者還在不停地告訴你他們對故事做了些修改，並且這些修改會影響你已經翻譯過的頁…… 那這個過程就沒完沒了。轉換狀態樹的格式也是一樣的問題：可能你剛完成某個地址的格式轉換，用戶就使用了該地址（因此更新了該地址的狀態），那你又得從頭轉換一遍（因為一個地址的狀態更新也會影響到整棵狀態樹）。
圖片描述
圖片描述
圖片描述
二級標題
當一筆交易讀取或者更新一個賬戶時，系統首先會搜索覆蓋樹。如果在覆蓋樹中找不到賬戶，接著將會在舊的十六叉樹中搜索值。
圖片描述
二級標題
圖片描述
合併過程不斷推進：每產生一個新的區塊，就從覆蓋樹上刪除n 個鍵，把它們重新插入二叉基層樹。此過程一直持續，直到所有的鍵都從覆蓋樹上移除。到達這步時，區塊頭就不再保留覆蓋狀態樹的樹根。
下一步
二級標題
致謝下一步
