多叉樹，紅黑樹，堆，Trie樹，B樹，B+樹...

1. 每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點；

2. 沒有父節(jié)點的節(jié)點稱為根節(jié)點；

3. 每一個非根節(jié)點有且只有一個父節(jié)點；

4. 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹；

5. 樹里面沒有環(huán)路(cycle)

維基百科中列舉了計算機(jī)科學(xué)中樹形結(jié)構(gòu)的種類

限于篇幅，本文主要介紹非LSM Tree的內(nèi)容。

多叉樹

樹體現(xiàn)了一種 繼承 的關(guān)系，節(jié)點之間為父子關(guān)系。多叉樹 是指一個父節(jié)點可以有多個子節(jié)點。也就是：爸爸可以有多個兒子，兒子只能有一個爸爸。

此外，節(jié)點的每個分支也代表著一種選擇，可以用來做決策。

應(yīng)用場景：
1.Linux文件系統(tǒng)
2.組織關(guān)系表示，如公司的組織架構(gòu)，角色權(quán)限系統(tǒng)等。
3.XML/HTML數(shù)據(jù)。
4.類的繼承關(guān)系
5.決策，如游戲中怪物使用的技能選擇，機(jī)器學(xué)習(xí)…

二叉樹

二叉樹（Binary tree）是每個節(jié)點最多只有兩個分支（即不存在分支度大于2的節(jié)點）的樹結(jié)構(gòu)，也就是說 爸爸 最多只能有 兩個兒子。

因為計算機(jī)應(yīng)用中存在很多“非黑即白”的場景，同樣我們可以利用 不是走左分支，就是走右分支 這種結(jié)構(gòu)選擇來做一些決策。

在我們的日常開發(fā)中，經(jīng)常需要對數(shù)據(jù)進(jìn)行增刪改查，每一個步驟的時間空間效率決定了應(yīng)用最終的性能。

時間效率 體現(xiàn)在 能否快速定位到要操作的數(shù)據(jù)元素，核心在于 索引的好壞；

空間效率?體現(xiàn)在 能否占用 更小的內(nèi)存空間，能否利用計算機(jī)各層介質(zhì)的緩存性能提高訪問速度（訪問速度：CPU>> 內(nèi)存>>磁盤）。

在以下樹形結(jié)構(gòu)的討論中，希望小伙伴能多從 索引，所占用內(nèi)存空間，操作的介質(zhì) 這些方面考慮數(shù)據(jù)的增刪改查性能。

二叉查找樹

二叉查找樹（Binary Search Tree）首先是二叉樹，同時滿足一定的有序性：節(jié)點的左子節(jié)點比自己小，節(jié)點的右子節(jié)點比自己大。

應(yīng)用場景：
二叉查找樹的有序性是它能夠廣泛應(yīng)用的原因。但是能否高效二分體現(xiàn)在樹的高度合理性上。下面要講的 紅黑樹/堆結(jié)構(gòu)才是其廣泛應(yīng)用。

紅黑樹

二叉查找樹的缺點在于：只限制了節(jié)點的有序性，但有序樹的構(gòu)造有好壞。一顆“壞”的有序樹直接會被拉成 “有序鏈表”。所以需要通過一定的條件保證樹的平衡性。

樹的平衡性是指整棵樹的最高子樹和最矮子樹相差不大，這樣整棵樹的高度相對來說低一些，相應(yīng)的增，刪，改，查操作的效率較高較穩(wěn)定（與樹高有關(guān)）。

紅黑樹（Red–black tree）是應(yīng)用很廣泛的一種平衡樹，是面試官的裝X利器。我們來看一下它保證平衡性的一些特性：

1. 節(jié)點是紅色或黑色。

2. 根是黑色。

3. 所有葉子都是黑色（葉子是NIL節(jié)點）。

4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。）

5. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長路徑不多于最短路徑的兩倍長(根據(jù)性質(zhì)4和性質(zhì)5)。從而整棵樹的高度比較穩(wěn)定，相應(yīng)的增、刪、改、查操作的效率較高較穩(wěn)定，而不同于普通的二叉查找樹。

此外相比其他的平衡樹：如高度平衡樹AVL樹，紅黑樹的增刪改效率較高，同時查找性能沒有下降很多也比較穩(wěn)定。所以工業(yè)級應(yīng)用更為廣泛。

應(yīng)用場景：適合排序，查找的場景。
1.容器的基本組成，如Java中的HashMap/TreeMap.
2.Linux內(nèi)核的完全公平調(diào)度器
3.Linux中epoll機(jī)制的實現(xiàn)…

堆

堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它滿足兩個特性：

1. 堆是一個完全二叉樹；

2. 堆中每一個節(jié)點的排序值都必須大于等于（或小于等于）其左右子節(jié)點的排序值。

這里解釋一下完全二叉樹。它是指：除了最后一層，其他層的節(jié)點個數(shù)都是滿的，最后一層的節(jié)點都靠左排列。

這樣我們就可以用數(shù)組來存儲。

假設(shè)根節(jié)點在i=0的位置：如果父節(jié)點的數(shù)組下標(biāo)為i，則左子節(jié)點的數(shù)組下標(biāo)為2 * i+1，右子節(jié)點的數(shù)組下標(biāo)為 2 * i + 2。數(shù)組比鏈表的存儲好處上篇文章233醬提過了，這里就不贅述了。

針對第2點，如果每個節(jié)點的值都大于等于子樹中每個節(jié)點值的堆，叫做“大頂堆”。反之叫做“小頂堆”。

堆這種結(jié)構(gòu)相對有序，且堆頂元素要么最小，要么最大。且利用了 數(shù)組和自身特性 增刪改查的時間復(fù)雜度較低。

應(yīng)用場景：
1.堆排序
2.TopK,求中位數(shù)，求
3.合并多個有序小文件或集合
4.優(yōu)先隊列，如定時任務(wù)的存儲等…

Trie樹

Trie樹 又稱前綴樹或字典樹，它是一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來解決在一組字符串集合中快速查找某個字符串的問題。

它的特性為：

1. 根節(jié)點不包含字符，除根節(jié)點外的每一個子節(jié)點都包含一個字符。

2. 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，就是該節(jié)點對應(yīng)的字符串。

3. 每個字符串的公共前綴作為一個字符節(jié)點保存。

如果我們有and,as,at,cn,com這些關(guān)鍵詞，那么構(gòu)建的trie樹如下：

Trie 樹的本質(zhì)，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起。這樣當(dāng)我們查找某個字符串時，只需要在Trie樹上匹配字符串的每個字符，比較次數(shù)僅和 字符串的長度 有關(guān)。

但是Trie 樹的缺點就是構(gòu)造Trie樹需要很大的內(nèi)存空間。因為父子字符節(jié)點之間用 指針關(guān)聯(lián)。如果用數(shù)組保存這些指針，這意味著子節(jié)點的數(shù)組需要窮舉出每一種可能。如子節(jié)點字符為a-z，就需要分配長度為26的數(shù)組來存儲這些可能的子節(jié)點。

改進(jìn)內(nèi)存分配的措施有：

1.子節(jié)點指針改為用：有序數(shù)組、跳表、散列表、紅黑樹來存儲。
2.子節(jié)點合并，如原來 hello存儲為：h->e->l->l->o ,現(xiàn)在可存儲為：h->e->llo

Trie 樹畢竟比較浪費空間，所以它在字符串的查找中，適合用于：1.字符集不能太大 2.字符串的公共前綴較多 的場景。

應(yīng)用場景：
1.關(guān)鍵詞匹配，提示，糾錯。
2.最長公共前綴匹配。
3.命令自動補(bǔ)全，如zsh.
4.網(wǎng)址瀏覽歷史記錄。
5.手機(jī)號碼簿查詢…

B樹、B+樹 是數(shù)據(jù)庫中經(jīng)常出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。對于數(shù)據(jù)庫的增刪改查效率，需要考慮的首要因素是：磁盤的IO訪問次數(shù)。

如何減少IO訪問次數(shù)？

前文我們已經(jīng)提到了索引，但是IO一次不容易，從磁盤中獲取數(shù)據(jù)通常是以塊為單位的。如果對于上千萬條數(shù)據(jù)，我們只建立一層索引結(jié)構(gòu)的話，那索引的數(shù)據(jù)量也是巨大的。

如何降低索引量？

假設(shè)我們到全世界找一個人，我們是按照 國家/省/市/區(qū)/街道/小區(qū)的順序來定位。同理，隨著數(shù)據(jù)量的增大，我們需要一層層的建立 多級索引 。越上層的索引每個塊中表示的數(shù)據(jù)范圍越大。

如何保證我們建立的多級索引 是“合適”的？

這個合適主要指：存儲的數(shù)據(jù)量大并且樹高小。同紅黑樹一樣，我們需要一些 限制條件 來保證樹高。這也就是以下數(shù)據(jù)結(jié)構(gòu)的限制條件原因了。

B樹

一個m階（該樹每個節(jié)點最多有 M 個子節(jié)點）的B樹具有以下特征：

1.根節(jié)點至少有兩個子女。
2.每個中間節(jié)點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m
3.每一個葉子節(jié)點都包含k-1個元素，其中 m/2 <= k <= m
4.所有的葉子節(jié)點都位于同一層。
5.每個節(jié)點中的元素從小到大排列，節(jié)點當(dāng)中k-1個元素正好是k個子節(jié)點包含的元素的值域分劃。

一個3階的B樹插入示意圖如下：

應(yīng)用場景：MongoDB

B+樹

一個m階的B+樹具有以下特征：

1.有k個子樹的中間節(jié)點包含有k個元素（B樹中是k-1個元素），每個元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點。
2.所有的葉子節(jié)點中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子節(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。
3.所有的中間節(jié)點元素都同時存在于子節(jié)點，在子節(jié)點元素中是最大（或最?。┰亍?/span>

看不懂沒關(guān)系，我們只需要知道這些限制條件是為了讓B+樹數(shù)據(jù)“矮而胖”就好。

這里我直接放張掘金小冊《從根兒上理解MYSQL》B+樹主鍵索引的示意圖：

應(yīng)用場景
1.Mysql InnoDB存儲引擎。

看到這里?？济嬖囶}來了：B樹和B+樹有什么區(qū)別？為什么Mongo用B樹？為什么Mysql用B+樹？

B樹 vs B+樹

看圖說話，B樹 和 B+樹顯著不同的地方是：
1.B樹非葉子節(jié)點即是索引，也是數(shù)據(jù)；B+樹非葉子節(jié)點僅是索引，數(shù)據(jù)全部存儲在葉子節(jié)點。
2.B+樹葉子節(jié)點的數(shù)據(jù)之間是用鏈表鏈接的。
這會導(dǎo)致：

B+樹相比B樹：

1.數(shù)據(jù)的連續(xù)性：B+樹葉子節(jié)點上一頁存儲的數(shù)據(jù)是連續(xù)的，當(dāng)需要一個節(jié)點上的數(shù)據(jù)時，B+樹可以增大緩存的命中率。

2.葉子節(jié)點之間的連接性：當(dāng)作范圍或全文掃描時，B+樹可以依賴葉子節(jié)點做線性順序掃描，而B樹只能在每一層的節(jié)點上做掃描。B+樹同樣可以增大緩存的命中率。

B樹相比B+樹：
當(dāng)作單一數(shù)據(jù)查詢時，B樹的節(jié)點平均離根節(jié)點更近，平均查詢效率比B+樹快。

總結(jié)一下：B+樹相比B樹，前者更適合范圍查詢，后者更適合單一數(shù)據(jù)查詢。

Mongo是非關(guān)系型數(shù)據(jù)庫，數(shù)據(jù)之間的關(guān)系用嵌套解決。它的主要使用場景是：追求 單個讀寫記錄的性能。

Mysql是關(guān)系型數(shù)據(jù)庫，數(shù)據(jù)之間的關(guān)系用共同的索引鍵，Join解決。它的使用場景：不僅存在大量的單一數(shù)據(jù)查詢，也存在大量的范圍查詢。

所以上面的問題可以簡單扯一扯了吧。

參考資料：
[1].維基百科
[2].https://www.youtube.com/watch?v=OJ5NYq1Eii8
[3].https://time.geekbang.org/column/article/72414
[4].https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c
[5].https://draveness.me/whys-the-design-mongodb-b-tree/