前言
《最小可行性區(qū)塊鏈設(shè)計系列》的第六講(http://www.reibang.com/p/a5d0cde54990 ) 討論了網(wǎng)絡(luò)通訊的實現(xiàn)岸夯，本文繼續(xù)討論一個重要的數(shù)據(jù)結(jié)構(gòu)：PatriciaTrie。
本文的代碼地址：(https://github.com/qikh/mini-block-chain/commit/442dbec3794c6e1a2da35fb9895f502e7acb9d8e) (開發(fā)語言為Kotlin朋腋，更簡潔的Java)
正文
PatriciaTrie是以太坊的一個重要的數(shù)據(jù)結(jié)構(gòu)他炊，也被成為Merkle Patricia Tree盯孙，被以太坊用來存儲賬戶的狀態(tài)(Account State)羽利。
以太坊和比特幣相比一個顯著的區(qū)別就是實現(xiàn)了用戶賬戶體系，而比特幣的賬戶余額是通過檢索賬戶相關(guān)的交易記錄(Transaction)序苏，然后把未消費余額統(tǒng)計后得到的余額手幢。從程序設(shè)計的角度來看，比特幣是無狀態(tài)(Stateless)設(shè)計忱详，而以太坊是有狀態(tài)(Statefull)設(shè)計围来。以太坊的賬戶體系更容易理解和使用，但是實現(xiàn)者需要解決一個技術(shù)問題：區(qū)塊鏈分叉匈睁。
當(dāng)比特幣網(wǎng)絡(luò)分叉發(fā)生時监透，賬戶余額的計算只需要根據(jù)新的交易記錄重新計算一遍。但是以太坊的賬戶狀態(tài)是隨著交易記錄而變化的航唆，如果出現(xiàn)網(wǎng)絡(luò)分叉(沒有分叉勝出)就意味著同一個賬戶出現(xiàn)了兩個甚至多個臨時狀態(tài)胀蛮，最長的分叉勝出后賬戶狀態(tài)才恢復(fù)為一個。一種直觀的實現(xiàn)方式可以給每個分叉分配一個臨時id糯钙，每個分叉上都保留賬戶的一個副本粪狼。但是這樣會帶來大量的臨時數(shù)據(jù)I/O，影響到系統(tǒng)的運行性能任岸。PatriciaTrie正是為了解決網(wǎng)絡(luò)分叉時的賬戶狀態(tài)問題而設(shè)計的再榄。
Trie是一種字典樹數(shù)據(jù)結(jié)構(gòu)，其Key通常是字符串演闭，可以實現(xiàn)有序快速查找不跟，核心思想是以空間換區(qū)時間。中文資料可以看Merkle Patricia Tree (MPT) 樹詳解（http://ethfans.org/posts/Merkle-Patricia-Tree ）米碰，英文資料可以看Understanding the ethereum trie（https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/ ）和Climbing Ethereum Trie（http://ethereumj.io/blog/2015/07/05/Ethereum-Trie/ ）
以太坊的PatriciaTrie是Radix trie的一種實現(xiàn)窝革，優(yōu)化了Trie的空間效率，并且把Trie節(jié)點的Hash值和節(jié)點數(shù)據(jù)存入到Key-Value數(shù)據(jù)庫(leveldb)中吕座，通過根節(jié)點Hash的切換可以實現(xiàn)狀態(tài)樹的切換(對應(yīng)區(qū)塊鏈的分叉功能)虐译，Vitalik Buterin在https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/ 一文中對PatriciaTrie的設(shè)計思路進行了說明。最終的PatriciaTrie實現(xiàn)不但具備快速檢索功能吴趴，還具備了不同版本的狀態(tài)轉(zhuǎn)換功能漆诽，通俗理解可以類比Git的版本實現(xiàn)或MacOS的Timemachine功能。
MiniBlockChain在實現(xiàn)PatriciaTrie時參考了
Understanding the ethereum trie一文的Python代碼（https://github.com/ebuchman/understanding_ethereum_trie ）和EthereumJ的代碼锣枝。Python的代碼相比較EthereumJ的代碼結(jié)構(gòu)更加清晰合理厢拭，尤其是遞歸實現(xiàn)部分。Python的實現(xiàn)有三種節(jié)點類型：Leaf撇叁、Branch和Extension供鸠，節(jié)點插入、刪除和整理的邏輯比較復(fù)雜陨闹。EthereumJ只有Leaf和Branch節(jié)點楞捂，實現(xiàn)邏輯簡單很多薄坏，但是代碼結(jié)構(gòu)比較混亂。
大家可以對照著上文提到的中英文資料和代碼實現(xiàn)來理解PatriciaTrie的實現(xiàn)寨闹。
下文我們會繼續(xù)探討適合區(qū)塊鏈的智能合約語言設(shè)計胶坠。
注：
區(qū)塊鏈的企業(yè)端應(yīng)用場景（聯(lián)盟鏈和私鏈）通常不需要電子貨幣功能，也不需要代幣的激勵功能繁堡，因此區(qū)塊鏈層面的賬戶體系可有可無沈善。無狀態(tài)(Stateless)設(shè)計一方面可以降低空間占用，另一方面也降低了實現(xiàn)難度椭蹄，更加適合面向企業(yè)端的區(qū)塊鏈產(chǎn)品矮瘟。
