嵌入式技術數(shù)據(jù)結構中常見的樹有哪些？

哈夫曼樹(Huffman Tree) ???

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

介紹一下 WPL（Weighted Path Length），也就是帶權路徑長度，說簡單一些就是【節(jié)點到根節(jié)點的路徑長度 * 該節(jié)點的權值】。說白了就是權值越大的節(jié)點，離根節(jié)點越近就對了。 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]這幾個節(jié)點對應的哈夫曼樹（的一種表現(xiàn)形式）。我們剛才也提了，哈夫曼樹組成的形式可能不唯一，就比如說把(b)鏡像過來看，也是哈夫曼樹。 ????哈夫曼樹的應用中，最有名的就是哈夫曼編碼了。通過這種編碼方式，可以使得整體編碼的長度最短。還需要說明的是，它是一種前綴編碼，任何一個編碼值，都不會為其他編碼值的前綴（最左子串）。 ????在 NLP(自然語言處理)領域劃時代之作—— word2vec 的過程中，也通過哈夫曼樹結構來加速查詢高頻詞語，有興趣的朋友可以了解一下。

最小生成樹(Minimum Spanning Tree)

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

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

線段樹(Segment Tree)

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

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

伸展樹(Splay Tree)

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

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

數(shù)據(jù)庫領域

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

B 樹

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

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

B+樹

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

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

與其說它是一種數(shù)據(jù)結構，其實它更像是基于此思想而衍生出的一系列算法操作的集合。它描述了將實時產(chǎn)生的大批量信息在內(nèi)存中排序、更新，然后按批次順序寫入磁盤固化、合并的流程，從而兼顧了大批量數(shù)據(jù)的高效寫入存儲和范圍查詢等使用場景。 ????我們剛才提到，B+樹結構的存儲索引并不適合在頻繁寫入的場景，其中一個很重要的原因就是因為它屬于非順序寫入。而針對傳統(tǒng)磁盤來說，由于扇區(qū)物理結構輪轉，順序寫入的性能遠好于非順序寫入。