哈夫曼樹(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 = 40
WPL_B = 9x1+5x2+4x3+2x3 = 37
WPL_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 算法，這兩種算法分別是從 隨機(jī)頂點的角度 和 權(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 樹誕生了。 ????B 樹也屬于一種自然平衡樹。內(nèi)部通過分裂機(jī)制，能夠保持?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ū)懭搿６槍鹘y(tǒng)磁盤來說，由于扇區(qū)物理結(jié)構(gòu)輪轉(zhuǎn)，順序?qū)懭氲男阅苓h(yuǎn)好于非順序?qū)懭搿?/p>

?隨機(jī)寫入磁盤慢了咋辦？ ??

??將非順序的信息在內(nèi)存中攢成有序的一批信息（Segment），然后一次性寫入磁盤不就好了么。 ?攢批的時候，數(shù)據(jù)丟失或者進(jìn)程崩潰了咋辦？ ??

??提前把數(shù)據(jù)寫到一個本地日志文件（WAL 機(jī)制）里做備胎（不對，是備份）不就好了。

?需要在批量數(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)域的實際問題太多了，同樣的，解法也很多。有興趣的朋友可以深入了解一下。

編輯：黃飛

?