但是如果被問到，為什麼用了索引之後，查詢就會變快？B+ Tree 索引的原理是什麼？這時候很多人可能就不知道了，今天我就以 MySQL 的 InnoDB 引擎為例，講一講 B+ Tree 索引的原理。

索引的基礎知識

MySQL 的基本儲存結構是頁，大概就是這個樣子的：

在這裡，我們需要了解以下幾點（非常重要）：

當我們用 MySQL 的 InnoDB 引擎建立表，有且只能有一個主鍵；如果我們沒有顯示地指定之間，那麼MySQL 會自動生成一個隱含欄位作為主鍵；

聚集索引：以主鍵建立的索引；聚集索引的葉子節點儲存的是表中的資料；

非聚集索引：非主鍵建立的索引；非聚集索引在葉子節點儲存的是主鍵和索引列；使用非聚集索引查詢資料，會查詢到葉子上的主鍵，再根據主鍵查到資料（這個過程叫做回表）。

頁和頁之間、頁和資料之間的關係

我們以聚集索引做講解，頁和頁之間、以及頁和資料之間的關係是這樣的：

資料頁和資料頁之間，組成一個雙向連結串列；

每個資料頁中的記錄，是一個單向連結串列；

每個資料頁都根據內部的記錄生成一個頁目錄（Page directory），如果是主鍵的話，可以在頁目錄中使用二分法快速定位；

如果我們根據一個非主鍵、非索引列進行查詢，那麼需要遍歷雙向連結串列，找到所在的頁；再遍歷頁內的單向連結串列；如果表內資料很大的話，這樣的查詢就會很慢。

B+ Tree 索引的原理

先讓我們看看 B+ Tree 索引大概是什麼樣子（以聚集/主鍵索引為例）：

假如這時候我們要查詢 id = 16 的資料：

查詢頁-1，找到頁-2 儲存的是小於 30 的資料；

查詢頁-2，找到頁-5 儲存的是 10~20 的資料；

查詢頁-5，找到 id = 16 的資料。

很顯然，沒有用索引的時候，需要遍歷雙向連結串列來定位對應的頁，而有了索引，則可以透過一層層“目錄”定位到對應的頁上。

索引是儲存引擎用於快速查詢記錄的資料結構，MySQL 資料庫內部索引是由不同的引擎實現的，主要說一下最常用的InnoDB引擎中的索引，InnoDB引擎中的索引是使用B+ 樹的結構來儲存的，B+ 樹結構如下圖：

先來說一下B+ 樹的特點：

葉子節點（最下面一層）儲存關鍵字（索引欄位的值）資訊及對應的全部資料記錄。

非葉子節點只儲存關鍵字的資訊及子節點的指標。

每個葉子節點相當於MySQL中的一個數據頁，同層級的葉子節點以雙向連結串列的形式連線。

每個節點中儲存了多條記錄，記錄之間用單鏈表的形式連線組成了一條有序的連結串列。

在 B+ 樹中檢索資料時：每次檢索都從根節點開始，一直搜尋到葉子節點。

InnoDB 的資料是按資料頁為單位來讀寫的。也就是說，當需要讀取一條記錄的時候，並不是將這個記錄本身從磁碟讀取出來，而是以頁為單位，將整個也載入到記憶體中，一個頁中可能有很多記錄，然後在記憶體中對頁透過二分法進行檢索。在InnoDB 中，每個頁的大小預設是16kb。

總體來說，MySQL中的索引用到了B+樹、連結串列、二分法，實現了快速查詢資料。

MySQL索引型別

InnoDB 中有兩種索引型別：主鍵索引與輔助索引。

主鍵索引（聚集索引）：每個表只有一個主鍵索引，葉子節點同時儲存了主鍵的值以及對應的全部記錄。

輔助索引（非聚集索引）：葉子節點儲存了索引欄位的值以及主鍵的值。

我們以上圖中Person表 為例，其中id 是主鍵，name 是輔助索引，接下里我們來看一下InnoDB引擎中資料檢索過程：

若需要查詢 id=1 的資料，只需要使用主鍵索引中檢索就可以查詢到資料。（紅色線）

若需要搜尋 name="Jacy" 的資料，需要使用非聚集索引與聚集索引，需要2步（藍色線）：

先透過輔助索引中檢索 name="Jacy"的資料，獲取 id 的值。

再透過id值 到主鍵索引中 檢索id=12的資料。

接下來，我們再看下以下查詢的資料檢索過程。

主鍵索引（或唯一索引）查詢

上圖中所有的資料都是唯一的，我們查詢26的記錄，過程如下：

首先把page1 頁載入到記憶體中透過二分法查詢。

確定26位於[20,40)中間，然後載入20所關聯的page3 頁.

將page3 頁載入到記憶體中，採用二分法找到26的記錄後退出。

非唯一索引查詢

上圖中查詢26的所有記錄，資料不唯一，過程如下：

將page1 頁載入到記憶體中透過二分法查詢。

確定26位於[20,40)中間，然後載入20所關聯的page3 頁。

將page3 頁載入到記憶體中透過二分法找到最後一個小於26的記錄是23，然後透過連結串列從23開始向後訪問，找到所有的26記錄，直到遇到第一個大於26的值退出。

模糊查詢

上圖中查詢以 b字母開頭的所有記錄，過程如下：

將page1頁載入到記憶體中，透過二分法查詢最後一個小於等於b的值(b)，和第一個大於b的(z)，b指向葉節點page3，z指向葉節點page5。

如此一來，可以確定以 b 開頭的記錄存在於[page3,page5) 這個範圍內。

最後依次載入page3 到記憶體中，透過二分法找到第一條b開頭的記錄，然後以連結串列方式繼續向後訪問page4 中的記錄，直至遇到一個字母為z的值退出。

如果查詢包含b的記錄，是如何執行的呢？

當我們使用 "%b%" 全模糊查詢時，透過索引我們還可以快速定位所在的頁嘛？

如上圖包含b字母的資料在每個頁中都存在，因此無法判斷包含 b 的記錄在哪些頁中，只能透過IO的方式載入所有頁，遍歷所有記錄進行過濾，才可以找到包含b的記錄。因此使用LIKE %b%進行全模糊查詢時，索引是無效的。

更多內容可以瀏覽《MySQL資料庫中如何正確的理解與使用索引》https://www.toutiao.com/i6759910720944472588/

這個問題和線性查詢、二分查詢是有很大關係的。索引後的資料可以使用二分法查詢，未索引的資料查詢需要線性查詢。下面詳細說一下這兩者之間的效能區別。

1、兩者的查詢原理

①、線性查詢

線性查詢又稱順序查詢，它的查詢原理就是從第一條記錄開始，逐個比較要查詢的欄位，直到欄位內容和查詢值相等，則查詢成功，返回結果。若比較結果與欄位所有記錄都不等，則查詢失敗。下面舉例說明：

需要在某個記錄數為N的陣列a[]中查詢元素k，那麼，線性查詢就是從a[1]開始和k進行對比，對比相等則返回a[i]，如果，不相等則繼續下一個查詢， i=i+1。直到 i=N為止。那線性查詢的效能就一目瞭然：

最好的情況就是對比1次就找到結果。最差的情況就是需要對比N次才能找到結果。平均計算，就是N/2次能找到結果。

②、二分查詢

二分法查詢也可以說是分段查詢。主要原理就是對已經排序的一組資料進行中間分段，中間分界點和查詢值對比。如果數值小於分界點，則要查詢的數落在前半段；如果數字大於分界點，則要查詢的數落在前半段；如果等於分界點，則要查詢數就已經找到。下面同樣舉例說明：

需要在某個記錄數為N且已經排好序的陣列a[]中查詢元素K，那麼，二分查詢首先是確定陣列的中點a[x]，其實也就是a[N/2]這個值（N/2採用進一法取整）。然後對比a[x]和K值，按照前面的方法迴圈縮小對比的區間，最終找到想要的值。二分查詢的效能如下：

二分法查詢N條記錄需要log2（N）次對比就能找到結果。前提是：陣列必須要排好序2、索引給資料庫查詢帶來的效能變化

資料庫中建立索引其實就是對資料庫表中一列或多列的值進行排序的結構。其實就是為了給二分查詢做好排序的前提。結合前面兩種查詢的原理，我們就很容易理解資料庫中索引變快的原因了。其實，資料庫通常情況下，資料量都是比較大的，一般都是上萬條，甚至達到億級記錄。我們用前面原理中的公式計算對比一下：

在10萬條記錄中查詢一個值：那麼，N=100000；線性查詢效能=N/2，計算可得，平均需要對比50000次;二分查詢效能=log2(N)，計算可得，大約需要17次；

從上面計算對比，我們可以看到，索引好了用二分查詢的效能會比線性查詢快非常多。

3、資料庫哪裡應該加索引

雖然加了索引後，查詢效能提升很多。但是在資料庫裡面也是不所有欄位都加索引的，因為，資料庫的整體效能不僅需要考慮查詢效能，還需要考慮寫入效能。當你在資料庫中某個欄位加入索引後，該欄位就需要建立對應的索引指標。每次新寫入或者修改欄位的記錄，都需要額外寫入索引指標。所以，在資料庫中，加入索引會加快搜索效能，但也會相應降低一點點寫入效能。所以，資料庫中建立索引一般在以下幾種情況建立索引。

經常需要搜尋的列，增加索引可以加快搜索速度；作為主鍵的列，強制該列的唯一性和組織表中資料的排列結構；在經常用在連線的列上，這些列主要是一些外來鍵，可以加快連線的速度；在經常需要根據範圍進行搜尋的列上建立索引，因為索引已經排序，其指定的範圍是連續的在經常需要排序的列上建立索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間在經常使用在WHERE子句中的列上面建立索引，加快條件的判斷速度總結

總之，資料庫中因為存在大量的資料，建立索引相當於對資料進行了排序，可以使用二分查詢法來查詢資料，確實會大大提高查詢的速度。但是也會相應降低一點點寫入的速度，所以，資料庫中的索引也是有針對性的建立索引的。

什麼是資料庫索引？

資料庫中的索引類似於書籍中的目錄，目錄可以快速獲取資訊，而不需要閱讀整本書。

在資料庫中，索引可以讓資料庫程式在不掃描整張表的情況下找到所需的資料。本書包含一組章節，並列出包含章節的頁碼。資料庫中的索引是表中一列或多列中的一組值，相應的索引列表代表這些值。

索引欄位可以是單個欄位也可以是多個欄位的組合，如果是多個欄位的組合，其索引值的排列首先按第一個欄位值進行排列，如果其值相同，再按第二個欄位的值進行排列，以此類推。

使用索引的意義有哪些？

資料庫中的糖指數類似於書中的目錄值，用於提高資訊檢索速度。

使用索引搜尋資料不需要掃描整個表格，也不需要快速搜尋資料。

索引使用的成本

糖指數需要佔據物理記憶體之外的位置。建立和執行索引需要一定的時間。

©更新索引表時，服務資料重建的速度要放慢。

資料庫索引類別

索引不需要重新排列檔案中記錄的順序。一個檔案可以有多個相互關聯的索引，每個索引支援鍵碼，透過索引可以快速訪問檔案中的記錄。

1、靜態索引

靜態索引是在建立檔案時建立的索引結構。檔案完成後，只有在重新組織時才能修改。2、動態索引

在一段時間內發生索引（主要是新增、修改、刪除資料。如果頁面已經完成，則需要對頁面進行分割，頻率分開，導致索引碎片增多），從而導致索引頁面分割。這樣會導致隨機訪問I/O檔案，而不是按照I/O的順序進行讀取，所以對索引的訪問速度會比較慢。如果碎片數量太多，資料庫可能不會使用索引（太慢，資料庫會選擇更高效的執行計劃）。

如何更好地使用資料庫索引

索引欄位非常小，最好有一個值，如整個值，如INT；對於經常變化的欄位，儘量不要建立索引，索引管理成本很高，生成索引碎片比較容易；如定期索引管理，修正索引碎片；不建立或維護不必要的重複索引，會增加資料變化（新增、修改、刪除）的成本。使用唯一的高欄位建立索引，不能在弱欄位如樓層中建立索引。

在SQL句子In中，儘量不要使用函式、運算子或表示式來計算where，這可能會導致索引的錯誤使用；必須避免在子空間語句中包含空值，否則會導致引擎在表被完全掃描時停止使用索引；你應該避免在句子中使用任何! =或<<，否則會導致引擎停止使用索引來掃描表。

索引簡單來說就是一本字典的目錄，資料量小的時候，字典比較薄，全部一掃而過，瞬間就能查詢到你指定的資料，但是隨著資料量的增加，字典越來越厚，全部掃，費時費力（消耗大量的系統記憶體，磁碟瞬間IO也會越來越吃緊，佔用大量系統資源，程序得不到釋放），這時候如果給字典新增加個對應章節（表）目錄，我們直接透過目錄就能快速檢索到有用資料，不會漫無邊際的全部掃，再去過濾。當然由於你新建了目錄（索引），肯定會佔用一定的字典空間，當然針對你的查詢來說，透過空間換時間，這個還是很值得的。針對插入，由於你需要往指定目錄（有索引的表）插入資料，字典（資料庫系統）需要重新更新制定目錄並且維護目錄資訊，因此插入這個過程會慢，如何解決這一問題呢，我們可以刪除指定目錄（索引或者分割槽），資料全部處理好以後重新建立目錄。