介紹

    索引用於加快數據訪問的速度。把電腦的磁碟比作一本字典，索引就是欄位的目錄，當我們想快速查到某個詞語的時候只需要通過查詢目錄找到詞語所在的頁數，然後直接打開某頁就可以。MySQL最常用的索引是B+樹索引，為什麼使用B+作為MySQL的索引，這是許多面試官必問的問題。

為什麼B+樹

硬體相關知識

    電腦的磁碟是一個圓盤的介面，圓盤上有一個個的圓圈，數據就是記錄在這些圓圈的扇區上。如下圖所示

當電腦系統讀取數據的時候要通過以下幾個步驟：
1、首先移動臂根據柱面號使磁頭移動到所需要的柱面上，這一過程被稱為尋道。所耗費的時間叫尋道時間(ts)。
2、目標扇區旋轉到磁頭下，這個過程耗費的時間叫旋轉時間。
    因此訪問磁碟的時間由三部分構成： 尋道時間+旋轉時間+數據傳輸時間 
第一部分尋道時間延遲最高，最大可達到100ms，旋轉時間取決於磁碟的轉速，轉速在7200轉/分鐘的磁碟平均旋轉時間在5ms左右。磁碟的讀取是以block(盤塊)為單位的，位於同一個盤塊的數據可以一次性讀取出來。在讀寫數據的時候儘量減少磁頭來回移動的次數，避免過多的查找時間。如果每次從磁碟上讀取數據的時候都要經歷上面的幾個過程那麼效率上無疑是極低的。

為什麼B+樹

    從上面可以看到，如果隨機訪問磁碟的速度是很慢的，因此需要設計一個合理的數據結構來減少隨機訪問磁碟的次數。B樹就是這樣一種數據結構。

B樹、B+樹介紹

B樹

    B樹是為存儲設備而設計的一種多叉平衡查找樹。它與紅黑樹類似，但是在降低IO操作方面B樹的表現要更好一些，B樹與紅黑樹最大的區別在於B樹可以有多個子節點，紅黑樹最多是有兩個子節點，這就決定了大多數情況下B樹的高度要比紅黑樹低很多，因此在查找的時候能夠降低IO次數。下圖是一棵B樹：

B 樹又叫平衡多路查找樹。一棵m階的B樹的特性如下：
    a.樹中每個結點最多含有m個孩子（m>=2）；
    b.除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是一個取上限的函數）；
    c.若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點）；
    d.所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息
    e.每個非終端結點中包含有n個關鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
        a) Ki (i=1…n)為關鍵字，且關鍵字按順序升序排序K(i-1)< Ki。 
        b) Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結點的關鍵字均小於Ki，但都大於K(i-1)。 
        c) 關鍵字的個數n必須滿足： [ceil(m / 2)-1]<= n <= m-1。
    B樹中的每個節點都儘可能存儲多的關鍵字信息和分支信息，但是不會超過磁碟塊的大小。這樣在有效降低了樹的高度，在查找的時候可以快速定位在指定的磁碟塊。假如要從上圖中找到79這個數字，首先從根節點開始掃描，79大於35所以選擇P3指針，指向磁碟塊4，在磁碟塊4中79在65和87之間，因此選擇P2指針，選擇磁碟塊10，這時候就可以從磁碟塊10中找到79。整個過程只需要3次IO，如果這棵樹被緩存在記憶體中，那麼只需要一次IO就可以讀到79這個數字。

B+樹

    B+樹是B的變種，一顆m階B+樹和m階B樹的異同點在於：
    1、有n棵子樹的節點中有n-1個關鍵字(與B樹n棵子樹有n-1個關鍵字，保持一致)
    2、所有的葉子節點中包含了全部的關鍵字的信息，以及指向含有這些關鍵字記錄的指針，且葉子節點本身依關鍵字的大小而自小而大順序鏈接(而B樹的葉子節點並沒有包含全部需要查找的信息)
    3、所有的非終端節點可以看成索引部分，節點中僅含有其子樹根節點中最大或者最小的關鍵字(而B樹的非終節點也要包含需要查找的有效信息)
    
由於B+樹的葉子節點是連接在一起的，因此相對於使用B樹作為索引，對於MySQL的範圍查詢更加優化。同時由於葉子節點包含所有關鍵字信息，因此有的查詢語句就不需要回表，只需要查詢索引就可以查到需要的數據。

索引類型

B樹索引

    雖然是叫B樹索引，但是資料庫實際上使用的是B+樹來組織數據。B樹索引意味著所有值都是按照順序存儲的，並且每個葉子節點到根節點的距離是相同的。
假如有如下數據表：

CREATE TABLE `people` (
  `last_name` varchar(50) DEFAULT NULL,
  `first_name` varchar(50) DEFAULT NULL,
  `dob` date DEFAULT NULL,
  `gender` enum('m','f') DEFAULT NULL,
  KEY `last_name` (`last_name`,`first_name`,`dob`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

該表對last_name,first_name,dob三列建立了索引，索引的組織方式如下：

當同時對多列進行索引的時候，索引的順序是非常重要的，上面的索引首先是按照last_name進行索引，在last_name相同的情況下在對first_name進行排序，最後是dob欄位。
    B樹索引適用於全鍵值、鍵值範圍和最左首碼查找:
全鍵值
    查找名字為Allen Kim，出生日期為1930-07-12的人，這樣的查找方式匹配了索引中的所有欄位，依次掃描索引中的last_name、first_name和dob欄位，找到對應的數據。
鍵值範圍
    查找姓名在Allen和Barrymore之間的人，這種查找方式也會使用到索引。需要註意的是這裡只能是索引中的第一列，也就是last_name的範圍查找。
首碼匹配
    查找last_name是以Al開頭的人，這種查詢會以此掃描索引中的節點，然後選出來對應的複合條件的行。也是只能使用第一列的首碼查詢。如果是說想查first_name的首碼匹配，那麼是無法使用到索引的，意味著要進行全表掃描。
精確匹配某一列，範圍批量另外一列
    精確匹配的列必須是所以中的第一列，範圍匹配的列是第二列，這樣才能使用到上面的索引。

B樹索引的使用限制：
1、不是按照最左列開始查詢的，無法使用索引。
2、不能跳過索引的列進行查詢。
3、如果使用到了範圍匹配，那麼範圍匹配右邊的列都無法使用索引查詢。

哈希索引

    哈希索引使用哈希表來實現，只有是精確匹配的時候才會生效。存儲引擎會對索引列計算出一個哈希值，然後保存一個哈希值到行數據的指針。哈希索引由於其特殊的組織方式，限制了其使用場景。哈希索引只適合值比較少的情況，例如枚舉類型。在以下幾種方式中是不適合使用哈希索引的：
1、哈希索引只包含哈希值和指針，不存儲欄位值，因此使用哈希索引避免不了要進行回表查詢。
2、哈希索引數據並不是按照值的順序進行排序的，因此哈希索引無法用來排序
3、哈希索引不支持部分索引列匹配。比如說在(A,B)兩列上簡歷哈希索引，那麼只有在同時使用A、B兩列查詢的時候才會使用哈希索引，只使用A列查詢無法使用哈希索引。
4、哈希索引只支持等值比較，不支持像between and這種範圍查詢。
5、使用哈希索引的時候應該儘量避免哈希衝突。

後記

    資料庫的索引機制解決的問題是在訪問記憶體數據與磁碟數據的速度差別很大的情況下，如何快速訪問數據的問題。只有瞭解了索引的原理才可以更好的設計表的索引欄位以及寫出性能更優的查詢語句。在我們寫SQL語句的時候頭腦中應該大體上能規划出查詢數據以及如何使用索引的過程。下一篇會介紹一下高性能索引的策略，帶你設計出更優的索引。

----------------------------------------------------------------

歡迎關註我的微信公眾號：yunxi-talk，分享Java乾貨，進階Java程式員必備。

​​​