摘要

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

為什么這里要講查詢算法和數(shù)據(jù)結(jié)構(gòu)呢？因為之所以要建立索引,，其實就是為了構(gòu)建一種數(shù)據(jù)結(jié)構(gòu),，可以在上面應(yīng)用一種高效的查詢算法，最終提高數(shù)據(jù)的查詢速度,。

索引的本質(zhì)

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

常見的查詢算法

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

順序查找（linear search ）

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

• 數(shù)據(jù)結(jié)構(gòu)：有序或無序隊列

• 復(fù)雜度：O(n)

二分查找（binary search）

比順序查找更快的查詢方法應(yīng)該就是二分查找了,，二分查找的原理是查找過程從數(shù)組的中間元素開始,，如果中間元素正好是要查找的元素，則搜素過程結(jié)束,；如果某一特定元素大于或者小于中間元素,，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較,。如果在某一步驟數(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);
}

二叉排序樹查找

二叉排序樹的特點是：

• 若它的左子樹不空,，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

• 若它的右子樹不空,，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值,；

• 它的左、右子樹也分別為二叉排序樹,。

搜索的原理：

• 若b是空樹,，則搜索失敗,，否則：

• 若x等于b的根節(jié)點的數(shù)據(jù)域之值，則查找成功,；否則：

• 若x小于b的根節(jié)點的數(shù)據(jù)域之值,，則搜索左子樹；否則：查找右子樹

• 數(shù)據(jù)結(jié)構(gòu)：二叉排序樹

• 時間復(fù)雜度： O(log2N)

哈希散列法(哈希表)

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

• 數(shù)據(jù)結(jié)構(gòu)：哈希表

• 時間復(fù)雜度：幾乎是O(1),，取決于產(chǎn)生沖突的多少。

分塊查找

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

• 先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表；

• 查找分兩個部分：先對索引表進行二分查找或順序查找,，以確定待查記錄在哪一塊中,；然后，在已確定的塊中用順序法進行查找,。

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

平衡多路搜索樹B樹（B-tree）

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

B Tree

B樹（Balance Tree）又叫做B- 樹（其實B-是由B-tree翻譯過來，所以B-樹和B樹是一個概念） ,，它就是一種平衡路查找樹。下圖就是一個典型的B樹：

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

• 有一個根節(jié)點,，根節(jié)點只有一個記錄和兩個孩子或者根節(jié)點為空,；

• 每個節(jié)點記錄中的key和指針相互間隔，指針指向孩子節(jié)點,；

• d是表示樹的寬度,，除葉子節(jié)點之外，其它每個節(jié)點有[d/2,d-1]條記錄,，并且些記錄中的key都是從左到右按大小排列的,，有[d/2+1,d]個孩子；

• 在一個節(jié)點中,，第n個子樹中的所有key,，小于這個節(jié)點中第n個key，大于第n-1個key,，比如上圖中B節(jié)點的第2個子節(jié)點E中的所有key都小于B中的第2個key 9,，大于第1個key 3;

• 所有的葉子節(jié)點必須在同一層次,，也就是它們具有相同的深度,；

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

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

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

B+Tree

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

• 每個節(jié)點的指針上限為2d而不是2d+1,；

• 內(nèi)節(jié)點不存儲data，只存儲key,；

• 葉子節(jié)點不存儲指針,；

下面是一個簡單的B+Tree示意

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

帶有順序訪問指針的B+Tree

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

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

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

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

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

兩種類型的存儲

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

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

存存取原理

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

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

主存的存取過程如下：

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

這里可以看出,，主存存取的時間僅與存取次數(shù)呈線性關(guān)系,，因為不存在機械操作，兩次存取的數(shù)據(jù)的“距離”不會對時間有任何影響,，例如,，先取A0再取A1和先取A0再取D3的時間消耗是一樣的。

磁盤存取原理

上文說過,，索引一般以文件形式存儲在磁盤上,，索引檢索需要磁盤I/O操作。與主存不同,，磁盤I/O存在機械運動耗費,，因此磁盤I/O的時間消耗是巨大的。

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

• 尋道時間是磁臂移動到指定磁道所需要的時間，主流磁盤一般在5ms以下,。

• 旋轉(zhuǎn)延遲就是我們經(jīng)常聽說的磁盤轉(zhuǎn)速,，比如一個磁盤7200轉(zhuǎn)，表示每分鐘能轉(zhuǎn)7200次,，也就是說1秒鐘能轉(zhuǎn)120次,，旋轉(zhuǎn)延遲就是1/120/2 = 4.17ms。

• 傳輸時間指的是從磁盤讀出或?qū)?shù)據(jù)寫入磁盤的時間,，一般在零點幾毫秒,，相對于前兩個時間可以忽略不計。

那么訪問一次磁盤的時間,，即一次磁盤IO的時間約等于5+4.17 = 9ms左右，聽起來還挺不錯的,，但要知道一臺500 -MIPS的機器每秒可以執(zhí)行5億條指令,，因為指令依靠的是電的性質(zhì)，換句話說執(zhí)行一次IO的時間可以執(zhí)行40萬條指令,，數(shù)據(jù)庫動輒十萬百萬乃至千萬級數(shù)據(jù),，每次9毫秒的時間，顯然是個災(zāi)難,。

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

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

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

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

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

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

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

B+樹性能分析

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

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

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

B+樹查找過程

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

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

MySQL索引實現(xiàn)

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

MyISAM索引實現(xiàn)

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

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

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

InnoDB索引實現(xiàn)

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

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

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

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

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

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

下一章將具體討論這些與索引有關(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ǔ),，實際上一旦理解了索引背后的機制，那么選擇高性能的策略就變成了純粹的推理,，并且可以理解這些策略背后的邏輯,。

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

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

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

• 第一個字段一定是有序的

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

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

最左前綴原理

我們再來詳細介紹一下聯(lián)合索引的查詢,。還是上面例子，我們在（a,b,c）字段上建了一個聯(lián)合索引,，所以這個索引是先按a 再按b 再按c進行排列的,，所以：

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

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,；

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

如果查詢語句是：

如果查詢語句是：

select * from table where b=2 and c=3； 因為沒有用到最左前綴a,，所以這個查詢是用戶到索引的,。

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

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

前綴索引

除了聯(lián)合索引之外,，對mysql來說其實還有一種前綴索引,。前綴索引就是用列的前綴代替整個列作為索引key，當前綴長度合適時,，可以做到既使得前綴索引的選擇性接近全列索引,，同時因為索引key變短而減少了索引文件的大小和維護開銷。

一般來說以下情況可以使用前綴索引：

• 字符串列(varchar,char,text等),，需要進行全字段匹配或者前匹配,。也就是=‘xxx’ 或者 like ‘xxx%’

• 字符串本身可能比較長，而且前幾個字符就開始不相同,。比如我們對中國人的姓名使用前綴索引就沒啥意義,，因為中國人名字都很短，另外對收件地址使用前綴索引也不是很實用,，因為一方面收件地址一般都是以XX省開頭,，也就是說前幾個字符都是差不多的，而且收件地址進行檢索一般都是like ’%xxx%’,，不會用到前匹配,。相反對外國人的姓名可以使用前綴索引，因為其字符較長,，而且前幾個字符的選擇性比較高,。同樣電子郵件也是一個可以使用前綴索引的字段。

• 前一半字符的索引選擇性就已經(jīng)接近于全字段的索引選擇性,。如果整個字段的長度為20,，索引選擇性為0.9，而我們對前10個字符建立前綴索引其選擇性也只有0.5，那么我們需要繼續(xù)加大前綴字符的長度,，但是這個時候前綴索引的優(yōu)勢已經(jīng)不明顯,，沒有太大的建前綴索引的必要了。

一些文章中也提到：

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

索引優(yōu)化策略

• 最左前綴匹配原則，上面講到了

• 主鍵外檢一定要建索引

• 對 where,on,group by,order by 中出現(xiàn)的列使用索引

• 盡量選擇區(qū)分度高的列作為索引,區(qū)分度的公式是count(distinct col)/count(*),，表示字段不重復(fù)的比例,，比例越大我們掃描的記錄數(shù)越少，唯一鍵的區(qū)分度是1,，而一些狀態(tài),、性別字段可能在大數(shù)據(jù)面前區(qū)分度就是0

• 對較小的數(shù)據(jù)列使用索引,這樣會使索引文件更小,同時內(nèi)存中也可以裝載更多的索引鍵

• 索引列不能參與計算，保持列“干凈”,，比如fromunixtime(createtime) = ’2014-05-29’就不能使用到索引,，原因很簡單，b+樹中存的都是數(shù)據(jù)表中的字段值,，但進行檢索時,，需要把所有元素都應(yīng)用函數(shù)才能比較，顯然成本太大,。所以語句應(yīng)該寫成createtime = unixtimestamp(’2014-05-29’);

• 為較長的字符串使用前綴索引

• 盡量的擴展索引,，不要新建索引。比如表中已經(jīng)有a的索引,，現(xiàn)在要加(a,b)的索引,，那么只需要修改原來的索引即可

• 不要過多創(chuàng)建索引, 權(quán)衡索引個數(shù)與DML之間關(guān)系，DML也就是插入,、刪除數(shù)據(jù)操作,。這里需要權(quán)衡一個問題，建立索引的目的是為了提高查詢效率的,，但建立的索引過多,，會影響插入、刪除數(shù)據(jù)的速度,，因為我們修改的表數(shù)據(jù),，索引也需要進行調(diào)整重建

• 對于like查詢，”%”不要放在前面,。

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

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

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

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