轉(zhuǎn)載自：https://blog.csdn.net/qq_33935254/article/details/55505472

1 Trie樹

Trie樹，又稱前綴樹或字典樹肿男，是一種有序樹督勺，用于保存關(guān)聯(lián)數(shù)組注簿，其中的鍵通常是字符串待锈。與二叉查找樹不同湖员，鍵不是直接保存在節(jié)點(diǎn)中贫悄，而是由節(jié)點(diǎn)在樹中的位置決定。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴破衔，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串清女，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串钱烟。一般情況下晰筛，不是所有的節(jié)點(diǎn)都有對(duì)應(yīng)的值，只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的鍵才有相關(guān)的值拴袭。
在圖示中读第，鍵標(biāo)注在節(jié)點(diǎn)中，值標(biāo)注在節(jié)點(diǎn)之下拥刻。每一個(gè)完整的英文單詞對(duì)應(yīng)一個(gè)特定的整數(shù)怜瞒。鍵不需要被顯式地保存在節(jié)點(diǎn)中。圖示中標(biāo)注出完整的單詞，只是為了演示trie的原理吴汪。trie中的鍵通常是字符串惠窄，但也可以是其它的結(jié)構(gòu)。

image

上圖是一個(gè)簡略視圖漾橙，實(shí)際上trie每個(gè)節(jié)點(diǎn)是一個(gè)確定長度的數(shù)組杆融，數(shù)組中每個(gè)節(jié)點(diǎn)的值是一個(gè)指向子節(jié)點(diǎn)的指針，最后有個(gè)標(biāo)志域霜运，標(biāo)識(shí)這個(gè)位置為止是否是一個(gè)完整的字符串脾歇，并且有幾個(gè)這樣的字符串

常見的用來存英文單詞的trie每個(gè)節(jié)點(diǎn)是一個(gè)長度為27的指針數(shù)組，index0-25代表a-z字符淘捡，26為標(biāo)志域藕各。如圖：

image

2 Patricia樹

Patricia樹，或稱Patricia trie焦除，或crit bit tree激况，壓縮前綴樹，是一種更節(jié)省空間的Trie膘魄。對(duì)于基數(shù)樹的每個(gè)節(jié)點(diǎn)誉碴，如果該節(jié)點(diǎn)是唯一的兒子的話，就和父節(jié)點(diǎn)合并瓣距。

image

3 Merkle樹

Merkle Tree黔帕，通常也被稱作Hash Tree，顧名思義蹈丸，就是存儲(chǔ)hash值的一棵樹成黄。Merkle樹的葉子是數(shù)據(jù)塊(例如，文件或者文件的集合)的hash值逻杖。非葉節(jié)點(diǎn)是其對(duì)應(yīng)子節(jié)點(diǎn)串聯(lián)字符串的hash奋岁。（不懂Hash運(yùn)算的可以自行百度）

要了解Merkle Tree就要先從Hash List說起：

怎么確定小的數(shù)據(jù)塊沒有損壞哪？只需要為每個(gè)數(shù)據(jù)塊做Hash荸百。BT下載的時(shí)候闻伶，在下載到真正數(shù)據(jù)之前，我們會(huì)先下載一個(gè)Hash列表够话。那么問題又來了蓝翰，怎么確定這個(gè)Hash列表本事是正確的哪？答案是把每個(gè)小塊數(shù)據(jù)的Hash值拼到一起女嘲，然后對(duì)這個(gè)長字符串在作一次Hash運(yùn)算畜份，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)。下載數(shù)據(jù)的時(shí)候欣尼，首先從可信的數(shù)據(jù)源得到正確的根Hash爆雹，就可以用它來校驗(yàn)Hash列表了，然后通過校驗(yàn)后的Hash列表校驗(yàn)數(shù)據(jù)塊。

image

Merkle Tree可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree钙态，即樹高為2的多叉Merkle Tree慧起。

在最底層，和哈希列表一樣册倒，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊完慧，有相應(yīng)地哈希和它對(duì)應(yīng)。但是往上走剩失，并不是直接去運(yùn)算根哈希屈尼，而是把相鄰的兩個(gè)哈希合并成一個(gè)字符串，然后運(yùn)算這個(gè)字符串的哈希拴孤，這樣每兩個(gè)哈希就結(jié)婚生子脾歧，得到了一個(gè)”子哈希“演熟。如果最底層的哈媳拗矗總數(shù)是單數(shù)，那到最后必然出現(xiàn)一個(gè)單身哈希芒粹，這種情況就直接對(duì)它進(jìn)行哈希運(yùn)算兄纺，所以也能得到它的子哈希。于是往上推化漆，依然是一樣的方式谭网，可以得到數(shù)目更少的新一級(jí)哈希般码，最終必然形成一棵倒掛的樹，到了樹根的這個(gè)位置，這一代就剩下一個(gè)根哈希了殖妇，我們把它叫做 Merkle Root泛范。

image

在p2p網(wǎng)絡(luò)下載網(wǎng)絡(luò)之前刃鳄，先從可信的源獲得文件的Merkle Tree樹根孽文。一旦獲得了樹根，就可以從其他從不可信的源獲取Merkle tree璧帝。通過可信的樹根來檢查接受到的MerkleTree捍岳。如果Merkle Tree是損壞的或者虛假的，就從其他源獲得另一個(gè)Merkle Tree睬隶，直到獲得一個(gè)與可信樹根匹配的MerkleTree锣夹。

Merkle Tree和HashList的主要區(qū)別是，可以直接下載并立即驗(yàn)證Merkle Tree的一個(gè)分支理疙。因?yàn)榭梢詫⑽募蟹殖尚〉臄?shù)據(jù)塊晕城，這樣如果有一塊數(shù)據(jù)損壞泞坦，僅僅重新下載這個(gè)數(shù)據(jù)塊就行了窖贤。如果文件非常大，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下載一個(gè)分支赃梧，然后立即驗(yàn)證這個(gè)分支滤蝠，如果分支驗(yàn)證通過，就可以下載數(shù)據(jù)了授嘀。而Hash list只有下載整個(gè)hash list才能驗(yàn)證物咳。

4 MPT（Merkle Patricia Tree）樹

知道了Merkle Tree，知道了Patricia Tree蹄皱，顧名思義览闰，MPT（Merkle Patricia Tree）就是這兩者混合后的產(chǎn)物。

在以太坊（ethereum）中巷折，使用了一種特殊的十六進(jìn)制前綴(hex-prefix, HP)編碼压鉴，所以在字母表中就有16個(gè)字符。這其中的一個(gè)字符為一個(gè)nibble锻拘。

MPT樹中的節(jié)點(diǎn)包括空節(jié)點(diǎn)油吭、葉子節(jié)點(diǎn)、擴(kuò)展節(jié)點(diǎn)和分支節(jié)點(diǎn):

空節(jié)點(diǎn)署拟，簡單的表示空婉宰，在代碼中是一個(gè)空串。

葉子節(jié)點(diǎn)（leaf）推穷，表示為[key,value]的一個(gè)鍵值對(duì)心包，其中key是key的一種特殊十六進(jìn)制編碼，value是value的RLP編碼馒铃。

擴(kuò)展節(jié)點(diǎn)（extension）谴咸，也是[key，value]的一個(gè)鍵值對(duì)骗露，但是這里的value是其他節(jié)點(diǎn)的hash值岭佳，這個(gè)hash可以被用來查詢數(shù)據(jù)庫中的節(jié)點(diǎn)。也就是說通過hash鏈接到其他節(jié)點(diǎn)萧锉。

分支節(jié)點(diǎn)（branch）珊随，因?yàn)镸PT樹中的key被編碼成一種特殊的16進(jìn)制的表示，再加上最后的value柿隙，所以分支節(jié)點(diǎn)是一個(gè)長度為17的list叶洞，前16個(gè)元素對(duì)應(yīng)著key中的16個(gè)可能的十六進(jìn)制字符，如果有一個(gè)[key,value]對(duì)在這個(gè)分支節(jié)點(diǎn)終止禀崖，最后一個(gè)元素代表一個(gè)值衩辟，即分支節(jié)點(diǎn)既可以搜索路徑的終止也可以是路徑的中間節(jié)點(diǎn)。

MPT樹中另外一個(gè)重要的概念是一個(gè)特殊的十六進(jìn)制前綴(hex-prefix, HP)編碼波附，用來對(duì)key進(jìn)行編碼艺晴。因?yàn)樽帜副硎?6進(jìn)制的昼钻，所以每個(gè)節(jié)點(diǎn)可能有16個(gè)孩子。因?yàn)橛袃煞N[key,value]節(jié)點(diǎn)(葉節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn))封寞，引進(jìn)一種特殊的終止符標(biāo)識(shí)來標(biāo)識(shí)key所對(duì)應(yīng)的是值是真實(shí)的值然评，還是其他節(jié)點(diǎn)的hash。如果終止符標(biāo)記被打開狈究，那么key對(duì)應(yīng)的是葉節(jié)點(diǎn)碗淌，對(duì)應(yīng)的值是真實(shí)的value。如果終止符標(biāo)記被關(guān)閉抖锥，那么值就是用于在數(shù)據(jù)塊中查詢對(duì)應(yīng)的節(jié)點(diǎn)的hash亿眠。無論key奇數(shù)長度還是偶數(shù)長度，HP都可以對(duì)其進(jìn)行編碼磅废。最后我們注意到一個(gè)單獨(dú)的hex字符或者4bit二進(jìn)制數(shù)字缕探，即一個(gè)nibble。

HP編碼很簡單还蹲。一個(gè)nibble被加到key前（下圖中的prefix）爹耗，對(duì)終止符的狀態(tài)和奇偶性進(jìn)行編碼。最低位表示奇偶性谜喊，第二低位編碼終止符狀態(tài)潭兽。如果key是偶數(shù)長度，那么加上另外一個(gè)nibble斗遏，值為0來保持整體的偶特性山卦。

image

如圖所示:

總共有2個(gè)擴(kuò)展節(jié)點(diǎn)，2個(gè)分支節(jié)點(diǎn)诵次，4個(gè)葉子節(jié)點(diǎn)账蓉。

其中葉子結(jié)點(diǎn)的鍵值情況為：

image

節(jié)點(diǎn)的前綴：

image

5 MPT樹的操作

下面從MPT樹的更新，刪除和查找過程來說明MPT樹的操作逾一。

1 更新

函數(shù)_update_and_delete_storage(self, node, key, value)

i. 如果node是空節(jié)點(diǎn)铸本，直接返回[pack_nibbles(with_terminator(key)), value]，即對(duì)key加上終止符遵堵，然后進(jìn)行HP編碼箱玷。

image

ii. 如果node是分支節(jié)點(diǎn)，如果key為空陌宿，則說明更新的是分支節(jié)點(diǎn)的value锡足，直接將node[-1]設(shè)置成value就行了。如果key不為空壳坪，則遞歸更新以key[0]位置為根的子樹舶得，即沿著key往下找，即調(diào)用_update_and_delete_storage(self._decode_to_node(node[key[0]]),key[1:], value)爽蝴。

image

iii. 如果node是kv節(jié)點(diǎn)（葉子節(jié)點(diǎn)或者擴(kuò)展節(jié)點(diǎn)）沐批，調(diào)用_update_kv_node(self, node, key, value)纫骑，見步驟iv

iv. curr_key是node的key，找到curr_key和key的最長公共前綴珠插，長度為prefix_length惧磺。Key剩余的部分為remain_key颖对，curr_key剩余的部分為remain_curr_key捻撑。

a) 如果remain_key==[]== remain_curr_key，即key和curr_key相等缤底，那么如果node是葉子節(jié)點(diǎn)顾患，直接返回[node[0], value]。如果node是擴(kuò)展節(jié)點(diǎn)个唧，那么遞歸更新node所鏈接的子節(jié)點(diǎn)江解，即調(diào)用_update_and_delete_storage(self._decode_to_node(node[1]),remain_key, value)

image

b) 如果remain_curr_key == []，即curr_key是key的一部分徙歼。如果node是擴(kuò)展節(jié)點(diǎn)犁河，遞歸更新node所鏈接的子節(jié)點(diǎn)，即調(diào)用_update_and_delete_storage(self._decode_to_node(node[1]),remain_key, value)魄梯；如果node是葉子節(jié)點(diǎn)桨螺，那么創(chuàng)建一個(gè)分支節(jié)點(diǎn)，分支節(jié)點(diǎn)的value是當(dāng)前node的value酿秸，分支節(jié)點(diǎn)的remain_key[0]位置指向一個(gè)葉子節(jié)點(diǎn)灭翔，這個(gè)葉子節(jié)點(diǎn)是[pack_nibbles(with_terminator(remain_key[1:])),value]

image

c) 否則，創(chuàng)建一個(gè)分支節(jié)點(diǎn)辣苏。如果curr_key只剩下了一個(gè)字符肝箱，并且node是擴(kuò)展節(jié)點(diǎn)，那么這個(gè)分支節(jié)點(diǎn)的remain_curr_key[0]的分支是node[1]稀蟋，即存儲(chǔ)node的value煌张。否則，這個(gè)分支節(jié)點(diǎn)的remain_curr_key[0]的分支指向一個(gè)新的節(jié)點(diǎn)退客，這個(gè)新的節(jié)點(diǎn)的key是remain_curr_key[1:]的HP編碼唱矛，value是node[1]。如果remain_key為空井辜，那么新的分支節(jié)點(diǎn)的value是要參數(shù)中的value绎谦，否則，新的分支節(jié)點(diǎn)的remain_key[0]的分支指向一個(gè)新的節(jié)點(diǎn)粥脚，這個(gè)新的節(jié)點(diǎn)是[pack_nibbles(with_terminator(remain_key[1:])),value]

d) 如果key和curr_key有公共部分窃肠，為公共部分創(chuàng)建一個(gè)擴(kuò)展節(jié)點(diǎn)，此擴(kuò)展節(jié)點(diǎn)的value鏈接到上面步驟創(chuàng)建的新節(jié)點(diǎn)刷允，返回這個(gè)擴(kuò)展節(jié)點(diǎn)冤留；否則直接返回上面步驟創(chuàng)建的新節(jié)點(diǎn)

image

v. 刪除老的node碧囊，返回新的node

l 刪除

刪除的過程和更新的過程類似，而且很簡單纤怒，函數(shù)名：_delete_and_delete_storage(self, key)

i. 如果node為空節(jié)點(diǎn)糯而，直接返回空節(jié)點(diǎn)

ii. 如果node為分支節(jié)點(diǎn)。如果key為空泊窘，表示刪除分支節(jié)點(diǎn)的值熄驼，直接另node[-1]=‘’, 返回node的正規(guī)化的結(jié)果。如果key不為空烘豹，遞歸查找node的子節(jié)點(diǎn)瓜贾，然后刪除對(duì)應(yīng)的value，即調(diào)用self._delete_and_delete_storage(self._decode_to_node(node[key[0]]),key[1:])携悯。返回新節(jié)點(diǎn)

iii. 如果node為kv節(jié)點(diǎn)祭芦，curr_key是當(dāng)前node的key。

a) 如果key不是以curr_key開頭憔鬼，說明key不在node為根的子樹內(nèi)龟劲，直接返回node。

b) 否則轴或，如果node是葉節(jié)點(diǎn)昌跌，返回BLANK_NODE if key == curr_key else node。

c)如果node是擴(kuò)展節(jié)點(diǎn)侮叮，遞歸刪除node的子節(jié)點(diǎn)避矢，即調(diào)用_delete_and_delete_storage(self._decode_to_node(node[1]),key[len(curr_key):])。如果新的子節(jié)點(diǎn)和node[-1]相等直接返回node囊榜。否則审胸，如果新的子節(jié)點(diǎn)是kv節(jié)點(diǎn)，將curr_key與新子節(jié)點(diǎn)的可以串聯(lián)當(dāng)做key卸勺，新子節(jié)點(diǎn)的value當(dāng)做vlaue砂沛，返回。如果新子節(jié)點(diǎn)是branch節(jié)點(diǎn)曙求，node的value指向這個(gè)新子節(jié)點(diǎn)碍庵，返回。

l 查找

查找操作更簡單悟狱，是一個(gè)遞歸查找的過程函數(shù)名為：_get(self, node, key)

i. 如果node是空節(jié)點(diǎn)静浴，返回空節(jié)點(diǎn)

ii. 如果node是分支節(jié)點(diǎn)，如果key為空挤渐，返回分支節(jié)點(diǎn)的value苹享；否則遞歸查找node的子節(jié)點(diǎn)，即調(diào)用_get(self._decode_to_node(node[key[0]]), key[1:])

iii. 如果node是葉子節(jié)點(diǎn)浴麻，返回node[1] if key == curr_key else ‘’

iv. 如果node是擴(kuò)展節(jié)點(diǎn)得问，如果key以curr_key開頭囤攀，遞歸查找node的子節(jié)點(diǎn)，即調(diào)用_get(self._decode_to_node(node[1]),key[len(curr_key):])宫纬；否則焚挠，說明key不在以node為根的子樹里，返回空