二叉搜索樹（BST）：
根節(jié)點(diǎn)的值大于其左子樹中任意一個(gè)節(jié)點(diǎn)的值，小于其右節(jié)點(diǎn)中任意一節(jié)點(diǎn)的值，這一規(guī)則適用于二叉查找樹中的每一個(gè)節(jié)點(diǎn)。其搜索效率與二叉樹的樹高有關(guān)，其查詢時(shí)間復(fù)雜度為O(logN).
搜索節(jié)點(diǎn)：查找某個(gè)數(shù)字X，從根節(jié)點(diǎn)開始比較。如果X比根節(jié)點(diǎn)大，則去與根節(jié)點(diǎn)的右節(jié)點(diǎn)比較，如此類推，直到找到X（或子節(jié)點(diǎn)為空）為止。
插入新節(jié)點(diǎn)：如果新節(jié)點(diǎn)的key在樹中已經(jīng)存在，則把舊節(jié)點(diǎn)覆蓋；如果沒有，則插入。
查找最小值、最大值：最小值始終在左下的葉子節(jié)點(diǎn)、最大值始終在右下的葉子節(jié)點(diǎn)。
刪除節(jié)點(diǎn)：A. 這個(gè)節(jié)點(diǎn)沒子節(jié)點(diǎn)，此情況最為簡單，直接刪除這個(gè)節(jié)點(diǎn)即可。
?? ?? ? ?B. 這個(gè)節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，把這個(gè)子節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)相連，然后刪除這個(gè)節(jié)點(diǎn)
?? ?? ? ?C. 這個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)：
? ? ? ? ? ? 1. 從此節(jié)點(diǎn)的右節(jié)點(diǎn)下面找出最小的節(jié)點(diǎn)X。
?? ??? ??? ?2. 因?yàn)閄節(jié)點(diǎn)是最小的，所以它的子節(jié)點(diǎn)數(shù)量肯定小于等于1個(gè)，把此子節(jié)點(diǎn)連到X的父節(jié)點(diǎn)上。
?? ??? ??? ?3. 然后用X節(jié)點(diǎn)替換要?jiǎng)h除的節(jié)點(diǎn)。
?? ??? ??? ?4. 刪除要?jiǎng)h除的節(jié)點(diǎn)。
優(yōu)點(diǎn)：查找速度、比較效率較高。
缺點(diǎn)：磁盤io較多，最壞的情況是io數(shù)等于樹高。
所以，就想辦法將“瘦高”的BST變得“矮胖”。
B-樹（?Balance-Tree）
B-樹（不讀做B減樹）是一種多路平衡樹，每個(gè)節(jié)點(diǎn)可以包含多個(gè)孩子，其上限k取決于磁盤大小，我們也把k稱為樹的階。
一個(gè)m階的B樹具有如下幾個(gè)特征：
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è)孩子包含的元素的值域分劃
拿（2，6）結(jié)點(diǎn)為例：包含兩個(gè)元素（2與6），以及3個(gè)孩子1，（3，5），8，并且1小于2，（3，5）介于2與6之間，8大于2，符合特征。
相較于二叉搜索樹，查詢過程的比較次數(shù)并不比二叉搜索樹少，尤其單個(gè)結(jié)點(diǎn)中的元素量較多時(shí)，但相較于磁盤io，內(nèi)存中的比較耗時(shí)基本可以忽略，故而，只要樹的高度足夠低就可以降低IO次數(shù)，大大提升查找性能。
插入操作：
? ? ? ?1、 若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)小于m-1，則直接插入即可。
2、 若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)等于m-1，則將引起結(jié)點(diǎn)的分裂。以中間關(guān)鍵碼為界將結(jié)點(diǎn)一分為二，產(chǎn)生一個(gè)新結(jié)點(diǎn)，并把中間關(guān)鍵碼插入到父結(jié)點(diǎn)(ｋ-1層)中
重復(fù)上述工作，最壞情況一直分裂到根結(jié)點(diǎn)，建立一個(gè)新的根結(jié)點(diǎn)，整個(gè)B樹增加一層。
刪除操作：
根據(jù)key刪除記錄，如果B樹中的記錄中不存對(duì)應(yīng)key的記錄，則刪除失敗。
1）如果當(dāng)前需要?jiǎng)h除的key位于非葉子結(jié)點(diǎn)上，則用后繼key（這里的后繼key均指后繼記錄的意思）覆蓋要?jiǎng)h除的key，然后在后繼key所在的子支中刪除該后繼key。此時(shí)后繼key一定位于葉子結(jié)點(diǎn)上，這個(gè)過程和二叉搜索樹刪除結(jié)點(diǎn)的方式類似。刪除這個(gè)記錄后執(zhí)行第2步
2）該結(jié)點(diǎn)key個(gè)數(shù)大于等于Math.ceil(m/2)-1，結(jié)束刪除操作，否則執(zhí)行第3步。
3）如果兄弟結(jié)點(diǎn)key個(gè)數(shù)大于Math.ceil(m/2)-1，則父結(jié)點(diǎn)中的key下移到該結(jié)點(diǎn)，兄弟結(jié)點(diǎn)中的一個(gè)key上移，刪除操作結(jié)束。
否則，將父結(jié)點(diǎn)中的key下移與當(dāng)前結(jié)點(diǎn)及它的兄弟結(jié)點(diǎn)中的key合并，形成一個(gè)新的結(jié)點(diǎn)。原父結(jié)點(diǎn)中的key的兩個(gè)孩子指針就變成了一個(gè)孩子指針，指向這個(gè)新結(jié)點(diǎn)。然后當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)，重復(fù)上第2步。
原始狀態(tài)：
刪除27
原始狀態(tài)：
刪除32，父節(jié)點(diǎn)下移與兄弟節(jié)點(diǎn)結(jié)合。
[參考博客]https://www.cnblogs.com/nullzx/p/8729425.html
應(yīng)用場(chǎng)景：文件系統(tǒng)、部分?jǐn)?shù)據(jù)庫索引（非關(guān)系型數(shù)據(jù)庫MongoDB）；
B+樹
B+樹是B-樹的變體，具有更高的查詢性能，MySql數(shù)據(jù)庫的索引就是使用的B+樹進(jìn)行查詢。
m階的B+樹具有如下幾個(gè)特征：
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)元素中是最大（或最?。┰亍Ｗ畲?小的元素始終在根節(jié)點(diǎn)。
特點(diǎn)描述：
每個(gè)父節(jié)點(diǎn)元素都出現(xiàn)在子節(jié)點(diǎn)中，并且是最大/小的元素。
每個(gè)葉子節(jié)點(diǎn)都帶有指向下一個(gè)葉子節(jié)點(diǎn)的指針，形成了一個(gè)有序鏈表。
僅葉子節(jié)點(diǎn)有衛(wèi)星數(shù)據(jù)，其它中間節(jié)點(diǎn)都是索引，在非聚集索引（NonClustered Index）中，葉子節(jié)點(diǎn)帶有指向衛(wèi)星數(shù)據(jù)的指針。
由于B+樹的中間節(jié)點(diǎn)不包含衛(wèi)星數(shù)據(jù)，所以相較于B-樹同一磁盤頁可以容納更多的節(jié)點(diǎn)元素。所以查詢過程中的磁盤IO進(jìn)一步降低。查詢的終點(diǎn)始終在葉子節(jié)點(diǎn)所以使得查詢效率非常穩(wěn)定。
優(yōu)勢(shì)（相對(duì)于B-樹）：
1.單一節(jié)點(diǎn)存儲(chǔ)更多的元素，使得查詢的IO次數(shù)更少。
2.所有查詢都要查找到葉子節(jié)點(diǎn)，查詢性能穩(wěn)定。
3.所有葉子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢。
其插入刪除操作與B樹類似。
