摘要

本文以MySQL數(shù)據(jù)庫(kù)為研究對(duì)象，討論與數(shù)據(jù)庫(kù)索引相關(guān)的一些話題。特別需要說(shuō)明的是，MySQL支持諸多存儲(chǔ)引擎，而各種存儲(chǔ)引擎對(duì)索引的支持也各不相同，因此MySQL數(shù)據(jù)庫(kù)支持多種索引類型，如BTree索引，哈希索引，全文索引等等。為了避免混亂，本文將只關(guān)注于BTree索引，因?yàn)檫@是平常使用MySQL時(shí)主要打交道的索引，至于哈希索引和全文索引本文暫不討論。

常見(jiàn)的查詢算法及數(shù)據(jù)結(jié)構(gòu)

為什么這里要講查詢算法和數(shù)據(jù)結(jié)構(gòu)呢？因?yàn)橹砸⑺饕?，其?shí)就是為了構(gòu)建一種數(shù)據(jù)結(jié)構(gòu)，可以在上面應(yīng)用一種高效的查詢算法，最終提高數(shù)據(jù)的查詢速度。

索引的本質(zhì)

MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。提取句子主干，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。

常見(jiàn)的查詢算法

我們知道，數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者會(huì)從查詢算法的角度進(jìn)行優(yōu)化。那么有哪些查詢算法可以使查詢速度變得更快呢？

順序查找（linear search ）

最基本的查詢算法當(dāng)然是順序查找（linear search），也就是對(duì)比每個(gè)元素的方法，不過(guò)這種算法在數(shù)據(jù)量很大時(shí)效率是極低的。

• 數(shù)據(jù)結(jié)構(gòu)：有序或無(wú)序隊(duì)列
• 復(fù)雜度：O(n)

//順序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}

二分查找（binary search）

比順序查找更快的查詢方法應(yīng)該就是二分查找了，二分查找的原理是查找過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜素過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。

• 數(shù)據(jù)結(jié)構(gòu)：有序數(shù)組
• 復(fù)雜度：O(logn)

//二分查找，遞歸版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

二叉排序樹(shù)查找

二叉排序樹(shù)的特點(diǎn)是：

• 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
• 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
• 它的左、右子樹(shù)也分別為二叉排序樹(shù)。

搜索的原理：

• 若b是空樹(shù)，則搜索失敗，否則：
• 若x等于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功；否則：
• 若x小于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹(shù)；否則：查找右子樹(shù)
• 數(shù)據(jù)結(jié)構(gòu)：二叉排序樹(shù)
• 時(shí)間復(fù)雜度： O(log2N)

哈希散列法(哈希表)

其原理是首先根據(jù)key值和哈希函數(shù)創(chuàng)建一個(gè)哈希表（散列表），燃耗根據(jù)鍵值，通過(guò)散列函數(shù)，定位數(shù)據(jù)元素位置。

• 數(shù)據(jù)結(jié)構(gòu)：哈希表
• 時(shí)間復(fù)雜度：幾乎是O(1)，取決于產(chǎn)生沖突的多少。

分塊查找

分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法。其算法思想是將n個(gè)數(shù)據(jù)元素”按塊有序”劃分為m塊（m ≤ n）。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須”按塊有序”；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，依次類推。
　　
算法流程：

• 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表；
• 查找分兩個(gè)部分：先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；然后，在已確定的塊中用順序法進(jìn)行查找。

這種搜索算法每一次比較都使搜索范圍縮小一半。它們的查詢速度就有了很大的提升。如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹(shù)查找只能應(yīng)用于二叉查找樹(shù)上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

平衡多路搜索樹(shù)B樹(shù)（B-tree）

上面講到了二叉樹(shù)，它的搜索時(shí)間復(fù)雜度為O(log2N)，所以它的搜索效率和樹(shù)的深度有關(guān)，如果要提高查詢速度，那么就要降低樹(shù)的深度。要降低樹(shù)的深度，很自然的方法就是采用多叉樹(shù)，再結(jié)合平衡二叉樹(shù)的思想，我們可以構(gòu)建一個(gè)平衡多叉樹(shù)結(jié)構(gòu)，然后就可以在上面構(gòu)建平衡多路查找算法，提高大數(shù)據(jù)量下的搜索效率。

B Tree

B樹(shù)（Balance Tree）又叫做B- 樹(shù)（其實(shí)B-是由B-tree翻譯過(guò)來(lái)，所以B-樹(shù)和B樹(shù)是一個(gè)概念） ，它就是一種平衡路查找樹(shù)。下圖就是一個(gè)典型的B樹(shù)：

image

從上圖中我們可以大致看到B樹(shù)的一些特點(diǎn)，為了更好的描述B樹(shù)，我們定義記錄為一個(gè)二元組[key, data]，key為記錄的鍵值，data表示其它數(shù)據(jù)（上圖中只有key，沒(méi)有畫(huà)出data數(shù)據(jù) ）。下面是對(duì)B樹(shù)的一個(gè)詳細(xì)定

• 有一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)只有一個(gè)記錄和兩個(gè)孩子或者根節(jié)點(diǎn)為空；
• 每個(gè)節(jié)點(diǎn)記錄中的key和指針相互間隔，指針指向孩子節(jié)點(diǎn)；
• d是表示樹(shù)的寬度，除葉子節(jié)點(diǎn)之外，其它每個(gè)節(jié)點(diǎn)有[d/2,d-1]條記錄，并且些記錄中的key都是從左到右按大小排列的，有[d/2+1,d]個(gè)孩子；
• 在一個(gè)節(jié)點(diǎn)中，第n個(gè)子樹(shù)中的所有key，小于這個(gè)節(jié)點(diǎn)中第n個(gè)key，大于第n-1個(gè)key，比如上圖中B節(jié)點(diǎn)的第2個(gè)子節(jié)點(diǎn)E中的所有key都小于B中的第2個(gè)key 9，大于第1個(gè)key 3;
• 所有的葉子節(jié)點(diǎn)必須在同一層次，也就是它們具有相同的深度；

由于B-Tree的特性，在B-Tree中按key檢索數(shù)據(jù)的算法非常直觀：首先從根節(jié)點(diǎn)進(jìn)行二分查找，如果找到則返回對(duì)應(yīng)節(jié)點(diǎn)的data，否則對(duì)相應(yīng)區(qū)間的指針指向的節(jié)點(diǎn)遞歸進(jìn)行查找，直到找到節(jié)點(diǎn)或找到null指針，前者查找成功，后者查找失敗。B-Tree上查找算法的偽代碼如下：

BTree_Search(node, key) {
     if(node == null) return null;
     foreach(node.key){
          if(node.key[i] == key) return node.data[i];
          if(node.key[i] > key) return BTree_Search(point[i]->node);
      }
     return BTree_Search(point[i+1]->node);
  }
data = BTree_Search(root, my_key);

關(guān)于B-Tree有一系列有趣的性質(zhì)，例如一個(gè)度為d的B-Tree，設(shè)其索引N個(gè)key，則其樹(shù)高h(yuǎn)的上限為logd((N+1)/2)，檢索一個(gè)key，其查找節(jié)點(diǎn)個(gè)數(shù)的漸進(jìn)復(fù)雜度為O(logdN)。從這點(diǎn)可以看出，B-Tree是一個(gè)非常有效率的索引數(shù)據(jù)結(jié)構(gòu)。

另外，由于插入刪除新的數(shù)據(jù)記錄會(huì)破壞B-Tree的性質(zhì)，因此在插入刪除時(shí)，需要對(duì)樹(shù)進(jìn)行一個(gè)分裂、合并、轉(zhuǎn)移等操作以保持B-Tree性質(zhì)，本文不打算完整討論B-Tree這些內(nèi)容，因?yàn)橐呀?jīng)有許多資料詳細(xì)說(shuō)明了B-Tree的數(shù)學(xué)性質(zhì)及插入刪除算法，有興趣的朋友可以查閱其它文獻(xiàn)進(jìn)行詳細(xì)研究。

B+Tree

其實(shí)B-Tree有許多變種，其中最常見(jiàn)的是B+Tree，比如MySQL就普遍使用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。B-Tree相比，B+Tree有以下不同點(diǎn)：

• 每個(gè)節(jié)點(diǎn)的指針上限為2d而不是2d+1；
• 內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key；
• 葉子節(jié)點(diǎn)不存儲(chǔ)指針；

下面是一個(gè)簡(jiǎn)單的B+Tree示意

image

由于并不是所有節(jié)點(diǎn)都具有相同的域，因此B+Tree中葉節(jié)點(diǎn)和內(nèi)節(jié)點(diǎn)一般大小不同。這點(diǎn)與B-Tree不同，雖然B-Tree中不同節(jié)點(diǎn)存放的key和指針可能數(shù)量不一致，但是每個(gè)節(jié)點(diǎn)的域和上限是一致的，所以在實(shí)現(xiàn)中B-Tree往往對(duì)每個(gè)節(jié)點(diǎn)申請(qǐng)同等大小的空間。一般來(lái)說(shuō)，B+Tree比B-Tree更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)，具體原因與外存儲(chǔ)器原理及計(jì)算機(jī)存取原理有關(guān)，將在下面討論。

帶有順序訪問(wèn)指針的B+Tree

一般在數(shù)據(jù)庫(kù)系統(tǒng)或文件系統(tǒng)中使用的B+Tree結(jié)構(gòu)都在經(jīng)典B+Tree的基礎(chǔ)上進(jìn)行了優(yōu)化，增加了順序訪問(wèn)指針。

image

如圖所示，在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，就形成了帶有順序訪問(wèn)指針的B+Tree。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問(wèn)的性能，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率。

這一節(jié)對(duì)B-Tree和B+Tree進(jìn)行了一個(gè)簡(jiǎn)單的介紹，下一節(jié)結(jié)合存儲(chǔ)器存取原理介紹為什么目前B+Tree是數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)索引的首選數(shù)據(jù)結(jié)構(gòu)。

索引數(shù)據(jù)結(jié)構(gòu)設(shè)相關(guān)的計(jì)算機(jī)原理

上文說(shuō)過(guò)，二叉樹(shù)、紅黑樹(shù)等數(shù)據(jù)結(jié)構(gòu)也可以用來(lái)實(shí)現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)普遍采用B-/+Tree作為索引結(jié)構(gòu)，這一節(jié)將結(jié)合計(jì)算機(jī)組成原理相關(guān)知識(shí)討論B-/+Tree作為索引的理論基礎(chǔ)。

兩種類型的存儲(chǔ)

在計(jì)算機(jī)系統(tǒng)中一般包含兩種類型的存儲(chǔ)，計(jì)算機(jī)主存（RAM）和外部存儲(chǔ)器（如硬盤、CD、SSD等）。在設(shè)計(jì)索引算法和存儲(chǔ)結(jié)構(gòu)時(shí)，我們必須要考慮到這兩種類型的存儲(chǔ)特點(diǎn)。主存的讀取速度快，相對(duì)于主存，外部磁盤的數(shù)據(jù)讀取速率要比主從慢好幾個(gè)數(shù)量級(jí)，具體它們之間的差別后面會(huì)詳細(xì)介紹。 上面講的所有查詢算法都是假設(shè)數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)主存中的，計(jì)算機(jī)主存一般比較小，實(shí)際數(shù)據(jù)庫(kù)中數(shù)據(jù)都是存儲(chǔ)到外部存儲(chǔ)器的。

一般來(lái)說(shuō)，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤上。這樣的話，索引查找過(guò)程中就要產(chǎn)生磁盤I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說(shuō)，索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤I/O的存取次數(shù)。下面詳細(xì)介紹內(nèi)存和磁盤存取原理，然后再結(jié)合這些原理分析B-/+Tree作為索引的效率。

存存取原理

目前計(jì)算機(jī)使用的主存基本都是隨機(jī)讀寫存儲(chǔ)器（RAM），現(xiàn)代RAM的結(jié)構(gòu)和存取原理比較復(fù)雜，這里本文拋卻具體差別，抽象出一個(gè)十分簡(jiǎn)單的存取模型來(lái)說(shuō)明RAM的工作原理。

image

從抽象角度看，主存是一系列的存儲(chǔ)單元組成的矩陣，每個(gè)存儲(chǔ)單元存儲(chǔ)固定大小的數(shù)據(jù)。每個(gè)存儲(chǔ)單元有唯一的地址，現(xiàn)代主存的編址規(guī)則比較復(fù)雜，這里將其簡(jiǎn)化成一個(gè)二維地址：通過(guò)一個(gè)行地址和一個(gè)列地址可以唯一定位到一個(gè)存儲(chǔ)單元。上圖展示了一個(gè)4 x 4的主存模型。

主存的存取過(guò)程如下：

當(dāng)系統(tǒng)需要讀取主存時(shí)，則將地址信號(hào)放到地址總線上傳給主存，主存讀到地址信號(hào)后，解析信號(hào)并定位到指定存儲(chǔ)單元，然后將此存儲(chǔ)單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取。寫主存的過(guò)程類似，系統(tǒng)將要寫入單元地址和數(shù)據(jù)分別放在地址總線和數(shù)據(jù)總線上，主存讀取兩個(gè)總線的內(nèi)容，做相應(yīng)的寫操作。

這里可以看出，主存存取的時(shí)間僅與存取次數(shù)呈線性關(guān)系，因?yàn)椴淮嬖跈C(jī)械操作，兩次存取的數(shù)據(jù)的“距離”不會(huì)對(duì)時(shí)間有任何影響，例如，先取A0再取A1和先取A0再取D3的時(shí)間消耗是一樣的。

磁盤存取原理

上文說(shuō)過(guò)，索引一般以文件形式存儲(chǔ)在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機(jī)械運(yùn)動(dòng)耗費(fèi)，因此磁盤I/O的時(shí)間消耗是巨大的。

磁盤讀取數(shù)據(jù)靠的是機(jī)械運(yùn)動(dòng)，當(dāng)需要從磁盤讀取數(shù)據(jù)時(shí)，系統(tǒng)會(huì)將數(shù)據(jù)邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個(gè)磁道，哪個(gè)扇區(qū)。為了讀取這個(gè)扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個(gè)扇區(qū)上方，為了實(shí)現(xiàn)這一點(diǎn)，磁頭需要移動(dòng)對(duì)準(zhǔn)相應(yīng)磁道，這個(gè)過(guò)程叫做尋道，所耗費(fèi)時(shí)間叫做尋道時(shí)間，然后磁盤旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過(guò)程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間，最后便是對(duì)讀取數(shù)據(jù)的傳輸。 所以每次讀取數(shù)據(jù)花費(fèi)的時(shí)間可以分為尋道時(shí)間、旋轉(zhuǎn)延遲、傳輸時(shí)間三個(gè)部分。其中：

• 尋道時(shí)間是磁臂移動(dòng)到指定磁道所需要的時(shí)間，主流磁盤一般在5ms以下。
• 旋轉(zhuǎn)延遲就是我們經(jīng)常聽(tīng)說(shuō)的磁盤轉(zhuǎn)速，比如一個(gè)磁盤7200轉(zhuǎn)，表示每分鐘能轉(zhuǎn)7200次，也就是說(shuō)1秒鐘能轉(zhuǎn)120次，旋轉(zhuǎn)延遲就是1/120/2 = 4.17ms。
• 傳輸時(shí)間指的是從磁盤讀出或?qū)?shù)據(jù)寫入磁盤的時(shí)間，一般在零點(diǎn)幾毫秒，相對(duì)于前兩個(gè)時(shí)間可以忽略不計(jì)。

那么訪問(wèn)一次磁盤的時(shí)間，即一次磁盤IO的時(shí)間約等于5+4.17 = 9ms左右，聽(tīng)起來(lái)還挺不錯(cuò)的，但要知道一臺(tái)500 -MIPS的機(jī)器每秒可以執(zhí)行5億條指令，因?yàn)橹噶钜揽康氖请姷男再|(zhì)，換句話說(shuō)執(zhí)行一次IO的時(shí)間可以執(zhí)行40萬(wàn)條指令，數(shù)據(jù)庫(kù)動(dòng)輒十萬(wàn)百萬(wàn)乃至千萬(wàn)級(jí)數(shù)據(jù)，每次9毫秒的時(shí)間，顯然是個(gè)災(zāi)難。

局部性原理與磁盤預(yù)讀

由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。

由于磁盤順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高I/O效率。預(yù)讀的長(zhǎng)度一般為頁(yè)（page）的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)（在許多操作系統(tǒng)中，頁(yè)得大小通常為4k），主存和磁盤以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號(hào)，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。

數(shù)據(jù)庫(kù)索引所采用的數(shù)據(jù)結(jié)構(gòu)B-/+Tree及其性能分析

到這里終于可以分析為何數(shù)據(jù)庫(kù)索引采用B-/+Tree存儲(chǔ)結(jié)構(gòu)了。上文說(shuō)過(guò)數(shù)據(jù)庫(kù)索引是存儲(chǔ)到磁盤的而我們又一般以使用磁盤I/O次數(shù)來(lái)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣。先從B-Tree分析，根據(jù)B-Tree的定義，可知檢索一次最多需要訪問(wèn)h-1個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)常駐內(nèi)存）。數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B-Tree還需要使用如下技巧：每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過(guò)100，因此h非常?。ㄍǔ２怀^(guò)3）。

綜上所述，如果我們采用B-Tree存儲(chǔ)結(jié)構(gòu)，搜索時(shí)I/O次數(shù)一般不會(huì)超過(guò)3次，所以用B-Tree作為索引結(jié)構(gòu)效率是非常高的。

B+樹(shù)性能分析

從上面介紹我們知道，B樹(shù)的搜索復(fù)雜度為O(h)=O(logdN)，所以樹(shù)的出度d越大，深度h就越小，I/O的次數(shù)就越少。B+Tree恰恰可以增加出度d的寬度，因?yàn)槊總€(gè)節(jié)點(diǎn)大小為一個(gè)頁(yè)大小，所以出度的上限取決于節(jié)點(diǎn)內(nèi)key和data的大?。?/p>

dmax=floor(pagesize/(keysize+datasize+pointsize))//floor表示向下取整

由于B+Tree內(nèi)節(jié)點(diǎn)去掉了data域，因此可以擁有更大的出度，從而擁有更好的性能。

B+樹(shù)查找過(guò)程

image

B-樹(shù)和B+樹(shù)查找過(guò)程基本一致。如上圖所示，如果要查找數(shù)據(jù)項(xiàng)29，那么首先會(huì)把磁盤塊1由磁盤加載到內(nèi)存，此時(shí)發(fā)生一次IO，在內(nèi)存中用二分查找確定29在17和35之間，鎖定磁盤塊1的P2指針，內(nèi)存時(shí)間因?yàn)榉浅６蹋ㄏ啾却疟P的IO）可以忽略不計(jì)，通過(guò)磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內(nèi)存，發(fā)生第二次IO，29在26和30之間，鎖定磁盤塊3的P2指針，通過(guò)指針加載磁盤塊8到內(nèi)存，發(fā)生第三次IO，同時(shí)內(nèi)存中做二分查找找到29，結(jié)束查詢，總計(jì)三次IO。真實(shí)的情況是，3層的b+樹(shù)可以表示上百萬(wàn)的數(shù)據(jù)，如果上百萬(wàn)的數(shù)據(jù)查找只需要三次IO，性能提高將是巨大的，如果沒(méi)有索引，每個(gè)數(shù)據(jù)項(xiàng)都要發(fā)生一次IO，那么總共需要百萬(wàn)次的IO，顯然成本非常非常高。

這一章從理論角度討論了與索引相關(guān)的數(shù)據(jù)結(jié)構(gòu)與算法問(wèn)題，下一章將討論B+Tree是如何具體實(shí)現(xiàn)為MySQL中索引，同時(shí)將結(jié)合MyISAM和InnDB存儲(chǔ)引擎介紹非聚集索引和聚集索引兩種不同的索引實(shí)現(xiàn)形式。

MySQL索引實(shí)現(xiàn)

在MySQL中，索引屬于存儲(chǔ)引擎級(jí)別的概念，不同存儲(chǔ)引擎對(duì)索引的實(shí)現(xiàn)方式是不同的，本文主要討論MyISAM和InnoDB兩個(gè)存儲(chǔ)引擎的索引實(shí)現(xiàn)方式。

MyISAM索引實(shí)現(xiàn)

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM索引的原理圖：

image

這里設(shè)表一共有三列，假設(shè)我們以Col1為主鍵，則上圖是一個(gè)MyISAM表的主索引（Primary key）示意?？梢钥闯鯩yISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。在MyISAM中，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒(méi)有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)。如果我們?cè)贑ol2上建立一個(gè)輔助索引，則此索引的結(jié)構(gòu)如下圖所示：

image

同樣也是一顆B+Tree，data域保存數(shù)據(jù)記錄的地址。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。
MyISAM的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分。

InnoDB索引實(shí)現(xiàn)

雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同。

第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹(shù)的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

image

上圖是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒(méi)有），如果沒(méi)有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類型為長(zhǎng)整形。

第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。換句話說(shuō)，InnoDB的所有輔助索引都引用主鍵作為data域。例如，下圖為定義在Col3上的一個(gè)輔助索引：

image

這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。

了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助，例如知道了InnoDB的索引實(shí)現(xiàn)后，就很容易明白為什么不建議使用過(guò)長(zhǎng)的字段作為主鍵，因?yàn)樗休o助索引都引用主索引，過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大。再例如，用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵則是一個(gè)很好的選擇。

下一章將具體討論這些與索引有關(guān)的優(yōu)化策略。

索引使用策略及優(yōu)化

MySQL的優(yōu)化主要分為結(jié)構(gòu)優(yōu)化（Scheme optimization）和查詢優(yōu)化（Query optimization）。本章討論的高性能索引策略主要屬于結(jié)構(gòu)優(yōu)化范疇。本章的內(nèi)容完全基于上文的理論基礎(chǔ)，實(shí)際上一旦理解了索引背后的機(jī)制，那么選擇高性能的策略就變成了純粹的推理，并且可以理解這些策略背后的邏輯。

聯(lián)合索引及最左前綴原理

聯(lián)合索引（復(fù)合索引）

首先介紹一下聯(lián)合索引。聯(lián)合索引其實(shí)很簡(jiǎn)單，相對(duì)于一般索引只有一個(gè)字段，聯(lián)合索引可以為多個(gè)字段創(chuàng)建一個(gè)索引。它的原理也很簡(jiǎn)單，比如，我們?cè)冢╝,b,c）字段上創(chuàng)建一個(gè)聯(lián)合索引，則索引記錄會(huì)首先按照A字段排序，然后再按照B字段排序然后再是C字段，因此，聯(lián)合索引的特點(diǎn)就是：

• 第一個(gè)字段一定是有序的
• 當(dāng)?shù)谝粋€(gè)字段值相等的時(shí)候，第二個(gè)字段又是有序的，比如下表中當(dāng)A=2時(shí)所有B的值是有序排列的，依次類推，當(dāng)同一個(gè)B值得所有C字段是有序排列的

| A | B | C | 
| 1 | 2 | 3 | 
| 1 | 4 | 2 | 
| 1 | 1 | 4 | 
| 2 | 3 | 5 | 
| 2 | 4 | 4 | 
| 2 | 4 | 6 | 
| 2 | 5 | 5 |

其實(shí)聯(lián)合索引的查找就跟查字典是一樣的，先根據(jù)第一個(gè)字母查，然后再根據(jù)第二個(gè)字母查，或者只根據(jù)第一個(gè)字母查，但是不能跳過(guò)第一個(gè)字母從第二個(gè)字母開(kāi)始查。這就是所謂的最左前綴原理。

最左前綴原理

我們?cè)賮?lái)詳細(xì)介紹一下聯(lián)合索引的查詢。還是上面例子，我們?cè)冢╝,b,c）字段上建了一個(gè)聯(lián)合索引，所以這個(gè)索引是先按a 再按b 再按c進(jìn)行排列的，所以：

以下的查詢方式都可以用到索引

select * from table where a=1；
select * from table where a=1 and b=2；
select * from table where a=1 and b=2 and c=3；

上面三個(gè)查詢按照 （a ）, （a，b ）,（a，b，c ）的順序都可以利用到索引，這就是最左前綴匹配。

如果查詢語(yǔ)句是：

select * from table where a=1 and c=3； 那么只會(huì)用到索引a。

如果查詢語(yǔ)句是：

select * from table where b=2 and c=3； 因?yàn)闆](méi)有用到最左前綴a，所以這個(gè)查詢是用戶到索引的。

如果用到了最左前綴，但是順序顛倒會(huì)用到索引碼？

select * from table where b=2 and a=1；
select * from table where b=2 and a=1 and c=3；

如果用到了最左前綴而只是顛倒了順序，也是可以用到索引的，因?yàn)閙ysql查詢優(yōu)化器會(huì)判斷糾正這條sql語(yǔ)句該以什么樣的順序執(zhí)行效率最高，最后才生成真正的執(zhí)行計(jì)劃。但我們還是最好按照索引順序來(lái)查詢，這樣查詢優(yōu)化器就不用重新編譯了。

前綴索引

除了聯(lián)合索引之外，對(duì)mysql來(lái)說(shuō)其實(shí)還有一種前綴索引。前綴索引就是用列的前綴代替整個(gè)列作為索引key，當(dāng)前綴長(zhǎng)度合適時(shí)，可以做到既使得前綴索引的選擇性接近全列索引，同時(shí)因?yàn)樗饕齥ey變短而減少了索引文件的大小和維護(hù)開(kāi)銷。

一般來(lái)說(shuō)以下情況可以使用前綴索引：

• 字符串列(varchar,char,text等)，需要進(jìn)行全字段匹配或者前匹配。也就是=‘xxx’ 或者 like ‘xxx%’
• 字符串本身可能比較長(zhǎng)，而且前幾個(gè)字符就開(kāi)始不相同。比如我們對(duì)中國(guó)人的姓名使用前綴索引就沒(méi)啥意義，因?yàn)橹袊?guó)人名字都很短，另外對(duì)收件地址使用前綴索引也不是很實(shí)用，因?yàn)橐环矫媸占刂芬话愣际且訶X省開(kāi)頭，也就是說(shuō)前幾個(gè)字符都是差不多的，而且收件地址進(jìn)行檢索一般都是like ’%xxx%’，不會(huì)用到前匹配。相反對(duì)外國(guó)人的姓名可以使用前綴索引，因?yàn)槠渥址^長(zhǎng)，而且前幾個(gè)字符的選擇性比較高。同樣電子郵件也是一個(gè)可以使用前綴索引的字段。
• 前一半字符的索引選擇性就已經(jīng)接近于全字段的索引選擇性。如果整個(gè)字段的長(zhǎng)度為20，索引選擇性為0.9，而我們對(duì)前10個(gè)字符建立前綴索引其選擇性也只有0.5，那么我們需要繼續(xù)加大前綴字符的長(zhǎng)度，但是這個(gè)時(shí)候前綴索引的優(yōu)勢(shì)已經(jīng)不明顯，沒(méi)有太大的建前綴索引的必要了。

一些文章中也提到：

MySQL 前綴索引能有效減小索引文件的大小，提高索引的速度。但是前綴索引也有它的壞處：MySQL 不能在 ORDER BY 或 GROUP BY 中使用前綴索引，也不能把它們用作覆蓋索引(Covering Index)。

索引優(yōu)化策略

• 最左前綴匹配原則，上面講到了
• 主鍵外檢一定要建索引
• 對(duì) where,on,group by,order by 中出現(xiàn)的列使用索引
• 盡量選擇區(qū)分度高的列作為索引,區(qū)分度的公式是count(distinct col)/count(*)，表示字段不重復(fù)的比例，比例越大我們掃描的記錄數(shù)越少，唯一鍵的區(qū)分度是1，而一些狀態(tài)、性別字段可能在大數(shù)據(jù)面前區(qū)分度就是0
• 對(duì)較小的數(shù)據(jù)列使用索引,這樣會(huì)使索引文件更小,同時(shí)內(nèi)存中也可以裝載更多的索引鍵
• 索引列不能參與計(jì)算，保持列“干凈”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很簡(jiǎn)單，b+樹(shù)中存的都是數(shù)據(jù)表中的字段值，但進(jìn)行檢索時(shí)，需要把所有元素都應(yīng)用函數(shù)才能比較，顯然成本太大。所以語(yǔ)句應(yīng)該寫成create_time = unix_timestamp(’2014-05-29’);
• 為較長(zhǎng)的字符串使用前綴索引
• 盡量的擴(kuò)展索引，不要新建索引。比如表中已經(jīng)有a的索引，現(xiàn)在要加(a,b)的索引，那么只需要修改原來(lái)的索引即可
• 不要過(guò)多創(chuàng)建索引, 權(quán)衡索引個(gè)數(shù)與DML之間關(guān)系，DML也就是插入、刪除數(shù)據(jù)操作。這里需要權(quán)衡一個(gè)問(wèn)題，建立索引的目的是為了提高查詢效率的，但建立的索引過(guò)多，會(huì)影響插入、刪除數(shù)據(jù)的速度，因?yàn)槲覀冃薷牡谋頂?shù)據(jù)，索引也需要進(jìn)行調(diào)整重建
• 對(duì)于like查詢，”%”不要放在前面。

SELECT * FROMhoudunwangWHEREunameLIKE'后盾%' -- 走索引 
SELECT * FROMhoudunwangWHEREunameLIKE "%后盾%" -- 不走索引

• 查詢where條件數(shù)據(jù)類型不匹配也無(wú)法使用索引

字符串與數(shù)字比較不使用索引;

CREATE TABLEa(achar(10)); 
EXPLAIN SELECT * FROMaWHEREa="1" – 走索引 
EXPLAIN SELECT * FROM a WHERE a=1 – 不走索引 

• 正則表達(dá)式不使用索引,這應(yīng)該很好理解,所以為什么在SQL中很難看到regexp關(guān)鍵字的原因

原文鏈接

https://blog.csdn.net/suifeng3051/article/details/52669644