心中有“樹”！圖文并茂介紹數(shù)據(jù)結(jié)構(gòu)中常見的樹（二）
計算機科學(xué)家尼古拉斯·沃斯（Niklaus Wirth）曾說過：編程=數(shù)據(jù)結(jié)構(gòu)+算法?，可見數(shù)據(jù)結(jié)構(gòu)在編程中的重要性。
50 年過去了，計算機行業(yè)日新月異，大佬的這句名言是否還適用于當(dāng)下？使用成熟且豐富的框架已經(jīng)可以完成絕大部分任務(wù)的今天，基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)的知識，是否還有用武之地？
今天，我們繼續(xù)上一章的話題，聊一聊數(shù)據(jù)結(jié)構(gòu)中的樹（Tree），在實際的編程中應(yīng)用場景。
大家好，我是不會寫代碼的純序員——Chunel Feng，很高興又在這里跟各位紳士們見面了。在上一章中，我們介紹了 6 種常見的樹結(jié)構(gòu)（BST，AVL，RB Tree，Trie Tree、Radix Tree、Suffix Tree），以及使用場景和解決的問題。是不是感覺 hin 簡單，都把握住了？
今天，我們繼續(xù)圍繞這個話題展開，再多介紹幾種常見的樹型結(jié)構(gòu)。當(dāng)然了，主要目的還是梳理它們使用的場景和解決的問題。
哈夫曼樹(Huffman Tree)
哈夫曼樹，又被稱為最優(yōu)二叉樹，屬于帶權(quán)值二叉樹的一種。它的真實節(jié)點全部分布在葉子節(jié)點中，是各種可能的組合中 WPL 值最小的形式。組合形式可能不唯一，但 WPL 值一定為最小。
介紹一下 WPL（Weighted Path Length），也就是?帶權(quán)路徑長度，說簡單一些就是【節(jié)點到根節(jié)點的路徑長度 * 該節(jié)點的權(quán)值】。說白了就是權(quán)值越大的節(jié)點，離根節(jié)點越近就對了。
WPL_A = 9x2+4x2+5x2+2x2 = 40WPL_B = 9x1+5x2+4x3+2x3 = 37WPL_C = 4x1+2x2+5x3+9x3 = 50
看一下上面這章圖和三個對應(yīng)的 WPL 的值，很明顯可以看出來(b)是[9，4，5，2]這幾個節(jié)點對應(yīng)的哈夫曼樹（的一種表現(xiàn)形式）。我們剛才也提了，哈夫曼樹組成的形式可能不唯一，就比如說把(b)鏡像過來看，也是哈夫曼樹。
哈夫曼樹的應(yīng)用中，最有名的就是哈夫曼編碼了。通過這種編碼方式，可以使得整體編碼的長度最短。還需要說明的是，它是一種前綴編碼，任何一個編碼值，都不會為其他編碼值的前綴（最左子串）。
在 NLP(自然語言處理)領(lǐng)域劃時代之作——?word2vec?的過程中，也通過哈夫曼樹結(jié)構(gòu)來加速查詢高頻詞語，有興趣的朋友可以了解一下。
最小生成樹(Minimum Spanning Tree)
最小生成樹，雖然叫做“樹”，但是它更多的出現(xiàn)在“圖”相關(guān)的知識中，描述的是將一個有權(quán)圖，轉(zhuǎn)化成?所有節(jié)點均可連通，并且連接邊的權(quán)值之和最小的樹形結(jié)構(gòu)。
提到這個，就肯定要說一下大名鼎鼎的?Prim 算法?和?Kruskal 算法，這兩種算法分別從?隨機頂點的角度?和?權(quán)值最小的邊的角度?出發(fā)，一步一步的選出適合的邊，然后最終形成一顆包含全部 n 個節(jié)點和 n-1 條邊的最小生成樹。
這方面比較經(jīng)典的應(yīng)用，就比如多個城市之間建鐵路，要求每個城市都連通、并且鐵路距離總和最小這種問題。后來我想想，送外賣的時候興許也能用到這個方法，該為 35 歲之后的職業(yè)生涯提前規(guī)劃起來了。
線段樹(Segment Tree)
線段樹，是一種特殊的平衡二叉查找樹，每個葉子節(jié)點表示一個真實的節(jié)點信息。而路徑上所有的非葉子節(jié)點，用來表示它包含的各層級子節(jié)點的范圍，并用于標(biāo)記這個范圍內(nèi)的一些信息，比如范圍內(nèi)的 max 值或 sum 值等。
線段樹可以較好的兼顧區(qū)間插入新數(shù)據(jù)和單點數(shù)據(jù)修改的邏輯。當(dāng)更新葉子節(jié)點內(nèi)容的時候，只要更新該節(jié)點對應(yīng)路徑上的節(jié)點信息即可。主要用于一些對范圍查詢有很高要求的場景。
值得一提的是，線段樹可以通過一個一維數(shù)組來表示，如上圖中綠色數(shù)字所示（其中 10、11 為空缺信息）。還需要說明的一點是，類似的概念還有區(qū)間樹，也有人將這兩個概念畫了等號，大家自行了解分辨。
伸展樹(Splay Tree)
伸展樹是一顆非平衡二叉搜索樹。它的設(shè)計思路是基于一種假設(shè)：最頻繁被查詢的信息，它（和它附近的節(jié)點）在下次查詢的時候更可能被查到。所以，通過 Splay Tree 查詢的時候，會隨著被查詢的信息，反復(fù)調(diào)整樹本身的結(jié)構(gòu)，從而將經(jīng)常被查詢到的節(jié)點，放到 root 附近。這樣就可能會加速查詢效率。
這個乍一聽，有點像 LRU 或者 LFU 類似的結(jié)構(gòu)，但又有所不同。首先，Splay Tree 中會保留所有的節(jié)點信息，不存在過期（或超限）銷毀的情況。還有一點就是它并不是被查到之后立即置頂，會有一些其他的綜合考量（比如，每次最多進(jìn)行 n 次旋轉(zhuǎn)）。
看一下上面這張圖吧，它模擬的是（頻繁）查詢 R 的時候，Splay Tree 的變化情況。說白了就是把 R 節(jié)點放到根節(jié)點的位置，下次查起來就方便多了。
Splay Tree 比較適合做緩存，特別在熱點數(shù)據(jù)相對集中的情況下，查詢效率很高。舉個應(yīng)用的例子吧：我們常用的輸入法，當(dāng)你輸入完拼音之后，會根據(jù)你的之前選擇情況，優(yōu)先出現(xiàn)某些詞語。但很多情況下，又不會直接把你上次選擇的詞語直接置頂，這就可以理解為是參考了伸展樹的思路（當(dāng)今輸入法的排序，實際更多的應(yīng)該是用 AI 算法做概率預(yù)測，而非單純的 Splay Tree）。
數(shù)據(jù)庫領(lǐng)域
數(shù)據(jù)庫中非常核心的一個部分，就是索引結(jié)構(gòu)的設(shè)計——這幾乎決定了數(shù)據(jù)庫的應(yīng)用領(lǐng)域。而索引結(jié)構(gòu)的設(shè)計，又是數(shù)據(jù)結(jié)構(gòu)和算法的“重災(zāi)區(qū)”。下面我們幾種來列舉幾種數(shù)據(jù)庫領(lǐng)域中，常見的樹結(jié)構(gòu)。
B 樹
傳統(tǒng)的二叉樹中，每個節(jié)點中包含一個信息，這樣如果節(jié)點數(shù)比較多，路徑就會很深。路徑深了，對應(yīng)的問題就是查詢的過程中，需要經(jīng)過更多的節(jié)點，從而造成性能下降?；诖耍珺 樹誕生了。
B 樹也屬于一種自平衡樹。內(nèi)部通過分裂機制，能夠保持?jǐn)?shù)據(jù)的有序。它的單個節(jié)點中可以保存 2~4 個信息。單個節(jié)點內(nèi)部有序，節(jié)點之間信息的間隔，可以作為劃分下面部分的依據(jù)。
看上面這張圖，樹中一共有 10 個信息，按照紅黑樹的形式存儲，最長的路徑應(yīng)該是 4。而通過 B 樹進(jìn)行存儲，就會顯得“矮胖”了，對應(yīng)的跨節(jié)點查詢次數(shù)也就縮短了。
B 樹比較適合于單點查詢的場景，比較常見的應(yīng)用就是 MongoDB 了。當(dāng)然了，B 樹也有一些不適合的場景，比如所有節(jié)點都放在磁盤上，則讀寫性能相對差；再比如說，如果我想查 5~9 范圍內(nèi)的所有數(shù)據(jù)，用 B 樹是不是就需要在 3 個節(jié)點中反復(fù)橫跳？
B+樹
B+樹就是為了解決上面拋出的兩個問題而設(shè)計的。與 B 樹相同的是，B+樹的節(jié)點中也包含了多個信息。但相比于 B 樹，B+樹做了一些改動：非葉子節(jié)點中僅保留數(shù)據(jù)之間的相對關(guān)系，而所有的真實信息均包含在葉子節(jié)點中。這樣的話，相對關(guān)系信息就可以放到內(nèi)存中，而將所有節(jié)點信息（可以認(rèn)為量較大）保留在磁盤中。
每次查詢，通過相對關(guān)系，在內(nèi)存中就可以快速的定位到具體的節(jié)點信息，從而減少磁盤的 IO 次數(shù)。這樣做還有一個好處，可以通過一條“線”將所有葉子節(jié)點串聯(lián)起來，從而方便做范圍查詢。大名鼎鼎的 Mysql 的存儲引擎 InnoDB，使用的就是這種思路。
不知道有沒有朋友跟我一樣，在很長的一段時間內(nèi)，把數(shù)據(jù)庫索引和 B+樹畫上了等號。其實不然，不同應(yīng)用領(lǐng)域的數(shù)據(jù)庫，有著不同的索引結(jié)構(gòu)。B+樹的信息存放在磁盤中，且屬于非順序?qū)懭?，所以查詢性能很高，但寫入的性能偏低。在大?shù)據(jù)存儲和日志服務(wù)等需要頻繁寫入操作的領(lǐng)域，就有些不合適了——這就要引出我們接下來的話題了。
日志結(jié)構(gòu)化合并樹（Log Structured Merge Tree）
多年前，谷歌在發(fā)大據(jù)領(lǐng)域發(fā)表了Big Table相關(guān)論文，LSM 樹是其中的實現(xiàn)思路。我第一次聽說 LSM Tree，是有幸跟一位 HBase 領(lǐng)域的資深大佬一起喝茶的時候。當(dāng)時我紅著臉表示，只聽說過其中的一部分。
與其說它是一種數(shù)據(jù)結(jié)構(gòu)，其實它更像是基于此思想而衍生出的一系列算法操作的集合。它描述了將實時產(chǎn)生的大批量信息在內(nèi)存中排序、更新，然后按批次順序?qū)懭氪疟P固化、合并的流程，從而兼顧了大批量數(shù)據(jù)的高效寫入存儲和范圍查詢等使用場景。
我們剛才提到，B+樹結(jié)構(gòu)的存儲索引并不適合在頻繁寫入的場景，其中一個很重要的原因就是因為它屬于非順序?qū)懭?。而針對傳統(tǒng)磁盤來說，由于扇區(qū)物理結(jié)構(gòu)輪轉(zhuǎn)，順序?qū)懭氲男阅苓h(yuǎn)好于非順序?qū)懭搿?/p>
?隨機寫入磁盤慢了咋辦？
將非順序的信息在內(nèi)存中攢成有序的一批信息（Segment），然后一次性寫入磁盤不就好了么。
?攢批的時候，數(shù)據(jù)丟失或者進(jìn)程崩潰了咋辦？
提前把數(shù)據(jù)寫到一個本地日志文件（WAL 機制）里做備胎（不對，是備份）不就好了。
?需要在批量數(shù)據(jù)中做范圍查找了咋辦？
在內(nèi)存中記錄每個 Segment（默認(rèn)有序）的起止范圍，每次查詢的時候僅查詢范圍內(nèi)的 Segment 不就好了。
?數(shù)據(jù)量太大，磁盤中的 Segment 太多，影響查詢性能了咋辦？
當(dāng)每個 Segment 大到一定的程度的時候，把幾個 Segment 做歸并排序，然后合并到一個大的 Segment 里不就好了么。
?寫入數(shù)據(jù)之后，想刪除咋辦？
根據(jù) key 找到最后一次寫入的信息，打上墓碑記號。查詢到的時候，返回“這個真沒有”不就好了么。
?墓碑記號太多，占用大量內(nèi)存，咋辦？?單點信息查詢，數(shù)據(jù)太多，而且經(jīng)常 miss，咋辦？?范圍查詢，不好確認(rèn)從哪個 Segment 開始，咋辦？?...
隨著大數(shù)據(jù)的爆火，LSM Tree 被廣泛用于 KV 型數(shù)據(jù)庫和 OLAP 場景中，比如純序員熟悉（拼寫方式）的 HBase、Cassandra、LevelDB 等。相關(guān)領(lǐng)域的實際問題太多了，同樣的，解法也很多。有興趣的朋友可以深入了解一下。
本章小節(jié)
本章中，我們又介紹了幾種常見的樹形結(jié)構(gòu)和相關(guān)使用場景。旨在說明，Tree 在編碼、緩存、數(shù)據(jù)庫等領(lǐng)域也有著廣泛的應(yīng)用。特別需要強調(diào)的是，在數(shù)據(jù)庫的存儲引擎設(shè)計方面，Tree 可是占據(jù)了半壁江山，這其中還有沒有用到其他類型的樹？
那在類似人工智能這種圖結(jié)構(gòu)占據(jù)主導(dǎo)位置的領(lǐng)域，樹結(jié)構(gòu)是否有它的一技之長呢？還有什么行業(yè)，會涉及到樹結(jié)構(gòu)呢？我們在下一章中，會跟大家繼續(xù)這個話題。
對這方面感興趣的朋友，歡迎添加我的微信。彼此交流學(xué)習(xí)的經(jīng)驗和心得，我還有一些很可（dou）愛（bi）的微信表情想跟你分享哦。
推薦閱讀
?心中有“樹”！圖文并茂介紹數(shù)據(jù)結(jié)構(gòu)中常見的樹（一）?記住這兩個二分模板，秒殺所有二分查找算法題！?人生重開模擬器突然火爆 GitHub，趕緊來玩一玩
長按識別下圖二維碼，關(guān)注公眾號「Doocs 開源社區(qū)」，第一時間跟你們分享好玩、實用的技術(shù)文章與業(yè)內(nèi)最新資訊。