索引的底層數據結構

MySQL中常用的是Hash索引和B+樹索引

Hash索引：基于哈希表實現的，查找速度非常快，但是由于哈希表的特性，不支持范圍查找和排序，在MySQL中支持的哈希索引是自適應的，不能手動創建

B+樹的結構

????????B+樹 是一種高效的多路平衡樹，適合磁盤存儲和范圍查詢。它的結構特點包括數據集中在葉子節點、葉子節點連接成鏈表、內部節點僅存儲鍵值和指針。在數據庫和文件系統中，B+樹 被廣泛應用于索引和數據存儲，具有查詢性能穩定、適合高并發等優勢。

?如圖：B+樹具有以下特點：

只有葉子結點才存放數據，中間節點都是用來存放目錄項作為索引

非葉子節點分為不同層次，通過分層來降低每一層的搜索量

B+樹的搜索策略：

從根節點開始，通過二分法快速定位到符合頁內范圍包含查詢值的頁，在中間結點中繼續根據二分法來尋找符合頁內范圍復合查詢值的頁，接著在葉子節點中通過槽查找記錄使用二分法快速定位要查詢的記錄在哪個槽，找到槽后再遍歷槽中所有的記錄，找到尋找的分組。

為什么InnoDB使用B+樹而不是B樹呢?

B-Tree：

• 每個節點既存儲數據也存儲子節點的指針
• 數據分布在所有的節點中，包括內部節點和葉子節點
• 查找時可能會直接在內部節點中就能找到數據不需要遍歷到葉子節點

B+Tree：

• 只有葉子結點存儲數據，內部節點僅存儲鍵值和子節點的指針
• 所有葉子節點通過指針連接成一個有序鏈表
• 查找時必須遍歷到葉子節點才能獲取數據?

B+Tree的優勢：

更適合磁盤I/O：

• 因為B+樹的內部節點不存儲數據只存儲鍵值和指針，所以每個節點可以存儲更多的鍵值，從而降低樹的高度，樹的高度越低磁盤I/O次數越少，查詢性能越高（索引數據量很大，一定是存儲在磁盤中的，每訪問一個節點就會進行一次磁盤IO操作，所以樹的高度越低，一次查詢的期望IO次數就越少，效率就越高）
• B+樹的葉子節點通過指針連接成鏈表，更適合范圍查詢如（BETWEEN，>，<等操作），而樹的范圍查詢需要在不同層級的節點之間跳轉，效率較低?

更適合數據庫場景：

• 數據集中在葉子節點上，查詢時都需要遍歷到葉子節點，這使得查詢性能更穩定。B樹的數據可能分布在內部節點和葉子結點，查詢性能不穩定?
• 數據庫查詢中經常需要使用范圍查詢，B+樹的葉子節點鏈表結構非常適合這種場景，而B樹需要多次遍歷內部節點

更適合并發控制：

• 在并發場景下，B+樹的葉子節點鏈表可以更容易地支持范圍查詢和順序訪問
• 而B樹的結構在并發訪問時可能需要更多的鎖機制（數據分布在內部節點和葉子節點。節點分裂與合并涉及多個節點。鎖的粒度較大，容易導致鎖沖突）

B+樹在InnoDB中的具體應用：

主鍵索引（聚簇索引）：

? ? ? ? InnoDB使用B+樹實現主鍵索引，葉子節點存儲完整的數據行

? ? ? ? 這種設計是的通過主鍵查詢數據時可以直接獲取數據，不需要回表

二級索引（非聚簇索引）：?

? ? ? ? InnoDB的二級索引也是B+樹，但是葉子節點存儲的是主鍵值，通過二級索引查詢時，先獲取主鍵值再通過主鍵索引查找數據（回表）