哈夫曼樹(shù)(Huffman Tree) ???

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

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

最小生成樹(shù)(Minimum Spanning Tree)

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

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

線段樹(shù)(Segment Tree)

線段樹(shù)，是一種特殊的平衡二叉查找樹(shù)，每個(gè)葉子節(jié)點(diǎn)表示一個(gè)真實(shí)的節(jié)點(diǎn)信息。而路徑上所有的非葉子節(jié)點(diǎn)，用來(lái)表示它包含的各層級(jí)子節(jié)點(diǎn)的范圍，并用于標(biāo)記這個(gè)范圍內(nèi)的一些信息，比如范圍內(nèi)的 max 值或 sum 值等。 ????線段樹(shù)可以較好地兼顧區(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ì)范圍查詢(xún)有很高要求的場(chǎng)景。

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

伸展樹(shù)(Splay Tree)

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

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

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

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

B 樹(shù)

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

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

B+樹(shù)

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

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

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

?隨機(jī)寫(xiě)入磁盤(pán)慢了咋辦？ ??

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

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

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

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

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

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

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

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

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

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

編輯：黃飛

?