詳談樹結(jié)構(gòu)（傳統(tǒng)樹、字典樹、hash 樹、Merkle Patricia Tree）

關于數(shù)據(jù)結(jié)構(gòu)中樹結(jié)構(gòu)的相關分享

本文參考： 樹結(jié)構(gòu)參考文獻

一、傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中的樹結(jié)構(gòu)

  • 樹結(jié)構(gòu)是一種非線性存儲結(jié)構(gòu)，存儲的是具有“一對多”關系的數(shù)據(jù)元素的集合。

[圖片上傳失敗...(image-83b557-1539180310707)]

  • 其中，討論較多的是二叉樹。二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。

1.1 二叉查找樹

  • 二叉查找樹定義：又稱二叉排序樹或二叉搜索樹。二叉排序樹或者是一棵空樹，具有下列性質(zhì)：
  1. 左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；右子樹均大于或等于它的根結(jié)點的值；
  2. 左、右子樹也分別為二叉排序樹；
  • 特點：
    • 二叉查找樹的性質(zhì)：對二叉查找樹進行中序遍歷，即可得到有序的數(shù)列。
    • 二叉查找樹的高度決定了二叉查找樹的查找效率。

1.2 平衡二叉樹

  • 為了讓二叉搜索樹的期望高度為 log2n，即使得各操作的時間復雜度為 O(log2n), 于是有了平衡二叉樹(即 AVL樹)。
  • 定義：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
  • 最小二叉平衡樹的節(jié)點的公式如下： F(n)=F(n-1)+F(n-2)+1

1.3 平衡二叉樹之紅黑樹

  • 定義：紅黑樹是一種自平衡二叉查找樹，其典型的用途是實現(xiàn)關聯(lián)數(shù)組(比如 C++ 中的 STL 中的map,和 set 等關聯(lián)式容器都是基于紅黑樹的)。
  • 它可以在O(logn)時間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。這使得它可以適用于實時應用（real time application）。
  • 紅黑樹還是2-3-4樹的一種等同，它們的思想是一樣的，只不過紅黑樹是2-3-4樹用二叉樹的形式表示的。
  • 2-3-4 樹把數(shù)據(jù)存儲在叫做元素的單獨單元中。它們組合成節(jié)點。每個節(jié)點都是下列之一：
    • 2-節(jié)點，就是說，它包含 1 個元素和 2 個兒子；
    • 3-節(jié)點，就是說，它包含 2 個元素和 3 個兒子；
    • 4-節(jié)點，就是說，它包含 3 個元素和 4 個兒子。
  • 如下圖(所示)：

[圖片上傳失敗...(image-d6bf01-1539180310707)]

  • 紅黑樹的性質(zhì)：
    紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。除了二叉查找樹特有性質(zhì)之外，紅黑樹還增加了如下要求:

性質(zhì)1. 節(jié)點是紅色或黑色，根是黑色，所有葉子都是黑色

性質(zhì)2. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點，即紅黑相間)，從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(簡稱黑高)。

  • 紅黑樹的圖例，如下：

[圖片上傳失敗...(image-52c714-1539180310707)]

  • 性質(zhì)分析：
    • 有了上面的幾個性質(zhì)作為限制，即可避免二叉查找樹退化成單鏈表的情況。但是，僅僅避免這種情況還不夠，這里還要考慮某個節(jié)點到其每個葉子節(jié)點路徑長度的問題。如果某些路徑長度過長，那么，在對這些路徑上的及誒單進行增刪查操作時，效率也會大大降低。這個時候性質(zhì)4和性質(zhì)5用途就凸顯了，有了這兩個性質(zhì)作為約束，即可保證任意節(jié)點到其每個葉子節(jié)點路徑最長不會超過最短路徑的2倍。
    • 原因如下：
    • 當某條路徑最短時，這條路徑必然都是由黑色節(jié)點構(gòu)成。當某條路徑長度最長時，這條路徑必然是由紅色和黑色節(jié)點相間構(gòu)成（性質(zhì)限定了不能出現(xiàn)兩個連續(xù)的紅色節(jié)點）。而性質(zhì)又限定了從任一節(jié)點到其每個葉子節(jié)點的所有路徑必須包含相同數(shù)量的黑色節(jié)點。此時，在路徑最長的情況下，路徑上紅色節(jié)點數(shù)量 = 黑色節(jié)點數(shù)量。該路徑長度為兩倍黑色節(jié)點數(shù)量，也就是最短路徑長度的2倍。(如下圖)
在這里插入圖片描述
  • 紅黑樹的自平衡調(diào)整操作：
    • 因為每一個紅黑樹也是一個特化的二叉查找樹，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。
    • 此外，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質(zhì)?；謴图t黑樹的性質(zhì)需要少量(O(logn))的顏色變更(實際是非?？焖俚?和不超過三次樹旋轉(zhuǎn)結(jié)構(gòu)變更(對于插入操作是兩次)。
    • 雖然插入和刪除很復雜，但操作時間仍可以保持為 O(logn) 次。
    • 具體的插入、構(gòu)建、刪除、和調(diào)整操作(代碼相關的)，可參見維基百科。
    • 紅黑樹調(diào)整

1.4 B 樹

  • B樹也是一種用于查找的平衡樹，但是它不是二叉樹，它是多路搜索樹。
  • 定義： B樹（B-tree）是一種樹狀數(shù)據(jù)結(jié)構(gòu)，能夠用來存儲排序后的數(shù)據(jù)。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、循序存取、插入數(shù)據(jù)及刪除的動作，都在對數(shù)時間內(nèi)完成。B樹即一般化的二叉查找樹，可以擁有多于2個子節(jié)點。與自平衡二叉查找樹不同，B樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。這種數(shù)據(jù)結(jié)構(gòu)常被應用在數(shù)據(jù)庫和文件系統(tǒng)的實現(xiàn)上。
    <br />
  • B樹作為一種多路搜索樹（并不是二叉的）的性質(zhì)：
    1. 定義任意非葉子結(jié)點最多只有M個兒子；且M>2；
    2. 根結(jié)點的兒子數(shù)為[2, M], 非根非葉子結(jié)點的兒子數(shù)為[M/2, M]；
    3. 每個結(jié)點存放至少 M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
    4. 非葉子結(jié)點的關鍵字個數(shù) = 指向兒子的指針個數(shù)-1；
    5. 非葉子結(jié)點的關鍵字有序：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
    6. 非葉子結(jié)點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，
      P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
    7. 所有葉子結(jié)點位于同一層；
      <br />
  • M=3 的 B 樹示例圖：
    [圖片上傳失敗...(image-c2cd3-1539180310707)]
    <br />
  • 比起正常的平衡二叉樹，B樹每個節(jié)點顯然能存儲的數(shù)據(jù)更多，在查找數(shù)據(jù)方面也顯得比較高效。
  • B樹創(chuàng)建的示意圖：
    <br />
    B 樹生成示意圖

1.5 B+樹

B+樹是B樹的變體，也是一種多路搜索樹：

  1. 其定義基本與B-樹相同，除了：
  2. 非葉子結(jié)點的子樹指針與關鍵字個數(shù)相同；
  3. 非葉子結(jié)點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）；
  4. 為所有葉子結(jié)點增加一個鏈指針；
  5. 所有關鍵字都在葉子結(jié)點出現(xiàn)；
  • 下圖為 M=3 的 B+ 樹的示意圖

[圖片上傳失敗...(image-c2ce8e-1539180310707)]

  • B+樹的搜索與B樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B樹可以在非葉子結(jié)點命中），其性能也等價于在關鍵字全集做一次二分查找；

B+ 樹的性質(zhì)：
1.所有關鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；
2.不可能在非葉子結(jié)點命中；
3.非葉子結(jié)點相當于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當于是存儲（關鍵字）數(shù)據(jù)的數(shù)據(jù)層；
4.更適合文件索引系統(tǒng)。

  • B + 樹的創(chuàng)建示意圖：
    <br />

    創(chuàng)建示意圖

  • B 樹和 B+ 樹的異同：

    • 結(jié)構(gòu)上
      • B樹中關鍵字集合分布在整棵樹中，葉節(jié)點中不包含任何關鍵字信息，而B+樹關鍵字集合分布在葉子結(jié)點中，非葉節(jié)點只是葉子結(jié)點中關鍵字的索引；
      • B樹中任何一個關鍵字只出現(xiàn)在一個結(jié)點中，而B+樹中的關鍵字必須出現(xiàn)在葉節(jié)點中，也可能在非葉結(jié)點中重復出現(xiàn)；
    • 性能上（也即為什么說B+樹比B樹更適合實際應用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引？）
      • 不同于B樹只適合隨機檢索，B+樹同時支持隨機檢索和順序檢索；
      • B+樹的磁盤讀寫代價更低。B+樹的內(nèi)部結(jié)點并沒有指向關鍵字具體信息的指針，其內(nèi)部結(jié)點比B樹小，盤塊能容納的結(jié)點中關鍵字數(shù)量更多，可一次性將索引讀入內(nèi)存中可以查找的關鍵字也就越多，相對的，IO讀寫次數(shù)也就降低了。而IO讀寫次數(shù)是影響索引檢索效率的最大因素。也就是說同樣數(shù)據(jù)情況下，B+ 樹會 B 樹更加“矮胖”，因此查詢效率更快。
      • B+樹的查詢效率更加穩(wěn)定。B樹搜索有可能會在非葉子結(jié)點結(jié)束，越靠近根節(jié)點的記錄查找時間越短，只要找到關鍵字即可確定記錄的存在，其性能等價于在關鍵字全集內(nèi)做一次二分查找。而在B+樹中，順序檢索比較明顯，隨機檢索時，任何關鍵字的查找都必須走一條從根節(jié)點到葉節(jié)點的路，所有關鍵字的查找路徑長度相同，導致每一個關鍵字的查詢效率相當。
      • （數(shù)據(jù)庫索引采用B+樹的主要原因是，）B-樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題。B+樹的葉子節(jié)點使用指針順序連接在一起，只要遍歷葉子節(jié)點就可以實現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作（或者說效率太低）。

1.6 B* 樹

  • B* 樹是 B+ 樹的變體，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針，將結(jié)點的最低利用率從1/2提高到2/3。
    <br />

  • 圖示如下：
    [圖片上傳失敗...(image-7bba3e-1539180310707)]

  • B* 樹定義了非葉子結(jié)點關鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）；

  • B+樹的分裂：當一個結(jié)點滿時，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針；B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點，所以它不需要指向兄弟的指針；

  • B*樹的分裂：當一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿，那么將一部分數(shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關鍵字，最后修改父結(jié)點中兄弟結(jié)點的關鍵字（因為兄弟結(jié)點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復制1/3的數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點的指針；

所以，B*樹分配新結(jié)點的概率比B+樹要低，空間使用率更高。

二、字典樹 ( Trie樹 )

Tire樹稱為字典樹，又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。

Tire樹的三個基本性質(zhì)：

  1. 根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符；
  2. 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應的字符串；
  3. 每個節(jié)點的所有子節(jié)點包含的字符都不相同。

Tire樹的應用：

  • 串的快速檢索

給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。在這道題中，我們可以用數(shù)組枚舉，用哈希，用字典樹，先把熟詞建一棵樹，然后讀入文章進行比較，這種方法效率是比較高的。

  • “串”排序

給定N個互不相同的僅由一個單詞構(gòu)成的英文名，讓你將他們按字典序從小到大輸出。用字典樹進行排序，采用數(shù)組的方式創(chuàng)建字典樹，這棵樹的每個結(jié)點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。

  • 最長公共前綴

對所有串建立字典樹，對于兩個串的最長公共前綴的長度即他們所在的結(jié)點的公共祖先個數(shù)，于是，問題就轉(zhuǎn)化為求公共祖先的問題。

三、決策樹(利用信息論的熵依靠決策樹做決策選擇)

  • 作為一個Coder,經(jīng)常遇到敲if, else if, else,其實就就是決策樹的思想。只是這么多條件，哪個條件特征先做if，哪個條件特征后做if比較優(yōu)呢？怎么準確定量選擇這個標準就是決策樹算法的要做的事情。
  • 信息論中熵的概念。熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變量X的熵的表達式如下：
  • 單隨機變量 X 的熵

H(X) = -\sum\limits_{i=1}^{n}p_i logp_i

  • 雙變量 X和Y 的聯(lián)合熵
    H(X,Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)
  • 條件熵的表達式H(X|Y)，條件熵類似于條件概率,它度量了我們的X在知道Y以后剩下的不確定性。表達式如下：

H(X|Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)

  • 根據(jù)決策樹構(gòu)建的過程，可以按照特征選擇方式分成如下三種大類：

[圖片上傳失敗...(image-f00bd3-1539180310707)]

  • 信息增益(又稱為互信息),定義為： H(X) - H(X|Y) ,記為I(X,Y)。
  • 在決策樹 ID3 算法中叫做信息增益。ID3算法就是用信息增益來判斷當前節(jié)點應該用什么特征來構(gòu)建決策樹。信息增益大，則越適合用來分類。
  • ID3 的缺點：
    • 沒有考慮連續(xù)特征，比如長度，密度都是連續(xù)值，無法在ID3運用。
    • 取值比較多的特征比取值少的特征信息增益大。
    • ID3算法對于缺失值的情況沒有做考慮等
    • 沒有考慮過擬合的問題
  • 于是提出了 C4.5
    • 對于使用信息增益作為標準容易偏向于取值較多的特征的問題。引入一個信息增益率的變量Ir(X,Y)，它是信息增益和特征熵的比值。表達式如下：

I_R(D,A) = \frac{I(A,D)}{H_A(D)}

  • C4.5 的缺點：
    • 決策樹算法非常容易過擬合
    • C4.5生成的是多叉樹，在計算機科學中二叉樹往往運算效率更高。
    • C4.5只能用于分類，如果能將決策樹用于回歸的話可以擴大它的使用范圍。
    • C4.5由于使用了熵模型，里面有大量的耗時的對數(shù)運算,如果是連續(xù)值還有大量的排序運算。是否可以通過適當?shù)慕档徒Y(jié)果準確性來簡化模型的運算強度。
  • 前面兩種方式都是基于信息論的熵模型，有耗時的計算問題，CART分類樹算法使用基尼系數(shù)來代替信息增益比，基尼系數(shù)代表了模型的不純度，基尼系數(shù)越小，則不純度越低，特征越好。這和信息增益(比)是相反的。(其實就是加了一個負號，對比信息熵的定義)
  • 在分類問題中，假設有K個類別，第k個類別的概率為pk, 則基尼系數(shù)的表達式為：

Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2

  • 如果是二類分類問題，概率是p，則基尼系數(shù)簡化為：

Gini(p) = 2p(1-p)

[圖片上傳失敗...(image-d70c23-1539180310707)]

四、梅克爾帕特里夏樹( Merkle Patricia Tree, MPT)

  • MPT: 基于加密學的，自校驗防篡改的數(shù)據(jù)結(jié)構(gòu)，用來存儲鍵值對關系。MPT是確定的。確定性是指同樣內(nèi)容的鍵值，將被保證找到同樣的結(jié)果，有同樣的根哈希。關于效率方面，對樹的插入，查找，刪除的時間復雜度控制在O(log(n))。
  • 前言：基數(shù)樹（Radix Tree）
  • 在一個標準的基數(shù)樹里，要存儲的數(shù)據(jù)，按下述所述：
[i0, i1, ... iN, value]
  • 其中的i0到iN的表示一般是二進制或十六進制的格式的字母符號。value表示的是樹節(jié)點中存儲的最終值。每一個i0到iN槽位的值，要么是NULL，要么是指向另一個節(jié)點的指針（在當前這個場景中，存儲的是其它節(jié)點的哈希值）。這樣我們就實現(xiàn)了一個簡單的鍵值對存儲。舉個例子來說，如果你想在這個基數(shù)樹中，找到鍵dog所對應的值。首先需要將dog轉(zhuǎn)換為比如ascii碼值（十六進制表示是646f67）。然后按字母序形成一個逐層向下的樹。沿著字母組成的路徑，在樹的底部葉節(jié)點上，即找到dog對應的值。具體來說，首先找到存儲這個鍵值對數(shù)據(jù)的根節(jié)點，找到下一層的第6個節(jié)點，然后再往下一層，找到節(jié)點4，然后一層一層往下找，直到完成了路徑 root -> 6 -> 4 -> 6 -> f -> 6 -> 7。這樣你將最終找到值的對應節(jié)點。
  • 基數(shù)樹的缺點:
    • 基數(shù)樹另一個主要的缺陷是低效。即使你只想存一個鍵值對，但其中的鍵長度有幾百字符長，那么每個字符的那個層級你都需要大量的額外空間。每次查找和刪除都會有上百個步驟。在這里我們引入Patricia樹來解決這個問題。
  • Patricia 樹
  • Patricia樹，或稱Patricia trie，或 crit bit tree，壓縮前綴樹，是一種更節(jié)省空間的Trie。對于基數(shù)樹的每個節(jié)點，如果該節(jié)點是唯一的兒子的話，就和父節(jié)點合并。

[圖片上傳失敗...(image-8a3963-1539180310707)]

  • Merkle 樹
  • Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹。Merkle樹的葉子是數(shù)據(jù)塊(例如，文件或者文件的集合)的hash值。非葉節(jié)點是其對應子節(jié)點串聯(lián)字符串的hash。
  • Merkle Tree 由 Hash List演化而來：
  • 在點對點網(wǎng)絡中作數(shù)據(jù)傳輸?shù)臅r候，會同時從多個機器上下載數(shù)據(jù)，而且很多機器可以認為是不穩(wěn)定或者不可信的。為了校驗數(shù)據(jù)的完整性，更好的辦法是把大的文件分割成小的數(shù)據(jù)塊（例如，把分割成2K為單位的數(shù)據(jù)塊）。這樣的好處是，如果小塊數(shù)據(jù)在傳輸過程中損壞了，那么只要重新下載這一快數(shù)據(jù)就行了，不用重新下載整個文件。
    怎么確定小的數(shù)據(jù)塊沒有損壞哪？只需要為每個數(shù)據(jù)塊做Hash。BT下載的時候，在下載到真正數(shù)據(jù)之前，我們會先下載一個Hash列表。那么問題又來了，怎么確定這個Hash列表本身是正確的哪？答案是把每個小塊數(shù)據(jù)的Hash值拼到一起，然后對這個長字符串在作一次Hash運算，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)。下載數(shù)據(jù)的時候，首先從可信的數(shù)據(jù)源得到正確的根Hash，就可以用它來校驗Hash列表了，然后通過校驗后的Hash列表校驗數(shù)據(jù)塊。

[圖片上傳失敗...(image-69461e-1539180310707)]

  • Merkle Tree 可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree。
  • 在最底層，和哈希列表一樣，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊，有相應地哈希和它對應。但是往上走，并不是直接去運算根哈希，而是把相鄰的兩個哈希合并成一個字符串，然后運算這個字符串的哈希，這樣每兩個哈希就結(jié)婚生子，得到了一個”子哈希“。如果最底層的哈?？倲?shù)是單數(shù)，那到最后必然出現(xiàn)一個單身哈希，這種情況就直接對它進行哈希運算，所以也能得到它的子哈希。于是往上推，依然是一樣的方式，可以得到數(shù)目更少的新一級哈希，最終必然形成一棵倒掛的樹，到了樹根的這個位置，這一代就剩下一個根哈希了，我們把它叫做 Merkle Root。

[圖片上傳失敗...(image-987993-1539180310707)]

  • 在p2p網(wǎng)絡下載網(wǎng)絡之前，先從可信的源獲得文件的Merkle Tree樹根。一旦獲得了樹根，就可以從其他從不可信的源獲取Merkle tree。通過可信的樹根來檢查接受到的MerkleTree。如果Merkle Tree是損壞的或者虛假的，就從其他源獲得另一個Merkle Tree，直到獲得一個與可信樹根匹配的MerkleTree。
  • Merkle Tree和HashList的主要區(qū)別是，可以直接下載并立即驗證 Merkle Tree的一個分支。因為可以將文件切分成小的數(shù)據(jù)塊，這樣如果有一塊數(shù)據(jù)損壞，僅僅重新下載這個數(shù)據(jù)塊就行了。如果文件非常大，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下載一個分支，然后立即驗證這個分支，如果分支驗證通過，就可以下載數(shù)據(jù)了。而Hash list只有下載整個hash list才能驗證。
  • MPT（Merkle Patricia Tree）樹****
  • MPT（Merkle Patricia Tree）就是這兩者混合的數(shù)據(jù)結(jié)構(gòu)。
  • MPT樹中的節(jié)點包括空節(jié)點、葉子節(jié)點、擴展節(jié)點和分支節(jié)點:
    • 空節(jié)點，簡單的表示空，在代碼中是一個空串。
    • 葉子節(jié)點（leaf），表示為[key,value]的一個鍵值對，其中key是key的一種特殊十六進制編碼，value是value的RLP編碼。
    • 擴展節(jié)點（extension），也是[key，value]的一個鍵值對，但是這里的value是其他節(jié)點的hash值，這個hash可以被用來查詢數(shù)據(jù)庫中的節(jié)點。也就是說通過hash鏈接到其他節(jié)點。
    • 分支節(jié)點（branch），因為MPT樹中的key被編碼成一種特殊的16進制的表示，再加上最后的value，所以分支節(jié)點是一個長度為17的list，前16個元素對應著key中的16個可能的十六進制字符，如果有一個[key,value]對在這個分支節(jié)點終止，最后一個元素代表一個值，即分支節(jié)點既可以搜索路徑的終止也可以是路徑的中間節(jié)點。
    • MPT 樹中另一個重要的概念是十六進制前綴(hex-prefix, HP)編碼，用來對key進行編碼。因為字母表是16進制的，所以每個節(jié)點可能有16個孩子。因為有兩種[key,value]節(jié)點(葉節(jié)點和擴展節(jié)點)，引進一種特殊的終止符標識來標識key所對應的是值是真實的值，還是其他節(jié)點的hash。如果終止符標記被打開，那么key對應的是葉節(jié)點，對應的值是真實的value。如果終止符標記被關閉，那么值就是用于在數(shù)據(jù)塊中查詢對應的節(jié)點的hash。
MPT

五、計算機科學中的樹結(jié)構(gòu)

[圖片上傳失敗...(image-58f33c-1539180310707)]

參考文獻：
1、http://blog.jobbole.com/111680/
2、https://blog.csdn.net/mine_song/article/details/63251546
3、https://www.cnblogs.com/pinard/p/6050306.html
4、https://blog.csdn.net/qq_33935254/article/details/55505472

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關系，并對這種結(jié)構(gòu)定義相應的運算，而且確保經(jīng)過這...
    Winterfell_Z閱讀 6,573評論 0贊 13
  • Merkle Tree概念 Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的...
    dtdh閱讀 1,115評論 2贊 3
  • B樹的定義 一棵m階的B樹滿足下列條件： 樹中每個結(jié)點至多有m個孩子。 除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少有m...
    文檔隨手記閱讀 13,659評論 0贊 25
  • 這是ActiveMQ系列的最后一篇文章，主要是關于ActiveMQ集群，這里采用的方式是：Zookeeper+Le...
    張豐哲閱讀 7,327評論 7贊 46

友情鏈接更多精彩內(nèi)容