多叉樹，紅黑樹，堆，Trie樹，B樹，B+樹...
樹形結(jié)構(gòu)，是指：數(shù)據(jù)元素之間的關(guān)系像一顆樹的數(shù)據(jù)結(jié)構(gòu)。我們看圖說話：
它具有以下特點(diǎn)：
每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無子節(jié)點(diǎn)；
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；
樹里面沒有環(huán)路(cycle)
維基百科中列舉了計(jì)算機(jī)科學(xué)中樹形結(jié)構(gòu)的種類
233醬當(dāng)然不會(huì)一個(gè)個(gè)講，我們只挑一些熟悉的面孔：多叉樹，二叉樹，二叉查找樹，紅黑樹，堆，Trie樹，B樹，B+樹，LSM Tree，了解他們在對(duì)不同規(guī)模的數(shù)據(jù) 增，刪，改，查 時(shí)所起到的作用就夠了。
限于篇幅，本文主要介紹非LSM Tree的內(nèi)容。
多叉樹
樹體現(xiàn)了一種 繼承 的關(guān)系，節(jié)點(diǎn)之間為父子關(guān)系。多叉樹 是指一個(gè)父節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。也就是：爸爸可以有多個(gè)兒子，兒子只能有一個(gè)爸爸。
當(dāng)需要這種分層，繼承的場景下均可以考慮用樹結(jié)構(gòu)來實(shí)現(xiàn)，可以簡化我們對(duì)數(shù)據(jù)關(guān)系的描述。
此外，節(jié)點(diǎn)的每個(gè)分支也代表著一種選擇，可以用來做決策。
應(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）是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支（即不存在分支度大于2的節(jié)點(diǎn)）的樹結(jié)構(gòu)，也就是說 爸爸 最多只能有 兩個(gè)兒子。
因?yàn)橛?jì)算機(jī)應(yīng)用中存在很多“非黑即白”的場景，同樣我們可以利用 不是走左分支，就是走右分支 這種結(jié)構(gòu)選擇來做一些決策。
另外，利用每個(gè)節(jié)點(diǎn)下參與方最多為兩個(gè)，也可以做一些事情。
應(yīng)用場景：
1.編譯器的語法樹構(gòu)造。
2.表達(dá)式求值和判斷：非葉子節(jié)點(diǎn)為操作符，葉子節(jié)點(diǎn)為數(shù)值。
3.Boolean求值，如（a and b）or (c or d)。
4.霍夫曼編碼
5.IPv4路由表的存儲(chǔ)…
在我們的日常開發(fā)中，經(jīng)常需要對(duì)數(shù)據(jù)進(jìn)行增刪改查，每一個(gè)步驟的時(shí)間空間效率決定了應(yīng)用最終的性能。
時(shí)間效率 體現(xiàn)在 能否快速定位到要操作的數(shù)據(jù)元素，核心在于 索引的好壞；
空間效率?體現(xiàn)在 能否占用 更小的內(nèi)存空間，能否利用計(jì)算機(jī)各層介質(zhì)的緩存性能提高訪問速度（訪問速度：CPU>> 內(nèi)存>>磁盤）。
在以下樹形結(jié)構(gòu)的討論中，希望小伙伴能多從 索引，所占用內(nèi)存空間，操作的介質(zhì) 這些方面考慮數(shù)據(jù)的增刪改查性能。
二叉查找樹
二叉查找樹（Binary Search Tree）首先是二叉樹，同時(shí)滿足一定的有序性：節(jié)點(diǎn)的左子節(jié)點(diǎn)比自己小，節(jié)點(diǎn)的右子節(jié)點(diǎn)比自己大。
這樣當(dāng)我們定位一個(gè)元素的位置時(shí)，從根節(jié)點(diǎn)開始查找，小于節(jié)點(diǎn)左拐，大于節(jié)點(diǎn)右拐。等于節(jié)點(diǎn)排序值就剛好找到。二分的索引思想就體現(xiàn)在其中。
應(yīng)用場景：
二叉查找樹的有序性是它能夠廣泛應(yīng)用的原因。但是能否高效二分體現(xiàn)在樹的高度合理性上。下面要講的 紅黑樹/堆結(jié)構(gòu)才是其廣泛應(yīng)用。
紅黑樹
二叉查找樹的缺點(diǎn)在于：只限制了節(jié)點(diǎn)的有序性，但有序樹的構(gòu)造有好壞。一顆“壞”的有序樹直接會(huì)被拉成 “有序鏈表”。所以需要通過一定的條件保證樹的平衡性。
樹的平衡性是指整棵樹的最高子樹和最矮子樹相差不大，這樣整棵樹的高度相對(duì)來說低一些，相應(yīng)的增，刪，改，查操作的效率較高較穩(wěn)定（與樹高有關(guān)）。
紅黑樹（Red–black tree）是應(yīng)用很廣泛的一種平衡樹，是面試官的裝X利器。我們來看一下它保證平衡性的一些特性：
節(jié)點(diǎn)是紅色或黑色。
根是黑色。
所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。
每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）
從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長路徑不多于最短路徑的兩倍長(根據(jù)性質(zhì)4和性質(zhì)5)。從而整棵樹的高度比較穩(wěn)定，相應(yīng)的增、刪、改、查操作的效率較高較穩(wěn)定，而不同于普通的二叉查找樹。
此外相比其他的平衡樹：如高度平衡樹AVL樹，紅黑樹的增刪改效率較高，同時(shí)查找性能沒有下降很多也比較穩(wěn)定。所以工業(yè)級(jí)應(yīng)用更為廣泛。
應(yīng)用場景：適合排序，查找的場景。
1.容器的基本組成，如Java中的HashMap/TreeMap.
2.Linux內(nèi)核的完全公平調(diào)度器
3.Linux中epoll機(jī)制的實(shí)現(xiàn)…
堆
堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它滿足兩個(gè)特性：
堆是一個(gè)完全二叉樹；
堆中每一個(gè)節(jié)點(diǎn)的排序值都必須大于等于（或小于等于）其左右子節(jié)點(diǎn)的排序值。
這里解釋一下完全二叉樹。它是指：除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，最后一層的節(jié)點(diǎn)都靠左排列。
這樣我們就可以用數(shù)組來存儲(chǔ)。
假設(shè)根節(jié)點(diǎn)在i=0的位置：如果父節(jié)點(diǎn)的數(shù)組下標(biāo)為i，則左子節(jié)點(diǎn)的數(shù)組下標(biāo)為2 * i+1，右子節(jié)點(diǎn)的數(shù)組下標(biāo)為 2 * i + 2。數(shù)組比鏈表的存儲(chǔ)好處上篇文章233醬提過了，這里就不贅述了。
針對(duì)第2點(diǎn)，如果每個(gè)節(jié)點(diǎn)的值都大于等于子樹中每個(gè)節(jié)點(diǎn)值的堆，叫做“大頂堆”。反之叫做“小頂堆”。
堆這種結(jié)構(gòu)相對(duì)有序，且堆頂元素要么最小，要么最大。且利用了 數(shù)組和自身特性 增刪改查的時(shí)間復(fù)雜度較低。
應(yīng)用場景：
1.堆排序
2.TopK,求中位數(shù)，求
3.合并多個(gè)有序小文件或集合
4.優(yōu)先隊(duì)列，如定時(shí)任務(wù)的存儲(chǔ)等…
Trie樹
Trie樹 又稱前綴樹或字典樹，它是一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來解決在一組字符串集合中快速查找某個(gè)字符串的問題。
它的特性為：
根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符。
從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，就是該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
每個(gè)字符串的公共前綴作為一個(gè)字符節(jié)點(diǎn)保存。
如果我們有and,as,at,cn,com這些關(guān)鍵詞，那么構(gòu)建的trie樹如下：
Trie 樹的本質(zhì)，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起。這樣當(dāng)我們查找某個(gè)字符串時(shí)，只需要在Trie樹上匹配字符串的每個(gè)字符，比較次數(shù)僅和 字符串的長度 有關(guān)。
但是Trie 樹的缺點(diǎn)就是構(gòu)造Trie樹需要很大的內(nèi)存空間。因?yàn)楦缸幼址?jié)點(diǎn)之間用 指針關(guān)聯(lián)。如果用數(shù)組保存這些指針，這意味著子節(jié)點(diǎn)的數(shù)組需要窮舉出每一種可能。如子節(jié)點(diǎn)字符為a-z，就需要分配長度為26的數(shù)組來存儲(chǔ)這些可能的子節(jié)點(diǎn)。
改進(jìn)內(nèi)存分配的措施有：
1.子節(jié)點(diǎn)指針改為用：有序數(shù)組、跳表、散列表、紅黑樹來存儲(chǔ)。
2.子節(jié)點(diǎn)合并，如原來 hello存儲(chǔ)為：h->e->l->l->o ,現(xiàn)在可存儲(chǔ)為：h->e->llo
Trie 樹畢竟比較浪費(fèi)空間，所以它在字符串的查找中，適合用于：1.字符集不能太大 2.字符串的公共前綴較多 的場景。
應(yīng)用場景：
1.關(guān)鍵詞匹配，提示，糾錯(cuò)。
2.最長公共前綴匹配。
3.命令自動(dòng)補(bǔ)全，如zsh.
4.網(wǎng)址瀏覽歷史記錄。
5.手機(jī)號(hào)碼簿查詢…
B樹、B+樹 是數(shù)據(jù)庫中經(jīng)常出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。對(duì)于數(shù)據(jù)庫的增刪改查效率，需要考慮的首要因素是：磁盤的IO訪問次數(shù)。
如何減少IO訪問次數(shù)？
前文我們已經(jīng)提到了索引，但是IO一次不容易，從磁盤中獲取數(shù)據(jù)通常是以塊為單位的。如果對(duì)于上千萬條數(shù)據(jù)，我們只建立一層索引結(jié)構(gòu)的話，那索引的數(shù)據(jù)量也是巨大的。
如何降低索引量？
假設(shè)我們到全世界找一個(gè)人，我們是按照 國家/省/市/區(qū)/街道/小區(qū)的順序來定位。同理，隨著數(shù)據(jù)量的增大，我們需要一層層的建立 多級(jí)索引 。越上層的索引每個(gè)塊中表示的數(shù)據(jù)范圍越大。
如何保證我們建立的多級(jí)索引 是“合適”的？
這個(gè)合適主要指：存儲(chǔ)的數(shù)據(jù)量大并且樹高小。同紅黑樹一樣，我們需要一些 限制條件 來保證樹高。這也就是以下數(shù)據(jù)結(jié)構(gòu)的限制條件原因了。
B樹
一個(gè)m階（該樹每個(gè)節(jié)點(diǎn)最多有 M 個(gè)子節(jié)點(diǎn)）的B樹具有以下特征：
1.根節(jié)點(diǎn)至少有兩個(gè)子女。
2.每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子，其中 m/2 <= k <= m
3.每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素，其中 m/2 <= k <= m
4.所有的葉子節(jié)點(diǎn)都位于同一層。
5.每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)子節(jié)點(diǎn)包含的元素的值域分劃。
一個(gè)3階的B樹插入示意圖如下：
應(yīng)用場景：MongoDB
B+樹
一個(gè)m階的B+樹具有以下特征：
1.有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
2.所有的葉子節(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
3.所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最?。┰?。
看不懂沒關(guān)系，我們只需要知道這些限制條件是為了讓B+樹數(shù)據(jù)“矮而胖”就好。
這里我直接放張掘金小冊《從根兒上理解MYSQL》B+樹主鍵索引的示意圖：
應(yīng)用場景
1.Mysql InnoDB存儲(chǔ)引擎。
看到這里?？济嬖囶}來了：B樹和B+樹有什么區(qū)別？為什么Mongo用B樹？為什么Mysql用B+樹？
B樹 vs B+樹
看圖說話，B樹 和 B+樹顯著不同的地方是：
1.B樹非葉子節(jié)點(diǎn)即是索引，也是數(shù)據(jù)；B+樹非葉子節(jié)點(diǎn)僅是索引，數(shù)據(jù)全部存儲(chǔ)在葉子節(jié)點(diǎn)。
2.B+樹葉子節(jié)點(diǎn)的數(shù)據(jù)之間是用鏈表鏈接的。
這會(huì)導(dǎo)致：
B+樹相比B樹：
1.數(shù)據(jù)的連續(xù)性：B+樹葉子節(jié)點(diǎn)上一頁存儲(chǔ)的數(shù)據(jù)是連續(xù)的，當(dāng)需要一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)時(shí)，B+樹可以增大緩存的命中率。
2.葉子節(jié)點(diǎn)之間的連接性：當(dāng)作范圍或全文掃描時(shí)，B+樹可以依賴葉子節(jié)點(diǎn)做線性順序掃描，而B樹只能在每一層的節(jié)點(diǎn)上做掃描。B+樹同樣可以增大緩存的命中率。
B樹相比B+樹：
當(dāng)作單一數(shù)據(jù)查詢時(shí)，B樹的節(jié)點(diǎn)平均離根節(jié)點(diǎn)更近，平均查詢效率比B+樹快。
總結(jié)一下：B+樹相比B樹，前者更適合范圍查詢，后者更適合單一數(shù)據(jù)查詢。
Mongo是非關(guān)系型數(shù)據(jù)庫，數(shù)據(jù)之間的關(guān)系用嵌套解決。它的主要使用場景是：追求 單個(gè)讀寫記錄的性能。
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/