索引的定義
MySQL官方對索引的定義為：索引（Index）是協助MySQL高效擷取資料的資料結構。
本質上，索引的目的是為了提高查詢效率，通過不斷地縮小想要擷取資料的範圍來篩選出最終想要的結果，同時把随機的事件變成順序的事件，也就是說，有了這種索引機制，我們可以總是用同一種查找方式來鎖定資料。
可以類比銀行的保險櫃，比如你要找歸屬你的保險櫃子。如果沒有索引，你需要拿着鑰匙，一個個的保險櫃的試過去才能找到屬于你的保險櫃。但是如果有了索引，而且保險櫃能夠以實體分區的方式存在在對應的區域，同時你可以根據鑰匙上的編号（A1003-10-17），找到保險櫃所在 A1003的存放房間，找到存放室保險櫃的第10排，再找到第17個位置，找到屬于你的保險櫃，這個定位就快很多了。在沒有索引的情況下，要想完成這個事情還是比較困難的。
索引的原理
除了保險櫃之外，生活中可以引出很多類似的索引例子，如字典詞典的目錄、圖書館的檢索錄、火車的座次表等。
它們的原理一緻：不斷的縮小資料範圍來篩選資料，并把随機資料變成順序資料，友善我們更快地鎖定資料。
這種索引的了解同樣适用我們的資料庫查詢，但是資料庫會有很多更複雜的情況，除了等值查詢外，還有範圍查詢(>、<、between、in)、模糊查詢(like)、并集查詢(or)、交集查詢（and）等等。這就要求資料庫選擇更加複雜和成熟的方式來應對所有問題。
根據我們上面保險櫃的案例，可以對資料按照一定規則進行拆分，這樣比對的範圍就降低了，但是這遠遠不夠滿足資料庫複雜的查詢要求。于是，資料庫系統的設計者從查詢算法的角度進行優化。
其中最基本的查詢算法是順序查找（linear search），這種算法複雜度為O(n)，在資料量很大時就很不理想了，而且資料量越大，計算越複雜。
但沒關系，強大的計算機科學提供了更多優秀的查找算法，比如二分查找（binary search）、二叉樹查找（binary tree search）等。
但是這些查找算法都要求應用于特定的資料結構之上，如二分查找要求被檢索資料有序，而二叉樹查找隻能基于二叉查找樹結構上操作，資料本身的組織結構不可能完全滿足各種資料結構，理論上也無法同時要求将多列都按順序進行組織。
是以，在資料之外，資料庫系統還維護着滿足特定查找算法的資料結構，這些資料結構以某種方式引用（指向）資料，這樣就可以在這些資料結構上實作進階查找算法。這種資料結構，就是索引。
這與上面MySQL官方對索引的定義遙相呼應了。
看下面的圖：
圖舉例了一種索引方式。右邊是一個資料表，這邊一共模拟了兩列七行的資料，字段1的是資料記錄的實體位址（實際應用中邏輯上相鄰的記錄在磁盤上并不一定實體相鄰，這邊主要為了舉例）。為了加快字段2的查找，可以維護一個左邊所示的二叉查找樹，每個節點分别包含索引鍵值和一個指向對應資料記錄實體位址的指針，這樣就可以運用二叉查找在O(log2n)O(log2n)的複雜度内擷取到相應資料。
這是索引的一種表現形式，但是實際的資料庫系統中比較普遍是采用B+樹來實作的。B+樹中的B代表平衡（balance），不是二叉（binary）。因為B+樹是從最早的平衡二叉樹演化而來的，是以我們可以先了解下二叉查找樹、平衡二叉樹（AVLTree）和平衡多路查找樹（B-Tree），因為B+樹是由這些樹逐漸演進而來。
二叉查找樹
二叉樹具有以下性質：左子樹的鍵值小于根的鍵值，右子樹的鍵值大于根的鍵值。 是以左中右是依次遞增的一個過程。
如下圖所示就是一棵二叉查找樹，
觀察該二叉樹有有如下發現，深度為1的節點的查找次數為1，深度為2的查找次數為2，深度為n的節點的查找次數為n，是以其平均查找次數為 (1+2+2+3+3+3+3) / 7 = 2.4次。
二叉查找樹也可以是如下結構（同樣滿足二叉樹 左 < 中 < 大的特性），同樣是7,21,35,42,51,77,89 這七個數字，也可以按照下圖的方式來構造：
但是這棵二叉樹的查詢效率就低了，平均查找次數為(1+2+3+4+5+6+6)/7=3.8次。
是以若想二叉樹的查詢效率盡可能高，需要這棵二叉樹是平衡的，進而引出新的定義：AVL樹（即平衡二叉樹）。
平衡二叉樹（AVL Tree）
平衡二叉樹（AVL樹）在符合二叉查找樹的條件下，還滿足任何節點的兩個子樹的高度最大差為1。下面的兩張圖檔，左邊是AVL樹，它的任何節點的兩個子樹的高度差<=1；右邊的不是AVL樹，其根節點的左子樹高度為3，而右子樹高度為1，高度差>1；
同理，在平衡二叉樹進行插入或删除節點，也可能導緻AVL樹失去平衡，這種失去平衡的二叉樹可以有四種狀态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。
看下圖示：
我們來逐一看下這幾種狀态。
LL（LeftLeft），即 左左。是指插入或删除一個節點後，根節點的左孩子（Left Child）的左孩子（Left Child）還有非空節點，導緻根節點的左子樹比右子樹高度>1，AVL樹失去平衡。
RR（RightRight），即 右右。是指插入或删除一個節點後，根節點的右孩子（Right Child）的右孩子（Right Child）還有非空節點，導緻根節點的右子樹比左子樹高度>1，AVL樹失去平衡。
LR（LeftRight），即 左右。插入或删除一個節點後，根節點的左孩子（Left Child）的右孩子（Right Child）還有非空節點，導緻根節點的左子樹比右子樹高度>1，AVL樹失去平衡。
RL（RightLeft），即 右左。插入或删除一個節點後，根節點的右孩子（Right Child）的左孩子（Left Child）還有非空節點，導緻根節點的右子樹比左子樹高度>1，AVL樹失去平衡。
失去平衡的AVL樹，可以通過旋轉來修複，旋轉的本質是将樹的節點進行調整，達到恢複平衡的目的。下面逐一來看下。
LL的旋轉：LL失去平衡的情況下，可以通過一次旋轉讓AVL樹恢複平衡。步驟如下：
1、将根節點的左孩子作為新根節點。
2、将新根節點的右孩子作為原根節點的左孩子。
3、将原根節點作為新根節點的右孩子。
如下圖所示：
RR的旋轉：RR失去平衡的情況下，旋轉方法與LL旋轉相反，步驟如下：
1、将根節點的右孩子作為新根節點。
2、将新根節點的左孩子作為原根節點的右孩子。
3、将原根節點作為新根節點的左孩子。
LR的旋轉：LR失去平衡的情況下，需要進行兩次旋轉，步驟如下：
1、圍繞根節點的左孩子進行RR旋轉。
2、圍繞根節點進行LL旋轉。
如下圖所示，它轉了兩次，最後恢複成一棵AVL樹：
RL的旋轉：RL失去平衡的情況下也需要進行兩次旋轉，旋轉方法與LR旋轉相反，步驟如下：
1、圍繞根節點的右孩子進行LL旋轉。
2、圍繞根節點進行RR旋轉。
平衡多路查找樹（B-Tree）
我們知道，磁盤這種儲存設備是以磁盤塊（block）為基本機關的，而B-樹也是基于這種存儲方式設計的平衡查找樹。
是以當我們從系統磁盤讀取資料時，以磁盤塊（block）為基本機關映射到記憶體中，位于同一個磁盤塊中的資料會被一次性讀取出來，而不是隻取需要的資料。InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小機關。InnoDB存儲引擎中預設每個頁的大小為16KB，可通過參數innodb_page_size将頁的大小設定為4K、8K、16K，我們可以在指令視窗輸入以下腳本檢視：
1 mysql> show variables like 'innodb_page_size';
2 +------------------+-------+
3 | Variable_name | Value |
4 +------------------+-------+
5 | innodb_page_size | 16384 |
6 +------------------+-------+
7 1 row in set 而系統一個磁盤塊的存儲空間往往沒有這麼大，是以InnoDB每次申請磁盤空間時都會是若幹位址連續磁盤塊來達到頁的大小16KB。
InnoDB在把磁盤資料讀入到磁盤時會以頁為基本機關，在查詢資料時如果一個頁中的每條資料都能有助于定位資料記錄的位置，
這将會減少磁盤I/O次數，提高查詢效率。
B-Tree結構的資料可以讓系統高效的找到資料所在的磁盤塊。為了描述B-Tree，首先定義一條記錄為一個二進制組[key, data] ，key為記錄的鍵值，對應表中的主鍵值，data為一行記錄中除主鍵外的資料。對于不同的記錄，key值互不相同。
一棵m階的B-Tree有如下特性：
1. 每個節點最多有m個孩子。
2. 除了根節點和葉子節點外，其它每個節點至少有Ceil(m/2)個孩子。
3. 若根節點不是葉子節點，則至少有2個孩子
4. 所有葉子節點都在同一層，且不包含其它關鍵字資訊
5. 每個非終端節點包含n個關鍵字資訊（P0,P1,…Pn, k1,…kn）
6. 關鍵字的個數n滿足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)為關鍵字，且關鍵字升序排序。
8. Pi(i=1,…n)為指向子樹根節點的指針。P(i-1)指向的子樹的所有節點關鍵字均小于ki，但都大于k(i-1)
B-Tree中的每個節點根據實際情況可以包含大量的關鍵字資訊和分支，如下圖所示為一個3階的B-Tree：
每個節點占用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的位址。兩個鍵值資料劃分成的三個範圍域對應三個指針指向的子樹的資料的範圍域。以根節點為例，兩個鍵值資料為33和66，P1指針指向的子樹的資料範圍為小于33，P2指針指向的子樹的資料範圍為33~66之間，P3指針指向的子樹的資料範圍為大于66。
模拟查找關鍵字55的過程：
1、根據根節點找到磁盤塊Disk1，讀入記憶體。第1次操作磁盤I/O。
2、比較鍵值55在區間（33,66），找到磁盤塊Disk1的指針P2。
3、根據P2指針找到磁盤塊Disk3，讀入記憶體。第2次操作磁盤I/O。
4、比較鍵值55在區間（39,62），找到磁盤塊Disk3的指針P2。
5、根據P2指針找到磁盤塊Disk8，讀入記憶體。第3次操作磁盤I/O。
6、在Disk8中的鍵值清單中找到關鍵字55。
通過上面的操作過程，發現需要3次磁盤I/O操作，和3次記憶體查找操作。由于記憶體中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。
B-Tree相對于AVLTree縮減了節點個數，使每次磁盤I/O取到記憶體的資料都發揮了作用，進而提高了查詢效率。
B+Tree
B+Tree是在B-Tree基礎上的一種優化，使其更适合實作外存儲索引結構，InnoDB存儲引擎就是用B+Tree實作其索引結構。
從上面的B-Tree結構圖中可以看到每個節點中不僅包含資料的key值，還有data值。而每一個頁的存儲空間是有限的，如果data資料較大時将會導緻每個節點（即一個頁）能存儲的key的數量很小，當存儲的資料量很大時同樣會導緻B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有資料記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上隻存儲key值資訊，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度，提高查找效率。
B+Tree相比較于B-Tree的不同點：
1、非葉子節點隻存儲鍵值資訊。
2、所有葉子節點之間都有一個鍊指針。
3、資料記錄都存放在葉子節點中。
将上面的B-Tree優化，由于B+Tree的非葉子節點隻存儲鍵值資訊，假設每個磁盤塊能存儲4個鍵值及指針資訊，則變成B+Tree後其結構如下圖所示：
通常在B+Tree上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點（即資料節點）之間是一種鍊式環結構。是以可以對B+Tree進行兩種查找運算：一種是對于主鍵的範圍查找和分頁查找，另一種是從根節點開始，進行随機查找。
可能上面例子中隻有22條資料記錄，看不出B+Tree的優點，下面做一個推算：
InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個位元組）或BIGINT（占用8個位元組），指針類型也一般為4或8個位元組，也就是說一個頁（B+Tree中的一個節點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為友善計算，這裡的K取值為〖10〗^3）。也就是說一個深度為3的B+Tree索引可以維護10^3 * 10^3 * 10^3 = 10億 條記錄。
實際情況中每個節點可能不能填充滿，是以在資料庫中，B+Tree的高度一般都在2~4層。mysql的InnoDB存儲引擎在設計時是将根節點常駐記憶體的，也就是說查找某一鍵值的行記錄時最多隻需要1~3次磁盤I/O操作。
資料庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在資料庫中的實作即為聚集索引，聚集索引的B+Tree中的葉子節點存放的是整張表的行記錄資料。輔助索引與聚集索引的差別在于輔助索引的葉子節點并不包含行記錄的全部資料，而是存儲相應行資料的聚集索引鍵，即主鍵。當通過輔助索引來查詢資料時，InnoDB存儲引擎會周遊輔助索引找到主鍵，然後再通過主鍵在聚集索引中找到完整的行記錄資料。
總結
根據上面，二叉查找樹，紅黑樹等資料結構也可以用來實作索引，但是檔案系統及資料庫系統普遍采用B+Tree作為索引結構（目前MySQL的MYISAM 和 INNODB 都是采用B+Tree作為索引結構），這是因為B+Tree索引的設計是以計算機磁盤存儲結構為理論基礎的。
索引以索引檔案的形式存儲在磁盤上，當采用B+Tree查找的時候，産生磁盤I/O消耗對性能的影響比其他方式小很多（評價一個資料結構作為索引的優劣最重要的名額就是在查找過程中磁盤I/O操作次數的漸進複雜度）。
換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數，而B+Tree無疑是較優的算法。
架構與思維·公衆号：撰稿者為bat、位元組的幾位高階研發/架構。不做廣告、不賣課、不要打賞，隻分享優質技術
碼字不易，歡迎關注，歡迎轉載
作者：翁智華
出處：https://www.cnblogs.com/wzh2010/
本文采用「CC BY 4.0」知識共享協定進行許可，轉載請注明作者及出處。