摘要

本文以MySQL數據庫為研究對象黍瞧，討論與數據庫索引相關的一些話題诸尽。特別需要說明的是，MySQL支持諸多存儲引擎印颤，而各種存儲引擎對索引的支持也各不相同您机，因此MySQL數據庫支持多種索引類型，如BTree索引年局，哈希索引际看，全文索引等等。為了避免混亂矢否，本文將只關注于BTree索引仲闽，因為這是平常使用MySQL時主要打交道的索引，至于哈希索引和全文索引本文暫不討論僵朗。

文章主要內容分為三個部分：

第一部分主要從數據結構及算法理論層面討論MySQL數據庫索引的數理基礎赖欣。

第二部分結合MySQL數據庫中MyISAM和InnoDB數據存儲引擎中索引的架構實現討論聚集索引、非聚集索引及覆蓋索引等話題验庙。

第三部分根據上面的理論基礎顶吮，討論MySQL中高性能使用索引的策略。

數據結構及算法基礎

索引的本質

MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數據的數據結構粪薛。提取句子主干悴了，就可以得到索引的本質：索引是數據結構。

我們知道违寿，數據庫查詢是數據庫的最主要功能之一让禀。我們都希望查詢數據的速度能盡可能的快，因此數據庫系統(tǒng)的設計者會從查詢算法的角度進行優(yōu)化陨界。最基本的查詢算法當然是順序查找（linear search）巡揍，這種復雜度為O(n)的算法在數據量很大時顯然是糟糕的，好在計算機科學的發(fā)展提供了很多更優(yōu)秀的查找算法菌瘪，例如二分查找（binary search）腮敌、二叉樹查找（binary tree search）等。如果稍微分析一下會發(fā)現俏扩，每種查找算法都只能應用于特定的數據結構之上糜工，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用于二叉查找樹上录淡，但是數據本身的組織結構不可能完全滿足各種數據結構（例如捌木，理論上不可能同時將兩列都按順序進行組織），所以嫉戚，在數據之外刨裆，數據庫系統(tǒng)還維護著滿足特定查找算法的數據結構澈圈，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找算法帆啃。這種數據結構瞬女，就是索引。

看一個例子：

圖1

圖1展示了一種可能的索引方式努潘。左邊是數據表诽偷，一共有兩列七條記錄，最左邊的是數據記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）疯坤。為了加快Col2的查找报慕，可以維護一個右邊所示的二叉查找樹，每個節(jié)點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針压怠，這樣就可以運用二叉查找在O(log2n)O(log2n)的復雜度內獲取到相應數據卖子。

雖然這是一個貨真價實的索引，但是實際的數據庫系統(tǒng)幾乎沒有使用二叉查找樹或其進化品種紅黑樹（red-black tree）實現的刑峡，原因會在下文介紹洋闽。

B-Tree和B+Tree

目前大部分數據庫系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結構，在本文的下一節(jié)會結合存儲器原理及計算機存取原理討論為什么B-Tree和B+Tree在被如此廣泛用于索引突梦，這一節(jié)先單純從數據結構角度描述它們诫舅。

B-Tree

為了描述B-Tree，首先定義一條數據記錄為一個二元組[key, data]宫患，key為記錄的鍵值刊懈，對于不同數據記錄，key是互不相同的娃闲；data為數據記錄除key外的數據虚汛。那么B-Tree是滿足下列條件的數據結構：

d為大于1的一個正整數，稱為B-Tree的度皇帮。

h為一個正整數卷哩，稱為B-Tree的高度。

每個非葉子節(jié)點由n-1個key和n個指針組成属拾，其中d<=n<=2d将谊。

每個葉子節(jié)點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針渐白，葉節(jié)點的指針均為null 尊浓。

所有葉節(jié)點具有相同的深度，等于樹高h纯衍。

key和指針互相間隔栋齿，節(jié)點兩端是指針。

一個節(jié)點中的key從左到右非遞減排列。

所有節(jié)點組成樹結構瓦堵。

每個指針要么為null基协，要么指向另外一個節(jié)點。

如果某個指針在節(jié)點node最左邊且不為null谷丸，則其指向節(jié)點的所有key小于v(key1)v(key1)堡掏，其中v(key1)v(key1)為node的第一個key的值应结。

如果某個指針在節(jié)點node最右邊且不為null刨疼，則其指向節(jié)點的所有key大于v(keym)v(keym)，其中v(keym)v(keym)為node的最后一個key的值鹅龄。

如果某個指針在節(jié)點node的左右相鄰key分別是keyikeyi和keyi+1keyi+1且不為null揩慕，則其指向節(jié)點的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)。

圖2是一個d=2的B-Tree示意圖扮休。

圖2

由于B-Tree的特性迎卤，在B-Tree中按key檢索數據的算法非常直觀：首先從根節(jié)點進行二分查找，如果找到則返回對應節(jié)點的data玷坠，否則對相應區(qū)間的指針指向的節(jié)點遞歸進行查找蜗搔，直到找到節(jié)點或找到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);

關于B-Tree有一系列有趣的性質，例如一個度為d的B-Tree兄渺，設其索引N個key缝龄，則其樹高h的上限為logd((N+1)/2)logd((N+1)/2)，檢索一個key挂谍，其查找節(jié)點個數的漸進復雜度為O(logdN)O(logdN)叔壤。從這點可以看出，B-Tree是一個非常有效率的索引數據結構口叙。

另外炼绘，由于插入刪除新的數據記錄會破壞B-Tree的性質，因此在插入刪除時妄田，需要對樹進行一個分裂饭望、合并、轉移等操作以保持B-Tree性質形庭，本文不打算完整討論B-Tree這些內容铅辞，因為已經有許多資料詳細說明了B-Tree的數學性質及插入刪除算法，有興趣的朋友可以在本文末的參考文獻一欄找到相應的資料進行閱讀萨醒。

B+Tree

B-Tree有許多變種斟珊，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實現其索引結構。

與B-Tree相比囤踩，B+Tree有以下不同點：

每個節(jié)點的指針上限為2d而不是2d+1旨椒。

內節(jié)點不存儲data，只存儲key堵漱；葉子節(jié)點不存儲指針综慎。

圖3是一個簡單的B+Tree示意。

圖3

由于并不是所有節(jié)點都具有相同的域勤庐，因此B+Tree中葉節(jié)點和內節(jié)點一般大小不同示惊。這點與B-Tree不同，雖然B-Tree中不同節(jié)點存放的key和指針可能數量不一致愉镰，但是每個節(jié)點的域和上限是一致的米罚，所以在實現中B-Tree往往對每個節(jié)點申請同等大小的空間。

一般來說丈探，B+Tree比B-Tree更適合實現外存儲索引結構录择，具體原因與外存儲器原理及計算機存取原理有關，將在下面討論碗降。

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

一般在數據庫系統(tǒng)或文件系統(tǒng)中使用的B+Tree結構都在經典B+Tree的基礎上進行了優(yōu)化隘竭，增加了順序訪問指針。

圖4

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

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

為什么使用B-Tree（B+Tree）

上文說過拯田，紅黑樹等數據結構也可以用來實現索引，但是文件系統(tǒng)及數據庫系統(tǒng)普遍采用B-/+Tree作為索引結構甩十，這一節(jié)將結合計算機組成原理相關知識討論B-/+Tree作為索引的理論基礎船庇。

一般來說，索引本身也很大侣监，不可能全部存儲在內存中鸭轮，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話橄霉，索引查找過程中就要產生磁盤I/O消耗窃爷，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優(yōu)劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度按厘。換句話說医吊，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。下面先介紹內存和磁盤存取原理逮京，然后再結合這些原理分析B-/+Tree作為索引的效率卿堂。

主存存取原理

目前計算機使用的主存基本都是隨機讀寫存儲器（RAM），現代RAM的結構和存取原理比較復雜懒棉，這里本文拋卻具體差別草描，抽象出一個十分簡單的存取模型來說明RAM的工作原理。

圖5

從抽象角度看漓藕，主存是一系列的存儲單元組成的矩陣陶珠，每個存儲單元存儲固定大小的數據挟裂。每個存儲單元有唯一的地址享钞，現代主存的編址規(guī)則比較復雜，這里將其簡化成一個二維地址：通過一個行地址和一個列地址可以唯一定位到一個存儲單元诀蓉。圖5展示了一個4 x 4的主存模型栗竖。

主存的存取過程如下：

當系統(tǒng)需要讀取主存時，則將地址信號放到地址總線上傳給主存渠啤，主存讀到地址信號后狐肢，解析信號并定位到指定存儲單元，然后將此存儲單元數據放到數據總線上沥曹，供其它部件讀取份名。

寫主存的過程類似，系統(tǒng)將要寫入單元地址和數據分別放在地址總線和數據總線上妓美，主存讀取兩個總線的內容僵腺，做相應的寫操作。

這里可以看出壶栋，主存存取的時間僅與存取次數呈線性關系辰如，因為不存在機械操作，兩次存取的數據的“距離”不會對時間有任何影響贵试，例如琉兜，先取A0再取A1和先取A0再取D3的時間消耗是一樣的。

磁盤存取原理

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

圖6是磁盤的整體結構示意圖。

圖6

一個磁盤由大小相同且同軸的圓形盤片組成往声，磁盤可以轉動（各個磁盤必須同步轉動）擂找。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭浩销，每個磁頭負責存取一個磁盤的內容贯涎。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動）慢洋，每個磁頭同一時刻也必須是同軸的塘雳，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術普筹，可不受此限制）败明。

圖7是磁盤結構的示意圖。

圖7

盤片被劃分成一系列同心環(huán)太防，圓心是盤片中心妻顶，每個同心環(huán)叫做一個磁道，所有半徑相同的磁道組成一個柱面蜒车。磁道被沿半徑線劃分成一個個小的段讳嘱，每個段叫做一個扇區(qū)，每個扇區(qū)是磁盤的最小存儲單元酿愧。為了簡單起見沥潭，我們下面假設磁盤只有一個盤片和一個磁頭。

當需要從磁盤讀取數據時嬉挡，系統(tǒng)會將數據邏輯地址傳給磁盤钝鸽，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁道庞钢，哪個扇區(qū)拔恰。為了讀取這個扇區(qū)的數據，需要將磁頭放到這個扇區(qū)上方焊夸，為了實現這一點仁连，磁頭需要移動對準相應磁道，這個過程叫做尋道阱穗，所耗費時間叫做尋道時間饭冬，然后磁盤旋轉將目標扇區(qū)旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間揪阶。

局部性原理與磁盤預讀

由于存儲介質的特性昌抠，磁盤本身存取就比主存慢很多，再加上機械運動耗費鲁僚，磁盤的存取速度往往是主存的幾百分分之一炊苫，因此為了提高效率裁厅，要盡量減少磁盤I/O。為了達到這個目的侨艾，磁盤往往不是嚴格按需讀取执虹，而是每次都會預讀，即使只需要一個字節(jié)唠梨，磁盤也會從這個位置開始袋励，順序向后讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時当叭，其附近的數據也通常會馬上被使用茬故。

程序運行期間所需要的數據通常比較集中。

由于磁盤順序讀取的效率很高（不需要尋道時間蚁鳖，只需很少的旋轉時間）磺芭，因此對于具有局部性的程序來說，預讀可以提高I/O效率醉箕。

預讀的長度一般為頁（page）的整倍數钾腺。頁是計算機管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊琅攘，每個存儲塊稱為一頁（在許多操作系統(tǒng)中垮庐，頁得大小通常為4k）松邪，主存和磁盤以頁為單位交換數據坞琴。當程序要讀取的數據不在主存中時，會觸發(fā)一個缺頁異常逗抑，此時系統(tǒng)會向磁盤發(fā)出讀盤信號剧辐，磁盤會找到數據的起始位置并向后連續(xù)讀取一頁或幾頁載入內存中，然后異常返回邮府，程序繼續(xù)運行荧关。

B-/+Tree索引的性能分析

到這里終于可以分析B-/+Tree索引的性能了。

上文說過一般使用磁盤I/O次數評價索引結構的優(yōu)劣褂傀。先從B-Tree分析忍啤，根據B-Tree的定義，可知檢索一次最多需要訪問h個節(jié)點仙辟。數據庫系統(tǒng)的設計者巧妙利用了磁盤預讀原理同波，將一個節(jié)點的大小設為等于一個頁，這樣每個節(jié)點只需要一次I/O就可以完全載入叠国。為了達到這個目的未檩，在實際實現B-Tree還需要使用如下技巧：

每次新建節(jié)點時，直接申請一個頁的空間粟焊，這樣就保證一個節(jié)點物理上也存儲在一個頁里冤狡，加之計算機存儲分配都是按頁對齊的孙蒙，就實現了一個node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點常駐內存）悲雳，漸進復雜度為O(h)=O(logdN)O(h)=O(logdN)挎峦。一般實際應用中，出度d是非常大的數字合瓢，通常超過100浑测，因此h非常小（通常不超過3）歪玲。

綜上所述迁央，用B-Tree作為索引結構效率是非常高的。

而紅黑樹這種結構滥崩，h明顯要深的多岖圈。由于邏輯上很近的節(jié)點（父子）物理上可能很遠，無法利用局部性钙皮，所以紅黑樹的I/O漸進復雜度也為O(h)蜂科，效率明顯比B-Tree差很多。

上文還說過短条，B+Tree更適合外存索引导匣，原因和內節(jié)點出度d有關。從上面分析可以看到茸时，d越大索引的性能越好贡定，而出度的上限取決于節(jié)點內key和data的大小：

dmax=floor(pagesize/(keysize+datasize+pointsize))dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整可都。由于B+Tree內節(jié)點去掉了data域缓待，因此可以擁有更大的出度，擁有更好的性能渠牲。

這一章從理論角度討論了與索引相關的數據結構與算法問題旋炒，下一章將討論B+Tree是如何具體實現為MySQL中索引，同時將結合MyISAM和InnDB存儲引擎介紹非聚集索引和聚集索引兩種不同的索引實現形式签杈。

MySQL索引實現

在MySQL中瘫镇，索引屬于存儲引擎級別的概念，不同存儲引擎對索引的實現方式是不同的答姥，本文主要討論MyISAM和InnoDB兩個存儲引擎的索引實現方式铣除。

MyISAM索引實現

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

圖8

這里設表一共有三列通孽，假設我們以Col1為主鍵，則圖8是一個MyISAM表的主索引（Primary key）示意睁壁”晨啵可以看出MyISAM的索引文件僅僅保存數據記錄的地址互捌。在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何區(qū)別行剂，只是主索引要求key是唯一的秕噪，而輔助索引的key可以重復。如果我們在Col2上建立一個輔助索引厚宰，則此索引的結構如下圖所示：

圖9

同樣也是一顆B+Tree腌巾，data域保存數據記錄的地址。因此铲觉，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引澈蝙，如果指定的Key存在，則取出其data域的值撵幽，然后以data域的值為地址灯荧，讀取相應數據記錄。

MyISAM的索引方式也叫做“非聚集”的盐杂，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分逗载。

InnoDB索引實現

雖然InnoDB也使用B+Tree作為索引結構，但具體實現方式卻與MyISAM截然不同链烈。

第一個重大區(qū)別是InnoDB的數據文件本身就是索引文件厉斟。從上文知道，MyISAM索引文件和數據文件是分離的强衡，索引文件僅保存數據記錄的地址擦秽。而在InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構食侮，這棵樹的葉節(jié)點data域保存了完整的數據記錄号涯。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引锯七。

圖10

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

第二個與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址坪蚁。換句話說奔穿，InnoDB的所有輔助索引都引用主鍵作為data域碗短。例如春缕，圖11為定義在Col3上的一個輔助索引：

圖11

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

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

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

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

MySQL的優(yōu)化主要分為結構優(yōu)化（Scheme optimization）和查詢優(yōu)化（Query optimization）。本章討論的高性能索引策略主要屬于結構優(yōu)化范疇勉吻。本章的內容完全基于上文的理論基礎监婶，實際上一旦理解了索引背后的機制，那么選擇高性能的策略就變成了純粹的推理齿桃，并且可以理解這些策略背后的邏輯惑惶。

示例數據庫

為了討論索引策略，需要一個數據量不算小的數據庫作為示例短纵。本文選用MySQL官方文檔中提供的示例數據庫之一：employees带污。這個數據庫關系復雜度適中，且數據量較大香到。下圖是這個數據庫的E-R關系圖（引用自MySQL官方手冊）：

圖12

MySQL官方文檔中關于此數據庫的頁面為http://dev.mysql.com/doc/employee/en/employee.html鱼冀。里面詳細介紹了此數據庫，并提供了下載地址和導入方法悠就，如果有興趣導入此數據庫到自己的MySQL可以參考文中內容千绪。

最左前綴原理與相關優(yōu)化

高效使用索引的首要條件是知道什么樣的查詢會使用到索引，這個問題和B+Tree中的“最左前綴原理”有關梗脾，下面通過例子說明最左前綴原理荸型。

這里先說一下聯合索引的概念。在上文中炸茧，我們都是假設索引只引用了單個的列瑞妇，實際上稿静，MySQL中的索引可以以一定順序引用多個列，這種索引叫做聯合索引踪宠，一般的自赔，一個聯合索引是一個有序元組，其中各個元素均為數據表的一列柳琢，實際上要嚴格定義索引需要用到關系代數绍妨，但是這里我不想討論太多關系代數的話題，因為那樣會顯得很枯燥柬脸，所以這里就不再做嚴格定義他去。另外，單列索引可以看成聯合索引元素數為1的特例倒堕。

以employees.titles表為例灾测，下面先查看其上都有哪些索引：

索引示意圖

從結果中可以到titles表的主索引為，還有一個輔助索引垦巴。為了避免多個索引使事情變復雜（MySQL的SQL優(yōu)化器在多索引時行為比較復雜）媳搪，這里我們將輔助索引drop掉：

ALTER TABLE employees.titles DROP INDEX emp_no;

這樣就可以專心分析索引PRIMARY的行為了。