該樓層疑似違規已被系統折疊?隱藏此樓查看此樓
一、索引B+ Tree 原理1. 數據結構
B Tree 指的是 Balance Tree，也就是平衡樹。平衡樹是一顆查找樹，并且所有葉子節點位于同一層。
B+ Tree 是基于 B Tree 和葉子節點順序訪問指針進行實現，它具有 B Tree 的平衡性，并且通過順序訪問指針來提高區間查詢的性能。
在 B+ Tree 中，一個節點中的 key 從左到右非遞減排列，如果某個指針的左右相鄰 key 分別是 keyi 和 keyi+1，且不為 null，則該指針指向節點的所有 key 大于等于 keyi 且小于等于 keyi+1
2. 操作
進行查找操作時，首先在根節點進行二分查找，找到一個 key 所在的指針，然后遞歸地在指針所指向的節點進行查找。直到查找到葉子節點，然后在葉子節點上進行二分查找，找出 key 所對應的 data。
插入刪除操作會破壞平衡樹的平衡性，因此在插入刪除操作之后，需要對樹進行一個分裂、合并、旋轉等操作來維護平衡性。
3. 與紅黑樹的比較
紅黑樹等平衡樹也可以用來實現索引，但是文件系統及數據庫系統普遍采用 B+ Tree 作為索引結構，主要有以下兩個原因：
(一)更少的查找次數
平衡樹查找操作的時間復雜度和樹高 h 相關，O(h)=O(logdN)，其中 d 為每個節點的出度。
紅黑樹的出度為 2，而 B+ Tree 的出度一般都非常大，所以紅黑樹的樹高 h 很明顯比 B+ Tree 大非常多，查找的次數也就更多。
(二)利用磁盤預讀特性
為了減少磁盤 I/O 操作，磁盤往往不是嚴格按需讀取，而是每次都會預讀。預讀過程中，磁盤進行順序讀取，順序讀取不需要進行磁盤尋道，并且只需要很短的旋轉時間，速度會非常快。
操作系統一般將內存和磁盤分割成固定大小的塊，每一塊稱為一頁，內存與磁盤以頁為單位交換數據。數據庫系統將索引的一個節點的大小設置為頁的大小，使得一次 I/O 就能完全載入一個節點。并且可以利用預讀特性，相鄰的節點也能夠被預先載入。
MySQL 索引
索引是在存儲引擎層實現的，而不是在服務器層實現的，所以不同存儲引擎具有不同的索引類型和實現。
1. B+Tree 索引
是大多數 MySQL 存儲引擎的默認索引類型。
因為不再需要進行全表掃描，只需要對樹進行搜索即可，所以查找速度快很多。
除了用于查找，還可以用于排序和分組。
可以指定多個列作為索引列，多個索引列共同組成鍵。
適用于全鍵值、鍵值范圍和鍵前綴查找，其中鍵前綴查找只適用于最左前綴查找。如果不是按照索引列的順序進行查找，則無法使用索引。
