哈夫曼樹(Huffman Tree) ???

?哈夫曼樹，又被稱為最優(yōu)二叉樹，屬于帶權(quán)值二叉樹的一種。它的真實(shí)節(jié)點(diǎn)全部分布在葉子節(jié)點(diǎn)中，是各種可能的組合中 WPL 值最小的形式。組合形式可能不唯一，但 WPL 值一定為最小。

介紹一下 WPL（Weighted Path Length），也就是 帶權(quán)路徑長度，說簡單一些就是【節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長度 * 該節(jié)點(diǎn)的權(quán)值】。說白了就是權(quán)值越大的節(jié)點(diǎn)，離根節(jié)點(diǎn)越近就對(duì)了。 WPL_A = 9x2+4x2+5x2+2x2 = 40
WPL_B = 9x1+5x2+4x3+2x3 = 37
WPL_C = 4x1+2x2+5x3+9x3 = 50 ????看一下上面這張圖和三個(gè)對(duì)應(yīng)的 WPL 的值，很明顯可以看出來(b)是[9，4，5，2]這幾個(gè)節(jié)點(diǎn)對(duì)應(yīng)的哈夫曼樹（的一種表現(xiàn)形式）。我們剛才也提了，哈夫曼樹組成的形式可能不唯一，就比如說把(b)鏡像過來看，也是哈夫曼樹。 ????哈夫曼樹的應(yīng)用中，最有名的就是哈夫曼編碼了。通過這種編碼方式，可以使得整體編碼的長度最短。還需要說明的是，它是一種前綴編碼，任何一個(gè)編碼值，都不會(huì)為其他編碼值的前綴（最左子串）。 ????在 NLP(自然語言處理)領(lǐng)域劃時(shí)代之作—— word2vec 的過程中，也通過哈夫曼樹結(jié)構(gòu)來加速查詢高頻詞語，有興趣的朋友可以了解一下。

最小生成樹(Minimum Spanning Tree)

最小生成樹，雖然叫做“樹”，但是它更多地出現(xiàn)在“圖”相關(guān)的知識(shí)中，描述的是將一個(gè)有權(quán)圖，轉(zhuǎn)化成 所有節(jié)點(diǎn)均可連通，并且連接兩邊的權(quán)值之和最小的樹形結(jié)構(gòu)。提到這個(gè)，就肯定要說一下大名鼎鼎的 Prim 算法 和 Kruskal 算法，這兩種算法分別是從 隨機(jī)頂點(diǎn)的角度 和 權(quán)值最小的邊的角度 出發(fā)，一步一步地選出適合的邊，然后最終形成一顆包含全部 n 個(gè)節(jié)點(diǎn)和 n-1 條邊的最小生成樹。

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

線段樹(Segment Tree)

線段樹，是一種特殊的平衡二叉查找樹，每個(gè)葉子節(jié)點(diǎn)表示一個(gè)真實(shí)的節(jié)點(diǎn)信息。而路徑上所有的非葉子節(jié)點(diǎn)，用來表示它包含的各層級(jí)子節(jié)點(diǎn)的范圍，并用于標(biāo)記這個(gè)范圍內(nèi)的一些信息，比如范圍內(nèi)的 max 值或 sum 值等。 ????線段樹可以較好地兼顧區(qū)間插入新數(shù)據(jù)和單點(diǎn)數(shù)據(jù)修改的邏輯。當(dāng)更新葉子節(jié)點(diǎn)內(nèi)容的時(shí)候，只要更新該節(jié)點(diǎn)對(duì)應(yīng)路徑上的節(jié)點(diǎn)信息即可。主要用于一些對(duì)范圍查詢有很高要求的場景。

值得一提的是，線段樹可以通過一個(gè)一維數(shù)組來表示，如上圖中綠色數(shù)字所示（其中 10、11 為空缺信息）。還需要說明的一點(diǎn)是，類似的概念還有區(qū)間樹，也有人將這兩個(gè)概念畫了等號(hào)，大家自行了解分辨。

伸展樹(Splay Tree)

伸展樹是一顆非平衡二叉搜索樹。它的設(shè)計(jì)思路是基于一種假設(shè)：最頻繁被查詢的信息，它（和它附近的節(jié)點(diǎn)）在下次查詢的時(shí)候更可能被查到。所以，通過 Splay Tree 查詢的時(shí)候，會(huì)隨著被查詢的信息，反復(fù)調(diào)整樹本身的結(jié)構(gòu)，從而將經(jīng)常被查詢到的節(jié)點(diǎn)，放到 root 附近。這樣就可能會(huì)加速查詢的效率。 ????這個(gè)乍一聽，有點(diǎn)像 LRU 或者 LFU 類似的結(jié)構(gòu)，但又有所不同。首先，Splay Tree 中會(huì)保留所有的節(jié)點(diǎn)信息，不存在過期（或超限）銷毀的情況。還有一點(diǎn)就是它并不是被查到之后立即置頂，會(huì)有一些其他的綜合考量（比如，每次最多進(jìn)行兩次 n 次旋轉(zhuǎn)）。

看一下上面這張圖吧，它模擬的是（頻繁）查詢 R 的時(shí)候，Splay Tree 的變化情況。說白了就是把 R 節(jié)點(diǎn)放到根節(jié)點(diǎn)的位置，下次查起來就方便多了。Splay Tree 比較適合做緩存，特別是在熱點(diǎn)數(shù)據(jù)相對(duì)集中的情況下，查詢效率很高。舉個(gè)應(yīng)用的例子吧：我們常用的輸入法，當(dāng)你輸入完拼音之后，會(huì)根據(jù)你的之前的選擇情況，優(yōu)先出現(xiàn)某些詞語。但很多情況下，又不會(huì)直接把你上次選擇的詞語直接置頂，這就可以理解為是參考了伸展樹的思路（當(dāng)今輸入法的排序，實(shí)際更多的應(yīng)該是用 AI 算法是做概率預(yù)測，而非單純的 Splay Tree）。

數(shù)據(jù)庫領(lǐng)域

數(shù)據(jù)庫中非常核心的一個(gè)部分，就是索引結(jié)構(gòu)的設(shè)計(jì)——這幾乎決定了數(shù)據(jù)庫的應(yīng)用領(lǐng)域。而索引結(jié)構(gòu)的設(shè)計(jì)，又是數(shù)據(jù)結(jié)構(gòu)和算法的“重災(zāi)區(qū)”。下面我們就來列舉幾種數(shù)據(jù)庫領(lǐng)域中，常見的樹結(jié)構(gòu)。

B 樹

傳統(tǒng)的二叉樹中，每個(gè)節(jié)點(diǎn)中包含一個(gè)信息，這樣如果節(jié)點(diǎn)數(shù)比較多，路徑就會(huì)很深。路徑深了，對(duì)應(yīng)的問題就是查詢的過程中，需要經(jīng)過更多的節(jié)點(diǎn)，從而造成性能下降?；诖?，B 樹誕生了。 ????B 樹也屬于一種自然平衡樹。內(nèi)部通過分裂機(jī)制，能夠保持?jǐn)?shù)據(jù)的有序。它的單個(gè)節(jié)點(diǎn)中可以保存 2~4 個(gè)信息。單個(gè)節(jié)點(diǎn)內(nèi)部有序，節(jié)點(diǎn)之間信息的間隔，可以作為劃分下面部分的依據(jù)。

看上面這張圖，樹中一共有 10 個(gè)人信息，按照紅黑樹的形式存儲(chǔ)，最長的路徑應(yīng)該是 4。而通過 B 樹進(jìn)行存儲(chǔ)，就會(huì)顯得“矮胖”了，對(duì)應(yīng)的跨節(jié)點(diǎn)查詢次數(shù)也就縮短了。 ????B 樹比較適合于單點(diǎn)查詢的場景，比較常見的應(yīng)用就是 MongoDB 了。當(dāng)然了，B 樹也有一些不適合的場景，比如所有節(jié)點(diǎn)都放在磁盤上，則讀寫性能相對(duì)差；再比如說，如果我想查 5~9 范圍內(nèi)的所有數(shù)據(jù)，用 B 樹是不是就需要在 3 個(gè)節(jié)點(diǎn)中反復(fù)橫跳？

B+樹

B+樹就是為了解決上面拋出的兩個(gè)問題而設(shè)計(jì)的。與 B 樹相同的是，B+樹的節(jié)點(diǎn)中也包含了多個(gè)信息。但相比于 B 樹，B+樹做了一些改動(dòng)：非葉子節(jié)點(diǎn)中僅保留數(shù)據(jù)之間的相對(duì)關(guān)系，而所有的真實(shí)信息均包含在葉子節(jié)點(diǎn)中。這樣的話，相對(duì)關(guān)系信息就可以放到內(nèi)存中，而將所有節(jié)點(diǎn)信息（可以認(rèn)為量較大）保留在磁盤中。

每次查詢，通過相對(duì)關(guān)系，在內(nèi)存中就可以快速的定位到具體的節(jié)點(diǎn)信息，從而減少磁盤的 IO 次數(shù)。這樣做還有一個(gè)好處，可以通過一條“線”將所有葉子節(jié)點(diǎn)串聯(lián)起來，從而方便做范圍查詢。大名鼎鼎的 Mysql 的存儲(chǔ)引擎 InnoDB，使用的就是這種思路。 ????不知道有沒有朋友跟我一樣，在很長的一段時(shí)間內(nèi)，把數(shù)據(jù)庫索引和 B+樹畫上了等號(hào)。其實(shí)不然，不同應(yīng)用領(lǐng)域的數(shù)據(jù)庫，有著不同的索引結(jié)構(gòu)。B+樹的信息存放在磁盤中，且屬于非順序?qū)懭?，所以查詢性能很高，但寫入的性能偏低。在大?shù)據(jù)存儲(chǔ)和日志服務(wù)等需要頻繁寫入操作的領(lǐng)域，就有些不合適了——這就要引出我們接下來的話題了。 日志結(jié)構(gòu)化合并樹（Log Structured Merge Tree） ????多年前，谷歌在發(fā)大據(jù)領(lǐng)域發(fā)表了Big Table相關(guān)論文，LSM 樹是其中的實(shí)現(xiàn)思路。我第一次聽說 LSM Tree，是有幸跟一位 HBase 領(lǐng)域的資深大佬一起喝茶的時(shí)候。當(dāng)時(shí)我紅著臉表示，只聽說過其中的一部分。

與其說它是一種數(shù)據(jù)結(jié)構(gòu)，其實(shí)它更像是基于此思想而衍生出的一系列算法操作的集合。它描述了將實(shí)時(shí)產(chǎn)生的大批量信息在內(nèi)存中排序、更新，然后按批次順序?qū)懭氪疟P固化、合并的流程，從而兼顧了大批量數(shù)據(jù)的高效寫入存儲(chǔ)和范圍查詢等使用場景。 ????我們剛才提到，B+樹結(jié)構(gòu)的存儲(chǔ)索引并不適合在頻繁寫入的場景，其中一個(gè)很重要的原因就是因?yàn)樗鼘儆诜琼樞驅(qū)懭?。而針?duì)傳統(tǒng)磁盤來說，由于扇區(qū)物理結(jié)構(gòu)輪轉(zhuǎn)，順序?qū)懭氲男阅苓h(yuǎn)好于非順序?qū)懭搿?/p>

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

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

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

?需要在批量數(shù)據(jù)中做范圍查找了咋辦？ ????在內(nèi)存中記錄每個(gè) Segment（默認(rèn)有序）的起止范圍，每次查詢的時(shí)候僅查詢范圍內(nèi)的 Segment 不就好了。

?數(shù)據(jù)量太大，磁盤中的 Segment 太多，影響查詢性能了咋辦？ ????

當(dāng)每個(gè) Segment 大到一定的程度的時(shí)候，把幾個(gè) Segment 做歸并排序，然后合并到一個(gè)大的 Segment 里不就好了么。

?寫入數(shù)據(jù)之后，想刪除咋辦？ ???

?根據(jù) key 找到最后一次寫入的信息，打上墓碑記號(hào)。查詢到的時(shí)候，返回“這個(gè)真沒有”不就好了么。

?墓碑記號(hào)太多，占用大量內(nèi)存，咋辦？

?單點(diǎn)信息查詢，數(shù)據(jù)太多，而且經(jīng)常 miss，咋辦？?范圍查詢，不好確認(rèn)從哪個(gè) Segment 開始，咋辦？?...

隨著大數(shù)據(jù)的爆火，LSM Tree 被廣泛用于 KV 型數(shù)據(jù)庫和 OLAP 場景中，比如純序員熟悉（拼寫方式）的 HBase、Cassandra、LevelDB 等。相關(guān)領(lǐng)域的實(shí)際問題太多了，同樣的，解法也很多。有興趣的朋友可以深入了解一下。

編輯：黃飛

?