一、什么是 Merkle Tree慕嚷？
Merkle Tree潘拨，是一種樹（數(shù)據(jù)結(jié)構(gòu)中所說的樹）卒暂，網(wǎng)上大都稱為Merkle Hash Tree,這是因為 它所構(gòu)造的Merkle Tree的所有節(jié)點都是Hash值。Merkle Tree具有以下特點：
- 它是一種樹撞叽，可以是二叉樹姻成，也可以多叉樹，無論是幾叉樹能扒，它都具有樹結(jié)構(gòu)的所有特點佣渴；
- Merkle樹的葉子節(jié)點上的value，是由你指定的初斑，這主要看你的設(shè)計了辛润，如Merkle Hash Tree會將數(shù)據(jù)的Hash值作為葉子節(jié)點的值；
3 非葉子節(jié)點的value是根據(jù)它下面所有的葉子節(jié)點值，然后按照一定的算法計算而得出的砂竖。如Merkle Hash Tree的非葉子節(jié)點value的計算方法是將該節(jié)點的所有子節(jié)點進(jìn)行組合真椿，然后對組合結(jié)果進(jìn)行hash計算所得出的hash value。
例如乎澄，下圖就是一個Merkle Hash Tree形狀突硝，如果它是Merkle Hash Tree，則節(jié)點7的hash value必須是通過節(jié)點15置济、16上的value計算而得到.
二解恰、 Merkle Tree的應(yīng)用
Git 版本控制系統(tǒng)，ZFS 文件系統(tǒng)以及我們自己下載電影常用的點對點網(wǎng)絡(luò) BT 下載浙于，都是通過 Merkle Tree 來進(jìn)行完整性校驗的护盈。
目前， 在計算機(jī)領(lǐng)域羞酗，Merkle Tree大多用來進(jìn)行比對以及驗證處理腐宋。比特幣錢包服務(wù)用 Merkle Tree 的機(jī)制來作”百分百準(zhǔn)備金證明“ 。在處理比對或驗證的應(yīng)用場景中時檀轨，特別是在分布式環(huán)境下進(jìn)行比對或驗證時胸竞，Merkle Tree會大大減少數(shù)據(jù)的傳輸量以及計算的復(fù)雜度。例如参萄，就拿圖一舉例卫枝，假如是 15,16.......30是一個個數(shù)據(jù)塊的hash值，我把這些數(shù)據(jù)從A傳輸?shù)紹拧揽，數(shù)據(jù)傳輸?shù)紹后剃盾，我想驗證下傳輸?shù)紹上的數(shù)據(jù)的有效性型（驗證數(shù)據(jù)是否在傳輸過程中發(fā)生變化），只需要驗證A 和 B上所構(gòu)造的Merkle Tree的root節(jié)點值是否一致即可淤袜，如果一致痒谴，表示數(shù)據(jù)是有效的，傳輸過程中沒有發(fā)生改變铡羡。假如在傳輸過程中积蔚，15對應(yīng)的數(shù)據(jù)被人篡改，通過Merkle Tree很容易定位找到（因為此時烦周，節(jié)點0,1,3,7,15對應(yīng)的hash值都發(fā)生了變化）尽爆，定位的時間復(fù)雜度為O（log(n））
三、Merkle Tree的優(yōu)點
相對于 Hash List读慎，Merkle Tree 的明顯的一個好處是可以單獨(dú)拿出一個分支來（作為一個小樹）對部分?jǐn)?shù)據(jù)進(jìn)行校驗漱贱，這個很多使用場合就帶來了哈希列表所不能比擬的方便和高效。
