資料結構中常見的樹

擊上方“ 一口Linux ”，選擇“ 置頂/星標公眾號 ”

乾貨福利，第一時間送達！

哈夫曼樹(Huffman Tree)

哈夫曼樹，又被稱為最優二叉樹，屬於帶權值二叉樹的一種。它的真實節點全部分佈在葉子節點中，是各種可能的組合中 WPL 值最小的形式。組合形式可能不唯一，但 WPL 值一定為最小。

介紹一下 WPL（Weighted Path Length），也就是 帶權路徑長度，說簡單一些就是【節點到根節點的路徑長度 * 該節點的權值】。說白了就是權值越大的節點，離根節點越近就對了。

WPL_A = 9x2+4x2+5x2+2x2 = 40
WPL_B = 9x1+5x2+4x3+2x3 = 37
WPL_C = 4x1+2x2+5x3+9x3 = 50

看一下上面這張圖和三個對應的 WPL 的值，很明顯可以看出來(b)是[9，4，5，2]這幾個節點對應的哈夫曼樹（的一種表現形式）。我們剛才也提了，哈夫曼樹組成的形式可能不唯一，就比如說把(b)映象過來看，也是哈夫曼樹。

哈夫曼樹的應用中，最有名的就是哈夫曼編碼了。通過這種編碼方式，可以使得整體編碼的長度最短。還需要說明的是，它是一種字首編碼，任何一個編碼值，都不會為其他編碼值的字首（最左子串）。

在 NLP(自然語言處理)領域劃時代之作—— word2vec 的過程中，也通過哈夫曼樹結構來加速查詢高頻詞語，有興趣的朋友可以瞭解一下。

最小生成樹(Minimum Spanning Tree)

最小生成樹，雖然叫做“樹”，但是它更多地出現在“圖”相關的知識中，描述的是將一個有權圖，轉化成 所有節點均可連通，並且連線兩邊的權值之和最小的樹形結構。提到這個，就肯定要說一下大名鼎鼎的 Prim 演算法 和 Kruskal 演算法，這兩種演算法分別是從 隨機頂點的角度 和 權值最小的邊的角度 出發，一步一步地選出適合的邊，然後最終形成一顆包含全部 n 個節點和 n-1 條邊的最小生成樹。

這方面比較經典的應用，就比如多個城市之間建鐵路，要求每個城市都連通、並且鐵路距離總和最小這種問題。後來我想想，送外賣的時候興許也能用到這個方法，該為 35 歲之後的職業生涯提前規劃起來了。

線段樹(Segment Tree)

線段樹，是一種特殊的平衡二叉查詢樹，每個葉子節點表示一個真實的節點資訊。而路徑上所有的非葉子節點，用來表示它包含的各層級子節點的範圍，並用於標記這個範圍內的一些資訊，比如範圍內的 max 值或 sum 值等。

線段樹可以較好地兼顧區間插入新資料和單點資料修改的邏輯。當更新葉子節點內容的時候，只要更新該節點對應路徑上的節點資訊即可。主要用於一些對範圍查詢有很高要求的場景。

值得一提的是，線段樹可以通過一個一維陣列來表示，如上圖中綠色數字所示（其中 10、11 為空缺資訊）。還需要說明的一點是，類似的概念還有區間樹，也有人將這兩個概念畫了等號，大家自行了解分辨。

伸展樹(Splay Tree)

伸展樹是一顆非平衡二叉搜尋樹。它的設計思路是基於一種假設：最頻繁被查詢的資訊，它（和它附近的節點）在下次查詢的時候更可能被查到。所以，通過 Splay Tree 查詢的時候，會隨著被查詢的資訊，反覆調整樹本身的結構，從而將經常被查詢到的節點，放到 root 附近。這樣就可能會加速查詢的效率。

這個乍一聽，有點像 LRU 或者 LFU 類似的結構，但又有所不同。首先，Splay Tree 中會保留所有的節點資訊，不存在過期（或超限）銷燬的情況。還有一點就是它並不是被查到之後立即置頂，會有一些其他的綜合考量（比如，每次最多進行兩次 n 次旋轉）。

看一下上面這張圖吧，它模擬的是（頻繁）查詢 R 的時候，Splay Tree 的變化情況。說白了就是把 R 節點放到根節點的位置，下次查起來就方便多了。Splay Tree 比較適合做快取，特別是在熱點資料相對集中的情況下，查詢效率很高。舉個應用的例子吧：我們常用的輸入法，當你輸入完拼音之後，會根據你的之前的選擇情況，優先出現某些詞語。但很多情況下，又不會直接把你上次選擇的詞語直接置頂，這就可以理解為是參考了伸展樹的思路（當今輸入法的排序，實際更多的應該是用 AI 演算法是做概率預測，而非單純的 Splay Tree）。

資料庫領域

資料庫中非常核心的一個部分，就是索引結構的設計——這幾乎決定了資料庫的應用領域。而索引結構的設計，又是資料結構和演算法的“重災區”。下面我們就來列舉幾種資料庫領域中，常見的樹結構。

B 樹

傳統的二叉樹中，每個節點中包含一個資訊，這樣如果節點數比較多，路徑就會很深。路徑深了，對應的問題就是查詢的過程中，需要經過更多的節點，從而造成效能下降。基於此，B 樹誕生了。

B 樹也屬於一種自然平衡樹。內部通過分裂機制，能夠保持資料的有序。它的單個節點中可以儲存 2~4 個資訊。單個節點內部有序，節點之間資訊的間隔，可以作為劃分下面部分的依據。

看上面這張圖，樹中一共有 10 個人資訊，按照紅黑樹的形式儲存，最長的路徑應該是 4。而通過 B 樹進行儲存，就會顯得“矮胖”了，對應的跨節點查詢次數也就縮短了。

B 樹比較適合於單點查詢的場景，比較常見的應用就是 MongoDB 了。當然了，B 樹也有一些不適合的場景，比如所有節點都放在磁碟上，則讀寫效能相對差；再比如說，如果我想查 5~9 範圍內的所有資料，用 B 樹是不是就需要在 3 個節點中反覆橫跳？

B+樹

B+樹就是為了解決上面丟擲的兩個問題而設計的。與 B 樹相同的是，B+樹的節點中也包含了多個資訊。但相比於 B 樹，B+樹做了一些改動：非葉子節點中僅保留資料之間的相對關係，而所有的真實資訊均包含在葉子節點中。這樣的話，相對關係資訊就可以放到記憶體中，而將所有節點資訊（可以認為量較大）保留在磁碟中。

每次查詢，通過相對關係，在記憶體中就可以快速的定位到具體的節點資訊，從而減少磁碟的 IO 次數。這樣做還有一個好處，可以通過一條“線”將所有葉子節點串聯起來，從而方便做範圍查詢。大名鼎鼎的 Mysql 的儲存引擎 InnoDB，使用的就是這種思路。

不知道有沒有朋友跟我一樣，在很長的一段時間內，把資料庫索引和 B+樹畫上了等號。其實不然，不同應用領域的資料庫，有著不同的索引結構。B+樹的資訊存放在磁碟中，且屬於非順序寫入，所以查詢效能很高，但寫入的效能偏低。在大資料儲存和日誌服務等需要頻繁寫入操作的領域，就有些不合適了——這就要引出我們接下來的話題了。

日誌結構化合並樹（Log Structured Merge Tree）

多年前，谷歌在發大據領域發表了Big Table相關論文，LSM 樹是其中的實現思路。我第一次聽說 LSM Tree，是有幸跟一位 HBase 領域的資深大佬一起喝茶的時候。當時我紅著臉表示，只聽說過其中的一部分。

與其說它是一種資料結構，其實它更像是基於此思想而衍生出的一系列演算法操作的集合。它描述了將實時產生的大批量資訊在記憶體中排序、更新，然後按批次順序寫入磁碟固化、合併的流程，從而兼顧了大批量資料的高效寫入儲存和範圍查詢等使用場景。

我們剛才提到，B+樹結構的儲存索引並不適合在頻繁寫入的場景，其中一個很重要的原因就是因為它屬於非順序寫入。而針對傳統磁碟來說，由於扇區物理結構輪轉，順序寫入的效能遠好於非順序寫入。

•隨機寫入磁碟慢了咋辦？

將非順序的資訊在記憶體中攢成有序的一批資訊（Segment），然後一次性寫入磁碟不就好了麼。

•攢批的時候，資料丟失或者程序崩潰了咋辦？

提前把資料寫到一個本地日誌檔案（WAL 機制）裡做備胎（不對，是備份）不就好了。

•需要在批量資料中做範圍查找了咋辦？

在記憶體中記錄每個 Segment（預設有序）的起止範圍，每次查詢的時候僅查詢範圍內的 Segment 不就好了。

•資料量太大，磁碟中的 Segment 太多，影響查詢效能了咋辦？

當每個 Segment 大到一定的程度的時候，把幾個 Segment 做歸併排序，然後合併到一個大的 Segment 裡不就好了麼。

•寫入資料之後，想刪除咋辦？

根據 key 找到最後一次寫入的資訊，打上墓碑記號。查詢到的時候，返回“這個真沒有”不就好了麼。

•墓碑記號太多，佔用大量記憶體，咋辦？•單點資訊查詢，資料太多，而且經常 miss，咋辦？•範圍查詢，不好確認從哪個 Segment 開始，咋辦？•...

隨著大資料的爆火，LSM Tree 被廣泛用於 KV 型資料庫和 OLAP 場景中，比如純序員熟悉（拼寫方式）的 HBase、Cassandra、LevelDB 等。相關領域的實際問題太多了，同樣的，解法也很多。有興趣的朋友可以深入瞭解一下。

end

點選“ 閱讀原文 ”檢視更多分享，歡迎 點分享、收藏、點贊、在看