應用場景：
二叉查找樹的有序性是它能夠廣泛應用的原因。但是能否高效二分體現在樹的高度合理性上。下面要講的 紅黑樹/堆結構才是其廣泛應用。
二叉查找樹的缺點在於：只限制了節點的有序性，但有序樹的構造有好壞。一顆「壞」的有序樹直接會被拉成 「有序鍊表」。所以需要通過一定的條件保證樹的平衡性。
樹的平衡性是指整棵樹的最高子樹和最矮子樹相差不大，這樣整棵樹的高度相對來說低一些，相應的增，刪，改，查操作的效率較高較穩定（與樹高有關）。
紅黑樹（Red–black tree）是應用很廣泛的一種平衡樹，是面試官的裝X利器。我們來看一下它保證平衡性的一些特性：
節點是紅色或黑色。
根是黑色。
所有葉子都是黑色（葉子是NIL節點）。
每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長路徑不多於最短路徑的兩倍長(根據性質4和性質5)。從而整棵樹的高度比較穩定，相應的增、刪、改、查操作的效率較高較穩定，而不同於普通的二叉查找樹。
此外相比其他的平衡樹：如高度平衡樹AVL樹，紅黑樹的增刪改效率較高，同時查找性能沒有下降很多也比較穩定。所以工業級應用更為廣泛。
應用場景：適合排序，查找的場景。
1.容器的基本組成，如Java中的HashMap/TreeMap.
2.Linux內核的完全公平調度器
3.Linux中epoll機制的實現…
堆是一種特殊的數據結構，它滿足兩個特性：
堆是一個完全二叉樹；
堆中每一個節點的排序值都必須大於等於（或小於等於）其左右子節點的排序值。
這裡解釋一下完全二叉樹。它是指：除了最後一層，其他層的節點個數都是滿的，最後一層的節點都靠左排列。
這樣我們就可以用數組來存儲。
假設根節點在i=0的位置：如果父節點的數組下標為i，則左子節點的數組下標為2 * i+1，右子節點的數組下標為 2 * i + 2。數組比鍊表的存儲好處上篇文章233醬提過了，這裡就不贅述了。
針對第2點，如果每個節點的值都大於等於子樹中每個節點值的堆，叫做「大頂堆」。反之叫做「小頂堆」。
堆這種結構相對有序，且堆頂元素要麼最小，要麼最大。且利用了 數組和自身特性 增刪改查的時間複雜度較低。
應用場景：
1.堆排序
2.TopK,求中位數，求
3.合併多個有序小文件或集合
4.優先隊列，如定時任務的存儲等…
Trie樹 又稱前綴樹或字典樹，它是一種專門處理字符串匹配的數據結構，用來解決在一組字符串集合中快速查找某個字符串的問題。
它的特性為：
根節點不包含字符，除根節點外的每一個子節點都包含一個字符。
從根節點到某一節點，路徑上經過的字符連接起來，就是該節點對應的字符串。
每個字符串的公共前綴作為一個字符節點保存。
如果我們有and,as,at,cn,com這些關鍵詞，那麼構建的trie樹如下：
Trie 樹的本質，就是利用字符串之間的公共前綴，將重複的前綴合併在一起。這樣當我們查找某個字符串時，只需要在Trie樹上匹配字符串的每個字符，比較次數僅和 字符串的長度 有關。
但是Trie 樹的缺點就是構造Trie樹需要很大的內存空間。因為父子字符節點之間用 指針關聯。如果用數組保存這些指針，這意味著子節點的數組需要窮舉出每一種可能。如子節點字符為a-z，就需要分配長度為26的數組來存儲這些可能的子節點。
改進內存分配的措施有：
1.子節點指針改為用：有序數組、跳表、散列表、紅黑樹來存儲。
2.子節點合併，如原來 hello存儲為：h->e->l->l->o ,現在可存儲為：h->e->llo
Trie 樹畢竟比較浪費空間，所以它在字符串的查找中，適合用於：1.字符集不能太大 2.字符串的公共前綴較多 的場景。
應用場景：
1.關鍵詞匹配，提示，糾錯。
2.最長公共前綴匹配。
3.命令自動補全，如zsh.
4.網址瀏覽歷史記錄。
5.手機號碼簿查詢…
B樹、B+樹 是資料庫中經常出現的數據結構。對於資料庫的增刪改查效率，需要考慮的首要因素是：磁碟的IO訪問次數。
如何減少IO訪問次數？
前文我們已經提到了索引，但是IO一次不容易，從磁碟中獲取數據通常是以塊為單位的。如果對於上千萬條數據，我們只建立一層索引結構的話，那索引的數據量也是巨大的。
如何降低索引量？
假設我們到全世界找一個人，我們是按照 國家/省/市/區/街道/小區的順序來定位。同理，隨著數據量的增大，我們需要一層層的建立 多級索引 。越上層的索引每個塊中表示的數據範圍越大。
如何保證我們建立的多級索引 是「合適」的？
這個合適主要指：存儲的數據量大並且樹高小。同紅黑樹一樣，我們需要一些 限制條件 來保證樹高。這也就是以下數據結構的限制條件原因了。
B樹一個m階（該樹每個節點最多有 M 個子節點）的B樹具有以下特徵：
1.根節點至少有兩個子女。
2.每個中間節點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m
3.每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m
4.所有的葉子節點都位於同一層。
5.每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個子節點包含的元素的值域分劃。
一個3階的B樹插入示意圖如下：
應用場景：MongoDB
B+樹一個m階的B+樹具有以下特徵：
1.有k個子樹的中間節點包含有k個元素（B樹中是k-1個元素），每個元素不保存數據，只用來索引，所有數據都保存在葉子節點。
2.所有的葉子節點中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子節點本身依關鍵字的大小自小而大順序連結。
3.所有的中間節點元素都同時存在於子節點，在子節點元素中是最大（或最小）元素。
看不懂沒關係，我們只需要知道這些限制條件是為了讓B+樹數據「矮而胖」就好。
這裡我直接放張掘金小冊《從根兒上理解MYSQL》B+樹主鍵索引的示意圖：
應用場景
1.Mysql InnoDB存儲引擎。
看到這裡常考面試題來了：B樹和B+樹有什麼區別？為什麼Mongo用B樹？為什麼Mysql用B+樹？
B樹 vs B+樹看圖說話，B樹 和 B+樹顯著不同的地方是：
1.B樹非葉子節點即是索引，也是數據；B+樹非葉子節點僅是索引，數據全部存儲在葉子節點。
2.B+樹葉子節點的數據之間是用鍊表連結的。
這會導致：
B+樹相比B樹：
1.數據的連續性：B+樹葉子節點上一頁存儲的數據是連續的，當需要一個節點上的數據時，B+樹可以增大緩存的命中率。
2.葉子節點之間的連接性：當作範圍或全文掃描時，B+樹可以依賴葉子節點做線性順序掃描，而B樹只能在每一層的節點上做掃描。B+樹同樣可以增大緩存的命中率。
B樹相比B+樹：
當作單一數據查詢時，B樹的節點平均離根節點更近，平均查詢效率比B+樹快。
總結一下：B+樹相比B樹，前者更適合範圍查詢，後者更適合單一數據查詢。
Mongo是非關係型資料庫，數據之間的關係用嵌套解決。它的主要使用場景是：追求 單個讀寫記錄的性能。
Mysql是關係型資料庫，數據之間的關係用共同的索引鍵，Join解決。它的使用場景：不僅存在大量的單一數據查詢，也存在大量的範圍查詢。
所以上面的問題可以簡單扯一扯了吧。