例如，下圖是用十六叉樹表示的鍵值對 (170, v)。十六進位制中，170 記作 0xaa，因此你只需要兩層：第一層記錄第一個 a，第二層記錄第二個 a。
可以看出，上圖的樹很矮，而且很寬。給定相同的鍵值對，下圖展示了二叉樹儲存的情形。170 在二叉樹中被表示為 10101010。
問題在於：如果要對所有節點做雜湊，重新計算根雜湊的時間就太長了，因此，為了計算根節點的雜湊，礦工將從資料庫中檢索 同層節點的兄弟雜湊值（sibling hashes） 。雖然後者（礦工從資料庫檢索兄弟雜湊值）花費的時間沒有前者（礦工從資料庫庫得到所有的葉子節點並做雜湊）那麼多，這個操作還是很耗時。因為每個雜湊都必須從資料庫中取出。
在十六叉樹中，通常每一層你都需要取出 15 個兄弟雜湊值。在上面那個我構造的例子（圖 1）中，（重計算根雜湊）就需要 30 個雜湊值。
儘管二叉樹層次更深一點，但在每一層只需要一個兄弟雜湊值。在上述例子（圖 2）中，僅僅需要 8 個雜湊值！這就是為什麼在實際中二叉樹更優。
覆蓋層轉變方法
不幸的是，轉換為二叉樹並不簡單。需要轉換的資料 太多了，執行轉換花費的時間將多於 15 秒的區塊生成時間 。
除此以外，設想你要翻譯一本 5000 頁的書，作者還在不停地告訴你他們對故事做了些修改，並且這些修改會影響你已經翻譯過的頁 …… 那這個過程就沒完沒了。轉換狀態樹的格式也是一樣的問題：可能你剛完成某個地址的格式轉換，使用者就使用了該地址（因此更新了該地址的狀態），那你又得從頭轉換一遍（因為一個地址的狀態更新也會影響到整棵狀態樹）。
解決這個問題的辦法是增加一個過渡期，過渡期間，在十六叉樹基層上建立一棵覆蓋樹（overlay tree）。這棵覆蓋樹是二叉樹格式的，它的作用是儲存狀態上發生的所有變化，直到基層十六叉樹完全轉換為二叉樹。轉換分為 3 步進行。
第 1 步 —— 轉換
在這種方法下，區塊高度為 h2 時肯定會有 兩個 狀態根：一個是 “基層” 十六叉樹狀態根，一個是 “覆蓋層” 二叉樹狀態根。
十六叉樹被設定為只讀，因此對狀態的任何更新都將在覆蓋樹上進行。
當一筆交易讀取或者更新一個賬戶時，系統首先會搜尋覆蓋樹。如果在覆蓋樹中找不到賬戶，接著將會在舊的十六叉樹中搜尋值。
與此同時，十六叉樹在後臺進行轉換。此時不需要擔心值插入的問題，因為所有的改變都會儲存在上層的覆蓋樹中。
第 2 步 —— 基層樹切換
當後臺轉換過程完成，礦工對外宣告，他們已經準備好用轉換結果（只讀二叉樹根）來替換隻讀的十六進位制基層樹根。對狀態的讀寫與步驟 1 階段是一樣的。（譯者注：此時的只讀二叉基層樹是根據原本的十六進位制狀態樹得到的）
當足夠多的一系列區塊對轉換所得的二叉基層樹根給出了相同的值，意味著大多數礦工都完成了轉換，並且認可轉換後的樹。合併過程則開始。（譯者注：此時的合併是針對只讀二叉基層樹和可讀寫二叉覆蓋樹）
第 3 步 —— 合併兩棵樹
合併過程不斷推進：每產生一個新的區塊，就從覆蓋樹上刪除 n 個鍵，把它們重新插入二叉基層樹。此過程一直持續，直到所有的鍵都從覆蓋樹上移除。到達這步時，區塊頭就不再保留覆蓋狀態樹的樹根。
整個步驟的核心只有一個：如果交易執行時要寫的鍵存在於覆蓋樹上，這個鍵就會從覆蓋樹上刪除，寫操作直接在二叉基層樹上進行。
下一步
為了估計完成轉換所需要的時間，我已經做了一個低轉換率的原型系統。我們確信，整個過程花費的時間不會太離譜，也就是說幾天時間就夠了。我們會隨著演算法的改進而公佈更多細節。
致謝
此提議得益於 Alexey Akhunov、Vitalik Buterin、Anna George、Sina Mahmoodi、Tomasz Stanczak 以及 Martin H. Swende 的寶貴意見。
原文連結:
https://medium.com/@gballet/ethereum-state-tree-format-change-using-an-overlay-e0862d1bf201
作者: Guillaume Ballet
翻譯&校對: 裴奇 & 阿劍
