B+樹的原理
B Tree是指Balance Tree 也就是我們經常說到的平衡樹。而所謂的平衡樹是指一個查找樹，并且該樹結構所有的葉子節點都位于同一層。
B+ Tree指基于B Tree和葉子節點順序通路指針而實作的一種資料結構，它具有B Tree的平衡性，同樣也可以通過順序通路指針操作來提升查詢的性能。
在B+ Tree中 來講一個節點中的key是從左往右依次遞減排列，如果某個指針的左右兩個值分别是key1 和 key2 并且 兩個值不為空，那麼指向該節點的所有的key大于等于key1并且小于等于key2。如下圖所示。
在進行查找操作的時候，首先從根節點開始進行二分查找，找到一個key所在的指針，然後在通過遞歸的方式在指針指向的結點中進行查找，并且一直找到子節點。然後在子節點上進行二分查找，并且找到對應的key所對應的data值。
在插入或者删除資料的時候，有時候會打破樹的平衡操作，這個時候就需要對樹結構進行分裂、合并、并且進行左旋轉或者是右旋轉來完成樹的平衡操作。
與紅黑樹的差別
其實紅黑樹等平衡樹也可以實作索引的操作，但是在MySQL中通常采用的是B+Tree的結構來實作索引操作的實作，主要是考慮到如下的幾個原因
更少的查找次數
對于一個平衡查找樹來講其操作的時間複雜度是等于樹的高度，而樹的高度大概是O(logdN) 其中的 d 表示每個節點的出度。
根據紅黑樹的特性，其每個節點的出度為2，而對于B+Tree來講，其出度是非常大的。而一個對數函數我們知道底數越大在相同節點條件下，其值越小，也就是說，在節點相同的情況下，紅黑樹的高度要比B+Tree的高度要高。是以自然而然其查詢效率就會下降。
計算機的預讀取機制
為了減少計算機磁盤的IO操作，磁盤往往不是按照一個嚴格的流程來讀取資料的，而是每次都會進行預讀取，在預讀取的過程中，磁盤會進行順序的讀取，而順序讀取不需要磁盤尋道，并且隻需要很短的轉動時間就可以完成，是以這個讀取會非常的快。
作業系統一般将記憶體和磁盤分割成固态大小的塊，每一塊稱為一頁，記憶體與磁盤以頁為機關交換資料。資料庫系統将索引的一個節點的大小設定為頁的大小，使得一次 I/O 就能完全載入一個節點，并且可以利用預讀特性，相鄰的節點也能夠被預先載入。
MySQL的索引
索引是在存儲引擎層面上實作的，并不是在伺服器層面上實作的，是以不同的存儲引擎有着不同類型的索引以及實作。
B+Tree 索引
是大多數 MySQL 存儲引擎的預設索引類型。因為不再需要進行全表掃描，隻需要對樹進行搜尋即可，是以查找速度快很多。除了用于查找，還可以用于排序和分組。可以指定多個列作為索引列，多個索引列共同組成鍵。
适用于全鍵值、鍵值範圍和鍵字首查找，其中鍵字首查找隻适用于最左字首查找。如果不是按照索引列的順序進行查找，則無法使用索引。
InnoDB 的 B+Tree 索引分為主索引和輔助索引。主索引的葉子節點 data 域記錄着完整的資料記錄，這種索引方式被稱為聚簇索引。因為無法把資料行存放在兩個不同的地方，是以一個表隻能有一個聚簇索引。如下圖所示
輔助索引的葉子節點的 data 域記錄着主鍵的值，是以在使用輔助索引進行查找時，需要先查找到主鍵值，然後再到主索引中進行查找。
哈希索引
哈希索引能以 O(1) 時間進行查找，但是失去了有序性，它具有以下限制:
- 無法用于排序與分組；
- 隻支援精确查找，無法用于部分查找和範圍查找。
InnoDB 存儲引擎有一個特殊的功能叫“自适應哈希索引”，當某個索引值被使用的非常頻繁時，會在 B+Tree 索引之上再建立一個哈希索引，這樣就讓 B+Tree 索引具有哈希索引的一些優點，比如快速的哈希查找。
全文索引
MyISAM 存儲引擎支援全文索引，用于查找文本中的關鍵詞，而不是直接比較是否相等。查找條件使用 MATCH AGAINST，而不是普通的 WHERE。
全文索引一般使用反向索引實作，它記錄着關鍵詞到其所在文檔的映射。
InnoDB 存儲引擎在 MySQL 5.6.4 版本中也開始支援全文索引。
空間資料索引
MyISAM 存儲引擎支援空間資料索引(R-Tree)，可以用于地理資料存儲。空間資料索引會從所有次元來索引資料，可以有效地使用任意次元來進行組合查詢。必須使用 GIS 相關的函數來維護資料。
索引優化
獨立的列
在進行查詢時，索引列不能是表達式的一部分，也不能是函數的參數，否則無法使用索引。
多列索引
在需要使用多個列作為條件進行查詢時，使用多列索引比使用多個單列索引性能更好。例如下面的語句中，最好把 actor_id 和 film_id 設定為多列索引。
索引列的順序
讓選擇性最強的索引列放在前面，索引的選擇性是指: 不重複的索引值和記錄總數的比值。最大值為 1，此時每個記錄都有唯一的索引與其對應。選擇性越高，查詢效率也越高
字首索引
對于 BLOB、TEXT 和 VARCHAR 類型的列，必須使用字首索引，隻索引開始的部分字元。對于字首長度的選取需要根據索引選擇性來确定。
覆寫索引
索引包含所有需要查詢的字段的值。
具有以下優點:
- 索引通常遠小于資料行的大小，隻讀取索引能大大減少資料通路量。
- 一些存儲引擎(例如 MyISAM)在記憶體中隻緩存索引，而資料依賴于作業系統來緩存。是以，隻通路索引可以不使用系統調用(通常比較費時)。
- 對于 InnoDB 引擎，若輔助索引能夠覆寫查詢，則無需通路主索引。
索引的優點
- 大大減少了伺服器需要掃描的資料行數。
- 幫助伺服器避免進行排序和分組，也就不需要建立臨時表(B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY 操作。臨時表主要是在排序和分組過程中建立，因為不需要排序和分組，也就不需要建立臨時表)。
- 将随機 I/O 變為順序 I/O(B+Tree 索引是有序的，也就将相鄰的資料都存儲在一起)。
索引的使用場景
- 對于非常小的表、大部分情況下簡單的全表掃描比建立索引更高效。
- 對于中到大型的表，索引就非常有效。
- 但是對于特大型的表，建立和維護索引的代價将會随之增長。這種情況下，需要用到一種技術可以直接區分出需要查詢的一組資料，而不是一條記錄一條記錄地比對，例如可以使用分區技術。