MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理

原文鏈接：MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理

本文以MySQL數(shù)據(jù)庫為研究對象叉弦，討論與數(shù)據(jù)庫索引相關(guān)的一些話題。特別需要說明的是瓶籽，MySQL支持諸多存儲引擎洞慎，而各種存儲引擎對索引的支持也各不相同，因此MySQL數(shù)據(jù)庫支持多種索引類型菱皆，如BTree索引须误，哈希索引挨稿，全文索引等等。為了避免混亂京痢，本文將只關(guān)注于BTree索引奶甘，因為這是平常使用MySQL時主要打交道的索引，至于哈希索引和全文索引本文暫不討論祭椰。

文章主要內(nèi)容分為三個部分臭家。

第一部分主要從數(shù)據(jù)結(jié)構(gòu)及算法理論層面討論MySQL數(shù)據(jù)庫索引的數(shù)理基礎。

第二部分結(jié)合MySQL數(shù)據(jù)庫中MyISAM和InnoDB數(shù)據(jù)存儲引擎中索引的架構(gòu)實現(xiàn)討論聚集索引方淤、非聚集索引及覆蓋索引等話題钉赁。

第三部分根據(jù)上面的理論基礎，討論MySQL中高性能使用索引的策略臣淤。

數(shù)據(jù)結(jié)構(gòu)及算法基礎

索引的本質(zhì)

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

數(shù)據(jù)庫查詢是數(shù)據(jù)庫的主要功能之一，最基本的查詢算法是順序查找（linear search）時間復雜度為O(n)按厘，顯然在數(shù)據(jù)量很大時效率很低医吊。優(yōu)化的查找算法如二分查找（binary search）、二叉樹查找（binary tree search）等逮京，雖然查找效率提高了卿堂。但是各自對檢索的數(shù)據(jù)都有要求：二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應用于二叉查找樹上懒棉，但是數(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)就是索引。

看一個例子：

圖1

圖1展示了一種可能的索引方式倔韭。左邊是數(shù)據(jù)表术浪，一共有兩列七條記錄，最左邊的是數(shù)據(jù)記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）寿酌。為了加快Col2的查找胰苏，可以維護一個右邊所示的二叉查找樹，每個節(jié)點分別包含索引鍵值和一個指向?qū)獢?shù)據(jù)記錄物理地址的指針醇疼，這樣就可以運用二叉查找在O(log2n)的復雜度內(nèi)獲取到相應數(shù)據(jù)碟联。

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

B-Tree和B+Tree

關(guān)于B樹和B+樹請參考關(guān)于B樹的一些總結(jié)壶栋，這篇文章介紹的比較詳細，同時容易理解普监。

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

B-Tree

為了描述B-Tree毙玻，首先定義一條數(shù)據(jù)記錄為一個二元組[key, data]，key為記錄的鍵值廊散，對于不同數(shù)據(jù)記錄桑滩，key是互不相同的；data為數(shù)據(jù)記錄除key外的數(shù)據(jù)允睹。那么B-Tree是滿足下列條件的數(shù)據(jù)結(jié)構(gòu)：

d>=2，即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é)點node最左邊且不為null粟焊，則其指向結(jié)點的所有key小于v(key1)，其中v(key1)為node的第一個key的值孙蒙。

如果某個指針在結(jié)點node最右邊且不為null项棠，則其指向結(jié)點的所有key大于v(keym)，其中v(keym)為node的最后一個key的值挎峦。

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

圖2是一個d=2的B-Tree示意圖坦胶。

圖2

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

BTree_Search(node, key) {if(node ==null)returnnull;foreach(node.key)

{if(node.key[i] == key)returnnode.data[i];if(node.key[i] > key)returnBTree_Search(point[i]->node);

}returnBTree_Search(point[i+1]->node);

}

data= BTree_Search(root, my_key);

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

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é)點不存儲指針楣导。

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

圖3

由于并不是所有節(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的基礎上進行了優(yōu)化秉继，增加了順序訪問指針祈噪。

圖4

如圖4所示，在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)撵幽。

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

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

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

主存存取原理

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

圖5

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

主存的存取過程如下：

當系統(tǒng)需要讀取主存時镜沽，則將地址信號放到地址總線上傳給主存，主存讀到地址信號后贱田，解析信號并定位到指定存儲單元缅茉，然后將此存儲單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取男摧。

寫主存的過程類似蔬墩，系統(tǒng)將要寫入單元地址和數(shù)據(jù)分別放在地址總線和數(shù)據(jù)總線上，主存讀取兩個總線的內(nèi)容耗拓，做相應的寫操作拇颅。

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

磁盤存取原理

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

圖6是磁盤的整體結(jié)構(gòu)示意圖痹届。

圖6

一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉(zhuǎn)動（各個磁盤必須同步轉(zhuǎn)動）打月。在磁盤的一側(cè)有磁頭支架短纵，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內(nèi)容僵控。磁頭不能轉(zhuǎn)動香到，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的报破，即從正上方向下看悠就，所有磁頭任何時候都是重疊的（不過目前已經(jīng)有多磁頭獨立技術(shù)，可不受此限制）充易。

圖7是磁盤結(jié)構(gòu)的示意圖梗脾。

圖7

盤片被劃分成一系列同心環(huán)，圓心是盤片中心盹靴，每個同心環(huán)叫做一個磁道炸茧，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段稿静，每個段叫做一個扇區(qū)梭冠，每個扇區(qū)是磁盤的最小存儲單元。為了簡單起見改备，我們下面假設磁盤只有一個盤片和一個磁頭控漠。

當需要從磁盤讀取數(shù)據(jù)時，系統(tǒng)會將數(shù)據(jù)邏輯地址傳給磁盤悬钳，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址盐捷，即確定要讀的數(shù)據(jù)在哪個磁道，哪個扇區(qū)默勾。為了讀取這個扇區(qū)的數(shù)據(jù)碉渡，需要將磁頭放到這個扇區(qū)上方，為了實現(xiàn)這一點母剥，磁頭需要移動對準相應磁道滞诺，這個過程叫做尋道，所耗費時間叫做尋道時間媳搪，然后磁盤旋轉(zhuǎn)將目標扇區(qū)旋轉(zhuǎn)到磁頭下铭段，這個過程耗費的時間叫做旋轉(zhuǎn)時間骤宣。

局部性原理與磁盤預讀

由于存儲介質(zhì)的特性秦爆，磁盤本身存取就比主存慢很多，再加上機械運動耗費憔披，磁盤的存取速度往往是主存的幾百分分之一等限，因此為了提高效率爸吮，要盡量減少磁盤I/O。為了達到這個目的望门，磁盤往往不是嚴格按需讀取形娇，而是每次都會預讀，即使只需要一個字節(jié)筹误，磁盤也會從這個位置開始桐早，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計算機科學中著名的局部性原理：

當一個數(shù)據(jù)被用到時厨剪，其附近的數(shù)據(jù)也通常會馬上被使用哄酝。

程序運行期間所需要的數(shù)據(jù)通常比較集中。

由于磁盤順序讀取的效率很高（不需要尋道時間祷膳，只需很少的旋轉(zhuǎn)時間）陶衅，因此對于具有局部性的程序來說，預讀可以提高I/O效率直晨。

預讀的長度一般為頁（page）的整倍數(shù)搀军。頁是計算機管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊勇皇，每個存儲塊稱為一頁（在許多操作系統(tǒng)中罩句，頁得大小通常為4k），主存和磁盤以頁為單位交換數(shù)據(jù)敛摘。當程序要讀取的數(shù)據(jù)不在主存中時的止，會觸發(fā)一個缺頁異常，此時系統(tǒng)會向磁盤發(fā)出讀盤信號着撩，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中诅福，然后異常返回，程序繼續(xù)運行拖叙。

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

從使用磁盤I/O次數(shù)評價索引結(jié)構(gòu)的優(yōu)劣性：根據(jù)B-Tree的定義氓润，可知檢索一次最多需要訪問h個結(jié)點。數(shù)據(jù)庫系統(tǒng)的設計者巧妙的利用了磁盤預讀原理薯鳍，將一個結(jié)點的大小設為等于一個頁面咖气，這樣每個結(jié)點只需要一次I/O就可以完全載入。為了達到這個目的挖滤，在實際實現(xiàn)B-Tree還需要使用如下技巧：

每次新建結(jié)點時崩溪，直接申請一個頁面的空間，這樣可以保證一個結(jié)點的大小等于一個頁面斩松，加之計算機存儲分配都是按頁對齊的伶唯，就實現(xiàn)了一個node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O（根結(jié)點常駐內(nèi)存）惧盹，漸進復雜度為O(h)=O(logdN)乳幸。一般實際應用中瞪讼，出讀d是非常大的數(shù)字，通常超過100粹断，因此h非常小符欠。

綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的瓶埋。

而紅黑樹結(jié)構(gòu)希柿，h明顯要深得多。由于邏輯上很近的結(jié)點（父子結(jié)點）物理上可能離得很遠养筒，無法利用局部性原理狡汉。所以即使紅黑樹的I/O漸進復雜度也為O(h)，但是查找效率明顯比B-Tree差得多闽颇。

B+Tree更適合外存索引盾戴，是和內(nèi)結(jié)點出度d有關(guān)。從上面分析可以看到兵多，d越大索引的性能越好尖啡，而出度的上限取決于結(jié)點內(nèi)key和data的大小：dmax=floor(pagesize/(keysize+datasize+pointsize))剩膘。

floor表示向下取整衅斩。由于B+Tree內(nèi)結(jié)點去掉了data域，因此可以擁有更大的出度怠褐，擁有更好的性能畏梆。

這一章從理論角度討論了與索引相關(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兩個存儲引擎(MySQL數(shù)據(jù)庫MyISAM和InnoDB存儲引擎的比較)的索引實現(xiàn)方式。

MyISAM索引實現(xiàn)

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

圖8

這里設表一共有三列，假設我們以Col1為主鍵遥金，則圖8是一個MyISAM表的主索引（Primary key）示意浴捆。可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址稿械。在MyISAM中选泻，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的溜哮，而輔助索引的key可以重復滔金。如果我們在Col2上建立一個輔助索引色解，則此索引的結(jié)構(gòu)如下圖所示：

圖9

同樣也是一顆B+Tree茂嗓，data域保存數(shù)據(jù)記錄的地址餐茵。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引述吸，如果指定的Key存在忿族，則取出其data域的值，然后以data域的值為地址蝌矛，讀取相應數(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ù)文件本身就是主索引。

圖10

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

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

圖11

這里以英文字符的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)容完全基于上文的理論基礎，實際上一旦理解了索引背后的機制淤击，那么選擇高性能的策略就變成了純粹的推理匠抗，并且可以理解這些策略背后的邏輯。

示例數(shù)據(jù)庫

為了討論索引策略污抬，需要一個數(shù)據(jù)量不算小的數(shù)據(jù)庫作為示例汞贸。本文選用MySQL官方文檔中提供的示例數(shù)據(jù)庫之一：employees。這個數(shù)據(jù)庫關(guān)系復雜度適中印机，且數(shù)據(jù)量較大矢腻。下圖是這個數(shù)據(jù)庫的E-R關(guān)系圖（引用自MySQL官方手冊）：

圖12

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

高效使用索引的首要條件是知道什么樣的查詢會使用到索引，這個問題和B+Tree中的“最左前綴原理”有關(guān)射赛，下面通過例子說明最左前綴原理多柑。

這里先說一下聯(lián)合索引的概念。在上文中楣责，我們都是假設索引只引用了單個的列竣灌，實際上，MySQL中的索引可以以一定順序引用多個列秆麸，這種索引叫做聯(lián)合索引初嘹，一般的，一個聯(lián)合索引是一個有序元組沮趣，其中各個元素均為數(shù)據(jù)表的一列屯烦，實際上要嚴格定義索引需要用到關(guān)系代數(shù)，但是這里我不想討論太多關(guān)系代數(shù)的話題，因為那樣會顯得很枯燥驻龟，所以這里就不再做嚴格定義温眉。另外，單列索引可以看成聯(lián)合索引元素數(shù)為1的特例翁狐。

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

| titles |0| PRIMARY? |2| title? ? ? | A? ? ? ? |? ? ? ? NULL |? ? ? | BTREE? ? ? |

| titles |0| PRIMARY? |3| from_date? | A? ? ? ? |443308|? ? ? | BTREE? ? ? |

| titles |1| emp_no? |1| emp_no? ? ? | A? ? ? ? |443308|? ? ? | BTREE? ? ? |+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+

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

ALTERTABLEemployees.titles DROP INDEX emp_no;

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

全列匹配

很明顯隐锭，當按照索引中所有列進行精確匹配（這里精確匹配指“=”或“IN”匹配）時，索引可以被用到计贰。這里有一點需要注意钦睡，理論上索引對順序是敏感的，但是由于MySQL的查詢優(yōu)化器會自動調(diào)整where子句的條件順序以使用適合的索引躁倒，例如我們將where中的條件順序顛倒：

效果是一樣的荞怒。

最左前綴匹配

EXPLAINSELECT*FROMemployees.titlesWHEREemp_no='10001';+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+| id | select_type | table? | type | possible_keys | key? ? | key_len | ref? | rows | Extra |+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+|1| SIMPLE? ? ? | titles | ref? | PRIMARY? ? ? | PRIMARY |4| const |1|? ? ? |+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+

當查詢條件精確匹配索引的左邊連續(xù)一個或幾個列時，如或秧秉，所以可以被用到褐桌，但是只能用到一部分，即條件所組成的最左前綴象迎。上面的查詢從分析結(jié)果看用到了PRIMARY索引荧嵌，但是key_len為4，說明只用到了索引的第一列前綴砾淌。

查詢條件用到了索引中列的精確匹配啦撮，但是中間某個條件未提供

此時索引使用情況和情況二相同，因為title未提供汪厨，所以查詢只用到了索引的第一列赃春，而后面的from_date雖然也在索引中，但是由于title不存在而無法和左前綴連接劫乱，因此需要對結(jié)果進行掃描過濾from_date（這里由于emp_no唯一织中，所以不存在掃描）。如果想讓from_date也使用索引而不是where過濾衷戈，可以增加一個輔助索引狭吼，此時上面的查詢會使用這個索引。除此之外脱惰，還可以使用一種稱之為“隔離列”的優(yōu)化方法搏嗡，將emp_no與from_date之間的“坑”填上。

首先我們看下title一共有幾種不同的值：

SELECTDISTINCT(title)FROMemployees.titles;+--------------------+| title? ? ? ? ? ? ? |+--------------------+| Senior Engineer? ? |

| Staff? ? ? ? ? ? ? |

| Engineer? ? ? ? ? |

| Senior Staff? ? ? |

| Assistant Engineer |

| Technique Leader? |

| Manager? ? ? ? ? ? |+--------------------+

只有7種。在這種成為“坑”的列值比較少的情況下采盒，可以考慮用“IN”來填補這個“坑”從而形成最左前綴：

這次key_len為59旧乞，說明索引被用全了，但是從type和rows看出IN實際上執(zhí)行了一個range查詢磅氨，這里檢查了7個key尺栖。看下兩種查詢的性能比較：

SHOW PROFILES;+----------+------------+-------------------------------------------------------------------------------+| Query_ID | Duration? | Query? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |+----------+------------+-------------------------------------------------------------------------------+|10|0.00058000|SELECT*FROMemployees.titlesWHEREemp_no='10001'ANDfrom_date='1986-06-26'|

|11|0.00052500|SELECT*FROMemployees.titlesWHEREemp_no='10001'ANDtitleIN...? ? ? ? ? |+----------+------------+-------------------------------------------------------------------------------+

“填坑”后性能提升了一點烦租。如果經(jīng)過emp_no篩選后余下很多數(shù)據(jù)延赌，則后者性能優(yōu)勢會更加明顯。當然叉橱，如果title的值很多挫以，用填坑就不合適了，必須建立輔助索引窃祝。

查詢條件沒有指定索引第一列

由于不是最左前綴掐松，索引這樣的查詢顯然用不到索引。

匹配某列前綴字符串

此時可以用到索引粪小，~~但是如果通配符不是只出現(xiàn)在末尾大磺，則無法使用索引。~~（原文表述有誤探膊，如果通配符%不出現(xiàn)在開頭杠愧，則可以用到索引，但根據(jù)具體情況不同可能只會用其中一個前綴）

范圍查詢

范圍列可以用到索引（必須是最左前綴）逞壁，但是范圍列后面的列無法用到索引流济。同時，索引最多用于一個范圍列猾担，因此如果查詢條件中有兩個范圍列則無法全用到索引袭灯。

可以看到索引對第二個范圍索引無能為力。這里特別要說明MySQL一個有意思的地方绑嘹，那就是僅用explain可能無法區(qū)分范圍索引和多值匹配稽荧，因為在type中這兩者都顯示為range。同時工腋，用了“between”并不意味著就是范圍查詢姨丈，例如下面的查詢：

看起來是用了兩個范圍查詢，但作用于emp_no上的“BETWEEN”實際上相當于“IN”擅腰，也就是說emp_no實際是多值精確匹配蟋恬。可以看到這個查詢用到了索引全部三個列趁冈。因此在MySQL中要謹慎地區(qū)分多值匹配和范圍匹配歼争，否則會對MySQL的行為產(chǎn)生困惑拜马。

查詢條件中含有函數(shù)或表達式

很不幸，如果查詢條件中含有函數(shù)或表達式沐绒，則MySQL不會為這列使用索引（雖然某些在數(shù)學意義上可以使用）俩莽。例如：

雖然這個查詢和情況五中功能相同驹暑，但是由于使用了函數(shù)left岭洲，則無法為title列應用索引，而情況五中用LIKE則可以吧彪。再如：

顯然這個查詢等價于查詢emp_no為10001的函數(shù)蹋肮，但是由于查詢條件是一個表達式出刷，MySQL無法為其使用索引∨鞅纾看來MySQL還沒有智能到自動優(yōu)化常量表達式的程度馁龟，因此在寫查詢語句時盡量避免表達式出現(xiàn)在查詢中，而是先手工私下代數(shù)運算濒翻，轉(zhuǎn)換為無表達式的查詢語句屁柏。

索引選擇性與前綴索引

既然索引可以加快查詢速度啦膜，那么是不是只要是查詢語句需要有送，就建上索引？答案是否定的僧家。因為索引雖然加快了查詢速度雀摘，但索引也是有代價的：索引文件本身要消耗存儲空間，同時索引會加重插入八拱、刪除和修改記錄時的負擔阵赠，另外，MySQL在運行時也要消耗資源維護索引肌稻，因此索引并不是越多越好清蚀。一般兩種情況下不建議建索引。

第一種情況是表記錄比較少爹谭，例如一兩千條甚至只有幾百條記錄的表枷邪，沒必要建索引，讓查詢做全表掃描就好了诺凡。至于多少條記錄才算多东揣，這個個人有個人的看法，我個人的經(jīng)驗是以2000作為分界線腹泌，記錄數(shù)不超過 2000可以考慮不建索引嘶卧，超過2000條可以酌情考慮索引。

另一種不建議建索引的情況是索引的選擇性較低凉袱。所謂索引的選擇性（Selectivity）芥吟，是指不重復的索引值（也叫基數(shù)侦铜，Cardinality）與表記錄數(shù)（#T）的比值：

Index Selectivity = Cardinality / #T

顯然選擇性的取值范圍為(0, 1]，選擇性越高的索引價值越大钟鸵，這是由B+Tree的性質(zhì)決定的泵额。

這個問題就像是面試時提問我的一個問題：性別列適不適合建立索引？

例如携添，上文用到的employees.titles表嫁盲，如果title字段經(jīng)常被單獨查詢，是否需要建索引烈掠，我們看一下它的選擇性：

SELECTcount(DISTINCT(title))/count(*) AS SelectivityFROMemployees.titles;+-------------+| Selectivity |+-------------+|0.0000|+-------------+

title的選擇性不足0.0001（精確值為0.00001579）羞秤，所以實在沒有什么必要為其單獨建索引。

有一種與索引選擇性有關(guān)的索引優(yōu)化策略叫做前綴索引左敌，就是用列的前綴代替整個列作為索引key瘾蛋，當前綴長度合適時，可以做到既使得前綴索引的選擇性接近全列索引矫限，同時因為索引key變短而減少了索引文件的大小和維護開銷哺哼。下面以employees.employees表為例介紹前綴索引的選擇和使用。

從圖12可以看到employees表只有一個索引叼风，那么如果我們想按名字搜索一個人取董，就只能全表掃描了：

如果頻繁按名字搜索員工，這樣顯然效率很低无宿，因此我們可以考慮建索引茵汰。有兩種選擇，建或孽鸡，看下兩個索引的選擇性：

SELECTcount(DISTINCT(first_name))/count(*) AS SelectivityFROMemployees.employees;+-------------+| Selectivity |+-------------+|0.0042|+-------------+SELECTcount(DISTINCT(concat(first_name, last_name)))/count(*) AS SelectivityFROMemployees.employees;+-------------+| Selectivity |+-------------+|0.9313|+-------------+

顯然選擇性太低蹂午，選擇性很好，但是first_name和last_name加起來長度為30彬碱，有沒有兼顧長度和選擇性的辦法豆胸？可以考慮用first_name和last_name的前幾個字符建立索引，例如巷疼，看看其選擇性：

SELECTcount(DISTINCT(concat(first_name, left(last_name,3))))/count(*) AS SelectivityFROMemployees.employees;+-------------+| Selectivity |+-------------+|0.7879|+-------------+

選擇性還不錯晚胡，但離0.9313還是有點距離，那么把last_name前綴加到4：

SELECTcount(DISTINCT(concat(first_name, left(last_name,4))))/count(*) AS SelectivityFROMemployees.employees;+-------------+| Selectivity |+-------------+|0.9007|+-------------+

這時選擇性已經(jīng)很理想了皮迟，而這個索引的長度只有18搬泥，比短了接近一半伏尼，我們把這個前綴索引建上：

ALTERTABLEemployees.employeesADDINDEX first_name_last_name4 (first_name, last_name(4));

此時再執(zhí)行一遍按名字查詢，比較分析一下與建索引前的結(jié)果：

SHOW PROFILES;+----------+------------+---------------------------------------------------------------------------------+| Query_ID | Duration? | Query? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |+----------+------------+---------------------------------------------------------------------------------+|87|0.11941700|SELECT*FROMemployees.employeesWHEREfirst_name='Eric'ANDlast_name='Anido'|

|90|0.00092400|SELECT*FROMemployees.employeesWHEREfirst_name='Eric'ANDlast_name='Anido'|+----------+------------+---------------------------------------------------------------------------------+

性能的提升是顯著的肢藐，查詢速度提高了120多倍吆豹。

前綴索引兼顧索引大小和查詢速度，但是其缺點是不能用于ORDER BY和GROUP BY操作理盆，也不能用于Covering index（即當索引本身包含查詢所需全部數(shù)據(jù)時痘煤，不再訪問數(shù)據(jù)文件本身）。

InnoDB的主鍵選擇與優(yōu)化

在使用InnoDB存儲引擎時猿规，如果沒有特別的需要衷快，請永遠使用一個與業(yè)務無關(guān)的自增字段作為主鍵。

經(jīng)骋塘看到有帖子或博客討論主鍵選擇問題蘸拔，有人建議使用業(yè)務無關(guān)的自增主鍵，有人覺得沒有必要环葵，完全可以使用如學號或身份證號這種唯一字段作為主鍵调窍。不論支持哪種論點，大多數(shù)論據(jù)都是業(yè)務層面的积担。如果從數(shù)據(jù)庫索引優(yōu)化角度看陨晶，使用InnoDB引擎而不使用自增主鍵絕對是一個糟糕的主意。

上文討論過InnoDB的索引實現(xiàn)帝璧，InnoDB使用聚集索引，數(shù)據(jù)記錄本身被存于主索引（一顆B+Tree）的葉子節(jié)點上湿刽。這就要求同一個葉子節(jié)點內(nèi)（大小為一個內(nèi)存頁或磁盤頁）的各條數(shù)據(jù)記錄按主鍵順序存放的烁，因此每當有一條新的記錄插入時，MySQL會根據(jù)其主鍵將其插入適當?shù)墓?jié)點和位置诈闺，如果頁面達到裝載因子（InnoDB默認為15/16）渴庆，則開辟一個新的頁（節(jié)點）。

如果表使用自增主鍵雅镊，那么每次插入新的記錄襟雷，記錄就會順序添加到當前索引節(jié)點的后續(xù)位置，當一頁寫滿仁烹，就會自動開辟一個新的頁耸弄。如下圖所示：

圖13

這樣就會形成一個緊湊的索引結(jié)構(gòu)，近似順序填滿卓缰。由于每次插入時也不需要移動已有數(shù)據(jù)计呈，因此效率很高砰诵，也不會增加很多開銷在維護索引上。

如果使用非自增主鍵（如果身份證號或?qū)W號等）捌显，由于每次插入主鍵的值近似于隨機茁彭，因此每次新紀錄都要被插到現(xiàn)有索引頁得中間某個位置：

圖14

此時MySQL不得不為了將新記錄插到合適位置而移動數(shù)據(jù)，甚至目標頁面可能已經(jīng)被回寫到磁盤上而從緩存中清掉扶歪，此時又要從磁盤上讀回來理肺，這增加了很多開銷，同時頻繁的移動善镰、分頁操作造成了大量的碎片哲嘲，得到了不夠緊湊的索引結(jié)構(gòu)，后續(xù)不得不通過OPTIMIZE TABLE來重建表并優(yōu)化填充頁面媳禁。

因此眠副，只要可以，請盡量在InnoDB上采用自增字段做主鍵竣稽。

后記

這篇文章斷斷續(xù)續(xù)寫了半個月囱怕，主要內(nèi)容就是上面這些了。不可否認毫别，這篇文章在一定程度上有紙上談兵之嫌娃弓，因為我本人對MySQL的使用屬于菜鳥級別，更沒有太多數(shù)據(jù)庫調(diào)優(yōu)的經(jīng)驗岛宦，在這里大談數(shù)據(jù)庫索引調(diào)優(yōu)有點大言不慚台丛。就當是我個人的一篇學習筆記了。

其實數(shù)據(jù)庫索引調(diào)優(yōu)是一項技術(shù)活砾肺，不能僅僅靠理論挽霉，因為實際情況千變?nèi)f化，而且MySQL本身存在很復雜的機制变汪，如查詢優(yōu)化策略和各種引擎的實現(xiàn)差異等都會使情況變得更加復雜侠坎。但同時這些理論是索引調(diào)優(yōu)的基礎，只有在明白理論的基礎上裙盾，才能對調(diào)優(yōu)策略進行合理推斷并了解其背后的機制实胸，然后結(jié)合實踐中不斷的實驗和摸索，從而真正達到高效使用MySQL索引的目的番官。

另外庐完，MySQL索引及其優(yōu)化涵蓋范圍非常廣，本文只是涉及到其中一部分徘熔。如與排序（ORDER BY）相關(guān)的索引優(yōu)化及覆蓋索引（Covering index）的話題本文并未涉及门躯，同時除B-Tree索引外MySQL還根據(jù)不同引擎支持的哈希索引、全文索引等等本文也并未涉及近顷。如果有機會生音，希望再對本文未涉及的部分進行補充吧宁否。

參考文獻

[1] Baron Scbwartz等著，王小東等譯缀遍；高性能MySQL（High Performance MySQL）慕匠；電子工業(yè)出版社，2010

[2] Michael Kofler 著域醇，楊曉云等譯台谊；MySQL5權(quán)威指南（The Definitive Guide to MySQL5）；人民郵電出版社譬挚，2006

[3] 姜承堯著锅铅；MySQL技術(shù)內(nèi)幕-InnoDB存儲引擎；機械工業(yè)出版社减宣，2011

[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

[5] Codd, E. F. (1970). "A relational model of data for large shared data banks". Communications of the ACM, , Vol. 13, No. 6, pp. 377-387

[6] MySQL5.1參考手冊 -http://dev.mysql.com/doc/refman/5.1/zh/index.html

寫代碼是一種藝術(shù)盐须，甚于蒙娜麗莎的微笑。

最后編輯于：2017.12.10 05:59:09

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末漆腌，一起剝皮案震驚了整個濱河市贼邓，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌闷尿，老刑警劉巖塑径，帶你破解...
沈念sama閱讀 217,185評論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異填具，居然都是意外死亡统舀，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,652評論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門劳景，熙熙樓的掌柜王于貴愁眉苦臉地迎上來誉简，“玉大人，你說我怎么就攤上這事枢泰∶枞冢” “怎么了？”我有些...
開封第一講書人閱讀 163,524評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵衡蚂，是天一觀的道長。經(jīng)常有香客問我骏庸，道長毛甲，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,339評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任具被，我火速辦了婚禮玻募，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘一姿。我一直安慰自己七咧，他們只是感情好跃惫，可當我...
茶點故事閱讀 67,387評論 6贊 391
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著艾栋，像睡著了一般爆存。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上蝗砾，一...
開封第一講書人閱讀 51,287評論 1贊 301
城市分裂傳說
那天先较，我揣著相機與錄音，去河邊找鬼悼粮。笑死闲勺，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的扣猫。我是一名探鬼主播菜循，決...
沈念sama閱讀 40,130評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼申尤！你這毒婦竟也來了癌幕？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 38,985評論 0贊 275
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤瀑凝，失蹤者是張志新（化名）和其女友劉穎序芦，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體粤咪，經(jīng)...
沈念sama閱讀 45,420評論 1贊 313
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡谚中，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,617評論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了寥枝。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片宪塔。...
茶點故事閱讀 39,779評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖囊拜，靈堂內(nèi)的尸體忽然破棺而出某筐，到底是詐尸還是另有隱情，我是刑警寧澤冠跷，帶...
沈念sama閱讀 35,477評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布南誊，位于F島的核電站，受9級特大地震影響蜜托，放射性物質(zhì)發(fā)生泄漏抄囚。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,088評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一橄务、第九天我趴在偏房一處隱蔽的房頂上張望幔托。院中可真熱鬧，春花似錦、人聲如沸重挑。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,716評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽谬哀。三九已至刺覆，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間玻粪，已是汗流浹背隅津。一陣腳步聲響...
開封第一講書人閱讀 32,857評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留劲室，地道東北人伦仍。一個月前我還...
沈念sama閱讀 47,876評論 2贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像很洋，于是被迫代替她去往敵國和親充蓝。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 44,700評論 2贊 354

MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理

推薦閱讀更多精彩內(nèi)容