二叉樹：一個節(jié)點內(nèi)只有【一個】關(guān)鍵值，這個節(jié)點的【左子節(jié)點小于當前節(jié)點】【右子節(jié)點大于當前節(jié)點】投蝉，查詢時膊爪，與當前節(jié)點進行比較，小于當前節(jié)點之值則繼續(xù)進入左子節(jié)點管毙，大于當前值則進入右子節(jié)點腿椎，依次往下找直到找到需求值
但是二叉樹有一個缺點，就是在某種極端情況下會變成線性鏈表的形式
這時候使用二分查找就很浪費性能夭咬，故出現(xiàn)了【平衡二叉樹(AVL樹)】
平衡二叉樹(AVL)：在二叉樹的基礎(chǔ)上要求每個子節(jié)點左右高度差不能超過1層
如果需要插入的去值會讓AVL失衡啃炸，變成非平衡二叉樹，也可以通過左旋右旋進行處理
左旋為逆時針旋轉(zhuǎn)卓舵，右旋為順時針
在插入的過程中南用，會出現(xiàn)一下四種情況破壞AVL樹的特性，我們可以采取如下相應(yīng)的旋轉(zhuǎn)。
1训枢、左-左型：做右旋。
2忘巧、右-右型：做左旋轉(zhuǎn)恒界。
3、左-右型：先做左旋砚嘴，后做右旋十酣。
4、右-左型：先做右旋际长，再做左旋耸采。
紅黑樹：如果在那種插入、刪除很頻繁的場景中工育，平衡樹需要頻繁著進行調(diào)整虾宇，這會使平衡樹的性能大打折扣，為了解決這個問題如绸，于是有了紅黑樹嘱朽，紅黑樹具有如下特點：
1、具有二叉查找樹的特點怔接。
2搪泳、根節(jié)點是黑色的；
3扼脐、每個葉子節(jié)點都是黑色的空節(jié)點（NIL）岸军，也就是說，葉子節(jié)點不存數(shù)據(jù)瓦侮。
4艰赞、任何相鄰的節(jié)點都不能同時為紅色，也就是說脏榆，紅色節(jié)點是被黑色節(jié)點隔開的猖毫。
5、每個節(jié)點须喂，從該節(jié)點到達其可達的葉子節(jié)點是所有路徑吁断，都包含相同數(shù)目的黑色節(jié)點。
B樹(B-樹)：一個節(jié)點內(nèi)包含【多個關(guān)鍵值和多個指針域】坞生，目的在于減少整棵樹的高度
B+樹：基于B樹
特點:
每個父節(jié)點都會出現(xiàn)在子節(jié)點中仔役，是該子節(jié)點的最大或者最小值，根節(jié)點的最大值就等于該B+樹的最大值是己，以后不論插入多少元素又兵，都需要保證根節(jié)點的最大值是整棵樹中最大的
每個葉子節(jié)點都帶有【指針】【指向下一個節(jié)點】，從而行成一個有序鏈表
B+樹中的【衛(wèi)星數(shù)據(jù)(data)】只在葉子節(jié)點存在，而B樹是不論中間節(jié)點或者葉子節(jié)點沛厨，都帶有衛(wèi)星數(shù)據(jù)【聚集索引中宙地，葉子節(jié)點直接包含衛(wèi)星數(shù)據(jù)。在非聚集索引中逆皮，葉子節(jié)點帶有指向衛(wèi)星數(shù)據(jù)的指針】
------------------------------------------------------------------------------------------------------
B+樹的好處：
因為不需要在中間節(jié)點存儲衛(wèi)星數(shù)據(jù)宅粥，則可以在單個節(jié)點存更多數(shù)據(jù)，比B樹減少了中間節(jié)點的層數(shù)电谣，降低IO次數(shù)
B樹的查詢性能不穩(wěn)定秽梅，最低效率可能是整棵樹的層高也可能在第二個節(jié)點就找到，而B+樹則非常穩(wěn)定剿牺，要求必須找到最后一層葉子節(jié)點
-------------------------------
B樹找值??
--------------------------
B+樹找值??
B+樹通過鏈表指針找值
B樹通過中序遍歷找值
