二叉樹：一個節(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樹的特性，我們可以采取如下相應的旋轉(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樹通過中序遍歷找值
