數據結構演示網站：Data Structure Visualization

先來了解兩個數據結構B樹與B+樹

B樹：

? ? ? ? N階B樹每個節點最多存儲N-1個Key，N個指針

? ? ? ? 例如：一個5階B樹，當前節點存儲到5個Key時，中間的數會向上分離，形成新節點

????????

? ? ? ???結果如下：B樹是多路平衡搜索樹，進行了自平衡

B+樹：

數據僅存儲在葉子節點，內部節點僅保存鍵和子節點指針。所有查詢必須走到葉子節點才能獲取數據。

葉子節點通過雙向鏈表串聯。

B樹與B+樹區別：

? ? ? ? 1.數據存儲：

? ? ? ? ? ? ? ? B樹：每個節點都有Key和數據

? ? ? ? ? ? ? ? B+樹：只有葉子結點有數據

? ? ? ? 2.結構：

? ? ? ? ? ? ? ? B樹：節點獨立，查找時需要回溯

? ? ? ? ? ? ? ? B+樹：基于雙向鏈表

? ? ? ? 3.查詢：?

? ? ? ? ? ? ? ? B樹：可能提前查找結束，時間不穩定

? ? ? ? ? ? ? ? B+樹：每次都走到葉子結點，時間穩定

索引分類：

? ? ? ? 按數據結構分類：

? ? ? ? ? ? ? ? ①B+樹索引：基于平衡多路搜索樹，用于查詢和排序

? ? ? ? ? ? ? ? ②哈希索引：基于哈希表，用于精準查詢

? ? ? ? ? ? ? ? ③全文索引：基于倒排索引，用于全文檢索

? ? ? ? ? ? ? ? ④R樹索引：使用空間數據，用于地理位置信息

? ? ? ? 按存儲方式分類：

? ? ? ? ? ? ? ? ①聚簇索引：數據存儲在葉子結點，索引即數據，減少回表，效率高，只能有一個

? ? ? ? ? ? ? ? ②非聚簇索引（二級索引）：數據地址存儲在葉子結點，當需要完整數據時需要回表，增加I/O操作，可以創建多個