索引的定義

MySQL官方對索引的定義為：索引（Index）是協(xié)助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

本質(zhì)上，索引的目的是為了提高查詢效率，通過不斷地縮小想要獲取數(shù)據(jù)的范圍來篩選出最終想要的結(jié)果，同時把隨機(jī)的事件變成順序的事件，也就是說，有了這種索引機(jī)制，我們可以總是用同一種查找方式來鎖定數(shù)據(jù)。

可以類比銀行的保險柜，比如你要找歸屬你的保險柜子。如果沒有索引，你需要拿著鑰匙，一個個的保險柜的試過去才能找到屬于你的保險柜。但是如果有了索引，而且保險柜能夠以物理分區(qū)的方式存在在對應(yīng)的區(qū)域，同時你可以根據(jù)鑰匙上的編號（A1003-10-17），找到保險柜所在 A1003的存放房間，找到存放室保險柜的第10排，再找到第17個位置，找到屬于你的保險柜，這個定位就快很多了。在沒有索引的情況下，要想完成這個事情還是比較困難的。

索引的原理

除了保險柜之外，生活中可以引出很多類似的索引例子，如字典詞典的目錄、圖書館的檢索錄、火車的座次表等。

它們的原理一致：不斷地縮小數(shù)據(jù)范圍來篩選數(shù)據(jù)，并把隨機(jī)數(shù)據(jù)變成順序數(shù)據(jù)，方便我們更快地鎖定數(shù)據(jù)。

這種索引的理解同樣適用我們的數(shù)據(jù)庫查詢，但是數(shù)據(jù)庫會有很多更復(fù)雜的情況，除了等值查詢外，還有范圍查詢(>、<、between、in)、模糊查詢(like)、并集查詢(or)、交集查詢（and）等等。這就要求數(shù)據(jù)庫選擇更加復(fù)雜和成熟的方式來應(yīng)對所有問題。

根據(jù)我們上面保險柜的案例，可以對數(shù)據(jù)按照一定規(guī)則進(jìn)行拆分，這樣匹配的范圍就降低了，但是這遠(yuǎn)遠(yuǎn)不夠滿足數(shù)據(jù)庫復(fù)雜的查詢要求。于是，數(shù)據(jù)庫系統(tǒng)的設(shè)計者從查詢算法的角度進(jìn)行優(yōu)化。

其中最基本的查詢算法是順序查找（linear search），這種算法復(fù)雜度為O(n)，在數(shù)據(jù)量很大時就很不理想了，而且數(shù)據(jù)量越大，計算越復(fù)雜。

但沒關(guān)系，強(qiáng)大的計算機(jī)科學(xué)提供了更多優(yōu)秀的查找算法，比如二分查找（binary search）、二叉樹查找（binary tree search）等。

但是這些查找算法都要求應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能基于二叉查找樹結(jié)構(gòu)上操作，數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)，理論上也無法同時要求將多列都按順序進(jìn)行組織。

因此，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

這與上面MySQL官方對索引的定義遙相呼應(yīng)了。

看下面的圖：

圖舉例了一種索引方式。右邊是一個數(shù)據(jù)表，這邊一共模擬了兩列七行的數(shù)據(jù)，字段1 的是數(shù)據(jù)記錄的物理地址（實(shí)際應(yīng)用中邏輯上相鄰的記錄在磁盤上并不一定物理相鄰，這邊主要為了舉例）。為了加快字段2 的查找，可以維護(hù)一個左邊所示的二叉查找樹，每個節(jié)點(diǎn)分別包含索引鍵值和一個指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運(yùn)用二叉查找在O(log2n)O(log2n)的復(fù)雜度內(nèi)獲取到相應(yīng)數(shù)據(jù)。

這是索引的一種表現(xiàn)形式，但是實(shí)際的數(shù)據(jù)庫系統(tǒng)中比較普遍是采用B+樹來實(shí)現(xiàn)的。B+樹中的B代表平衡（balance），不是二叉（binary）。因?yàn)锽+樹是從最早的平衡二叉樹演化而來的，所以我們可以先了解下二叉查找樹、平衡二叉樹（AVLTree）和平衡多路查找樹（B-Tree），因?yàn)锽+樹是由這些樹逐步演進(jìn)而來。

二叉查找樹

二叉樹具有以下性質(zhì)：左子樹的鍵值小于根的鍵值，右子樹的鍵值大于根的鍵值。所以左中右是依次遞增的一個過程。

如下圖所示就是一棵二叉查找樹，

觀察該二叉樹有有如下發(fā)現(xiàn)，深度為1的節(jié)點(diǎn)的查找次數(shù)為1，深度為2的查找次數(shù)為2，深度為n的節(jié)點(diǎn)的查找次數(shù)為n，因此其平均查找次數(shù)為 (1+2+2+3+3+3+3) / 7 = 2.4次。

二叉查找樹也可以是如下結(jié)構(gòu)（同樣滿足二叉樹左 < 中 < 大的特性），同樣是7,21,35,42,51,77,89 這七個數(shù)字，也可以按照下圖的方式來構(gòu)造：

但是這棵二叉樹的查詢效率就低了，平均查找次數(shù)為(1+2+3+4+5+6+6)/7=3.8次。

因此若想二叉樹的查詢效率盡可能高，需要這棵二叉樹是平衡的，從而引出新的定義：AVL樹（即平衡二叉樹）。

平衡二叉樹（AVL Tree）

平衡二叉樹（AVL樹）在符合二叉查找樹的條件下，還滿足任何節(jié)點(diǎn)的兩個子樹的高度最大差為1。下面的兩張圖片，左邊是AVL樹，它的任何節(jié)點(diǎn)的兩個子樹的高度差<=1；右邊的不是AVL樹，其根節(jié)點(diǎn)的左子樹高度為3，而右子樹高度為1，高度差>1；

同理，在平衡二叉樹進(jìn)行插入或刪除節(jié)點(diǎn)，也可能導(dǎo)致AVL樹失去平衡，這種失去平衡的二叉樹可以有四種狀態(tài)：LL（左左）、RR（右右）、LR（左右）、RL（右左）。

看下圖示：

我們來逐一看下這幾種狀態(tài)。

LL（LeftLeft），即左左。是指插入或刪除一個節(jié)點(diǎn)后，根節(jié)點(diǎn)的左孩子（Left Child）的左孩子（Left Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的左子樹比右子樹高度>1，AVL樹失去平衡。

RR（RightRight），即右右。是指插入或刪除一個節(jié)點(diǎn)后，根節(jié)點(diǎn)的右孩子（Right Child）的右孩子（Right Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的右子樹比左子樹高度>1，AVL樹失去平衡。

LR（LeftRight），即左右。插入或刪除一個節(jié)點(diǎn)后，根節(jié)點(diǎn)的左孩子（Left Child）的右孩子（Right Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的左子樹比右子樹高度>1，AVL樹失去平衡。

RL（RightLeft），即右左。插入或刪除一個節(jié)點(diǎn)后，根節(jié)點(diǎn)的右孩子（Right Child）的左孩子（Left Child）還有非空節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的右子樹比左子樹高度>1，AVL樹失去平衡。

失去平衡的AVL樹，可以通過旋轉(zhuǎn)來修復(fù)，旋轉(zhuǎn)的本質(zhì)是將樹的節(jié)點(diǎn)進(jìn)行調(diào)整，達(dá)到恢復(fù)平衡的目的。下面逐一來看下。

LL的旋轉(zhuǎn)： LL失去平衡的情況下，可以通過一次旋轉(zhuǎn)讓AVL樹恢復(fù)平衡。步驟如下：

1、將根節(jié)點(diǎn)的左孩子作為新根節(jié)點(diǎn)。

2、將新根節(jié)點(diǎn)的右孩子作為原根節(jié)點(diǎn)的左孩子。

3、將原根節(jié)點(diǎn)作為新根節(jié)點(diǎn)的右孩子。

如下圖所示：

RR的旋轉(zhuǎn)： RR失去平衡的情況下，旋轉(zhuǎn)方法與LL旋轉(zhuǎn)相反，步驟如下：

1、將根節(jié)點(diǎn)的右孩子作為新根節(jié)點(diǎn)。

2、將新根節(jié)點(diǎn)的左孩子作為原根節(jié)點(diǎn)的右孩子。

3、將原根節(jié)點(diǎn)作為新根節(jié)點(diǎn)的左孩子。

如下圖所示：

LR的旋轉(zhuǎn)： LR失去平衡的情況下，需要進(jìn)行兩次旋轉(zhuǎn)，步驟如下：

1、圍繞根節(jié)點(diǎn)的左孩子進(jìn)行RR旋轉(zhuǎn)。

2、圍繞根節(jié)點(diǎn)進(jìn)行LL旋轉(zhuǎn)。

如下圖所示，它轉(zhuǎn)了兩次，最后恢復(fù)成一棵AVL樹：

RL的旋轉(zhuǎn)： RL失去平衡的情況下也需要進(jìn)行兩次旋轉(zhuǎn)，旋轉(zhuǎn)方法與LR旋轉(zhuǎn)相反，步驟如下：

1、圍繞根節(jié)點(diǎn)的右孩子進(jìn)行LL旋轉(zhuǎn)。

2、圍繞根節(jié)點(diǎn)進(jìn)行RR旋轉(zhuǎn)。

如下圖所示，它轉(zhuǎn)了兩次，最后恢復(fù)成一棵AVL樹：

平衡多路查找樹（B-Tree）

我們知道，磁盤這種存儲設(shè)備是以磁盤塊（block）為基本單位的，而B-樹也是基于這種存儲方式設(shè)計的平衡查找樹。

所以當(dāng)我們從系統(tǒng)磁盤讀取數(shù)據(jù)時，以磁盤塊（block）為基本單位映射到內(nèi)存中，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來，而不是只取需要的數(shù)據(jù)。InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認(rèn)每個頁的大小為16KB，可通過參數(shù)innodb_page_size將頁的大小設(shè)置為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

而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達(dá)到頁的大小16KB。

InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位，在查詢數(shù)據(jù)時如果一個頁中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，

這將會減少磁盤I/O次數(shù)，提高查詢效率。

B-Tree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效地找到數(shù)據(jù)所在的磁盤塊。為了描述B-Tree，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值，對應(yīng)表中的主鍵值，data為一行記錄中除主鍵外的數(shù)據(jù)。對于不同的記錄，key值互不相同。

一棵m階的B-Tree有如下特性：

1. 每個節(jié)點(diǎn)最多有m個孩子。

2. 除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外，其它每個節(jié)點(diǎn)至少有Ceil(m/2)個孩子。

3. 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有2個孩子

4. 所有葉子節(jié)點(diǎn)都在同一層，且不包含其它關(guān)鍵字信息

5. 每個非終端節(jié)點(diǎn)包含n個關(guān)鍵字信息（P0,P1,…Pn, k1,…kn）

6. 關(guān)鍵字的個數(shù)n滿足：ceil(m/2)-1 <= n <= m-1

7. ki(i=1,…n)為關(guān)鍵字，且關(guān)鍵字升序排序。

8. Pi(i=1,…n)為指向子樹根節(jié)點(diǎn)的指針。P(i-1)指向的子樹的所有節(jié)點(diǎn)關(guān)鍵字均小于ki，但都大于k(i-1)

B-Tree中的每個節(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支，如下圖所示為一個3階的B-Tree：

每個節(jié)點(diǎn)占用一個盤塊的磁盤空間，一個節(jié)點(diǎn)上有兩個升序排序的關(guān)鍵字和三個指向子樹根節(jié)點(diǎn)的指針，指針存儲的是子節(jié)點(diǎn)所在磁盤塊的地址。兩個鍵值數(shù)據(jù)劃分成的三個范圍域?qū)?yīng)三個指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點(diǎn)為例，兩個鍵值數(shù)據(jù)為33和66，P1指針指向的子樹的數(shù)據(jù)范圍為小于33，P2指針指向的子樹的數(shù)據(jù)范圍為33~66之間，P3指針指向的子樹的數(shù)據(jù)范圍為大于66。

模擬查找關(guān)鍵字55的過程：

1、根據(jù)根節(jié)點(diǎn)找到磁盤塊Disk1，讀入內(nèi)存。第1次操作磁盤I/O。

2、比較鍵值55在區(qū)間（33,66），找到磁盤塊Disk1的指針P2。

3、根據(jù)P2指針找到磁盤塊Disk3，讀入內(nèi)存。第2次操作磁盤I/O。

4、比較鍵值55在區(qū)間（39,62），找到磁盤塊Disk3的指針P2。

5、根據(jù)P2指針找到磁盤塊Disk8，讀入內(nèi)存。第3次操作磁盤I/O。

6、在Disk8中的鍵值列表中找到關(guān)鍵字55。

通過上面的操作過程，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。

B-Tree相對于AVLTree縮減了節(jié)點(diǎn)個數(shù)，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率。

B+Tree

B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲索引結(jié)構(gòu)，InnoDB存儲引擎就是用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

從上面的B-Tree結(jié)構(gòu)圖中可以看到每個節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數(shù)據(jù)較大時將會導(dǎo)致每個節(jié)點(diǎn)（即一個頁）能存儲的key的數(shù)量很小，當(dāng)存儲的數(shù)據(jù)量很大時同樣會導(dǎo)致B-Tree的深度較大，增大查詢時的磁盤I/O次數(shù)，進(jìn)而影響查詢效率。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲key值信息，這樣可以大大加大每個節(jié)點(diǎn)存儲的key值數(shù)量，降低B+Tree的高度，提高查找效率。

B+Tree相比較于B-Tree的不同點(diǎn)：

1、非葉子節(jié)點(diǎn)只存儲鍵值信息。

2、所有葉子節(jié)點(diǎn)之間都有一個鏈指針。

3、數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中。

將上面的B-Tree優(yōu)化，由于B+Tree的非葉子節(jié)點(diǎn)只存儲鍵值信息，假設(shè)每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結(jié)構(gòu)如下圖所示：

通常在B+Tree上有兩個頭指針，一個指向根節(jié)點(diǎn)，另一個指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。因此可以對B+Tree進(jìn)行兩種查找運(yùn)算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。

可能上面例子中只有22條數(shù)據(jù)記錄，看不出B+Tree的優(yōu)點(diǎn)，下面做一個推算：

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)），指針類型也一般為4或8個字節(jié)，也就是說一個頁（B+Tree中的一個節(jié)點(diǎn)）中大概存儲16KB/(8B+8B)=1K個鍵值（因?yàn)槭枪乐担瑸榉奖阌嬎悖@里的K取值為〖10〗^3）。也就是說一個深度為3的B+Tree索引可以維護(hù)10^3 * 10^3 * 10^3 = 10億條記錄。

實(shí)際情況中每個節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫中，B+Tree的高度一般都在2~4層。mysql的InnoDB存儲引擎在設(shè)計時是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在數(shù)據(jù)庫中的實(shí)現(xiàn)即為聚集索引，聚集索引的B+Tree中的葉子節(jié)點(diǎn)存放的是整張表的行記錄數(shù)據(jù)。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵，即主鍵。當(dāng)通過輔助索引來查詢數(shù)據(jù)時，InnoDB存儲引擎會遍歷輔助索引找到主鍵，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)。

總結(jié)

根據(jù)上面，二叉查找樹，紅黑樹等數(shù)據(jù)結(jié)構(gòu)也可以用來實(shí)現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)普遍采用B+Tree作為索引結(jié)構(gòu)（目前MySQL的MYISAM 和 INNODB 都是采用B+Tree作為索引結(jié)構(gòu) ），這是因?yàn)锽+Tree索引的設(shè)計是以計算機(jī)磁盤存儲結(jié)構(gòu)為理論基礎(chǔ)的。

索引以索引文件的形式存儲在磁盤上，當(dāng)采用B+Tree查找的時候，產(chǎn)生磁盤I/O消耗對性能的影響比其他方式小很多（評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度）。

換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)，而B+Tree無疑是較優(yōu)的算法。