Merkle Tree厉亏，是一種樹(shù)（數(shù)據(jù)結(jié)構(gòu)中所說(shuō)的樹(shù)）引镊，網(wǎng)上大都稱(chēng)為Merkle Hash Tree,這是因?yàn)?它所構(gòu)造的Merkle Tree的所有節(jié)點(diǎn)都是Hash值。Merkle Tree具有以下特點(diǎn)：
1. 它是一種樹(shù)院溺，可以是二叉樹(shù)诞丽，也可以多叉樹(shù)，無(wú)論是幾叉樹(shù)迹栓，它都具有樹(shù)結(jié)構(gòu)的所有特點(diǎn)掉分；
2. Merkle樹(shù)的葉子節(jié)點(diǎn)上的value，是由你指定的克伊，這主要看你的設(shè)計(jì)了酥郭，如Merkle Hash Tree會(huì)將數(shù)據(jù)的Hash值作為葉子節(jié)點(diǎn)的值；
3 非葉子節(jié)點(diǎn)的value是根據(jù)它下面所有的葉子節(jié)點(diǎn)值愿吹，然后按照一定的算法計(jì)算而得出的不从。如Merkle Hash Tree的非葉子節(jié)點(diǎn)value的計(jì)算方法是將該節(jié)點(diǎn)的所有子節(jié)點(diǎn)進(jìn)行組合，然后對(duì)組合結(jié)果進(jìn)行hash計(jì)算所得出的hash value犁跪。
例如椿息，下圖就是一個(gè)Merkle Hash Tree形狀，如果它是Merkle Hash Tree耘拇，則節(jié)點(diǎn)7的hash value必須是通過(guò)節(jié)點(diǎn)15撵颊、16上的value計(jì)算而得到.
目前， 在計(jì)算機(jī)領(lǐng)域惫叛，Merkle Tree大多用來(lái)進(jìn)行比對(duì)以及驗(yàn)證處理倡勇。在處理比對(duì)或驗(yàn)證的應(yīng)用場(chǎng)景中時(shí)，特別是在分布式環(huán)境下進(jìn)行比對(duì)或驗(yàn)證時(shí)嘉涌，Merkle Tree會(huì)大大減少數(shù)據(jù)的傳輸量以及計(jì)算的復(fù)雜度妻熊。例如，就拿圖一舉例仑最，假如是 15,16.......30是一個(gè)個(gè)數(shù)據(jù)塊的hash值扔役，我把這些數(shù)據(jù)從A傳輸?shù)紹，數(shù)據(jù)傳輸?shù)紹后警医，我想驗(yàn)證下傳輸?shù)紹上的數(shù)據(jù)的有效性型（驗(yàn)證數(shù)據(jù)是否在傳輸過(guò)程中發(fā)生變化）亿胸，只需要驗(yàn)證A 和 B上所構(gòu)造的Merkle Tree的root節(jié)點(diǎn)值是否一致即可坯钦，如果一致，表示數(shù)據(jù)是有效的侈玄，傳輸過(guò)程中沒(méi)有發(fā)生改變婉刀。假如在傳輸過(guò)程中，15對(duì)應(yīng)的數(shù)據(jù)被人篡改序仙，通過(guò)Merkle Tree很容易定位找到（因?yàn)榇藭r(shí)突颊，節(jié)點(diǎn)0,1,3,7,15對(duì)應(yīng)的hash值都發(fā)生了變化），定位的時(shí)間復(fù)雜度為O（log(n））.
