一刻蚯、mysql數(shù)據(jù)結(jié)構(gòu)

Mysql的兩種主要的存儲(chǔ)引擎都依賴的數(shù)據(jù)結(jié)構(gòu)為B+tree毁葱，一種從B-tree改進(jìn)而來的樹狀數(shù)據(jù)結(jié)構(gòu)
本節(jié)將從幾個(gè)方面來介紹：
1. 介紹B-tree和B+tree隶症；
2. 介紹兩種主要的存儲(chǔ)引擎如何實(shí)現(xiàn)索引阀蒂；

1.1 介紹B-tree和B+tree

1.1.1 B-tree

B-tree名為多路搜索平衡樹驮捍，在此先定義一組值[key,data]危虱，key即為鍵，data即為key鍵所指向的值悍及。
在大多數(shù)的文獻(xiàn)與書籍中葵礼，對(duì)于B-tree的定義有一些差別，本文中參考的是清華大學(xué)出版社的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（2007年版）并鸵。

一棵m階的 B 樹鸳粉，或?yàn)榭諛洌驗(yàn)闈M足下列特性的m叉樹:

1. 樹中每一個(gè)結(jié)點(diǎn)至多有m棵子樹园担；
2. 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)届谈，則至少有兩棵子樹；
3. 除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有?m/2?棵子樹弯汰；
   4.所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)(n,A{0} ,K{1},A{1},K{2} ,A{2},...,K{n},A{n})艰山， 其中：K{i}（i=1,...,n）為關(guān)鍵字，且K{i}<K{i+1}（i=1,...,n-1);A{i}（i=0,...,n）為指向子樹根結(jié)點(diǎn)的指針咏闪，且指針A_{i-1}所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于K{i}（i=1,...,n）曙搬，A{n} 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于K{n} ，n（?m/2??1≤n≤m?1）為關(guān)鍵字的個(gè)數(shù)鸽嫂；
4. 所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上纵装，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在据某，指向這些結(jié)點(diǎn)的指針為空）橡娄。

B-tree示例圖：

B-tree

1.1.2 B+tree

B+tree是B-tree的變體，對(duì)于階數(shù)為m的樹其中改變的地方有：

1. B+tree中每個(gè)結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)范圍變?yōu)?m/2?≤n≤m癣籽，即結(jié)點(diǎn)的最左邊不是子樹指針而是關(guān)鍵字key挽唉；
2. 內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key筷狼；葉子節(jié)點(diǎn)不存儲(chǔ)指針瓶籽，并且所有的關(guān)鍵字key都會(huì)在葉子結(jié)點(diǎn)再存儲(chǔ)一遍
3. 一般B+tree都帶有每個(gè)葉子節(jié)點(diǎn)的指向相鄰葉子節(jié)點(diǎn)的順序指針

在做了以上改變后，B+tree的查找則都必須要查找到葉結(jié)點(diǎn)埂材，而B-tree則可能在某個(gè)內(nèi)結(jié)點(diǎn)即停止查找塑顺；還有B+tree的查找可以有根結(jié)點(diǎn)和起始葉結(jié)點(diǎn)兩個(gè)出發(fā)點(diǎn)。
B+tree示例圖：

B+tree

1.2 兩種存儲(chǔ)引擎如何實(shí)現(xiàn)索引

目前比較主流的存儲(chǔ)引擎貌似是MyISAM和InnoDB兩種楞遏，這里先介紹這兩個(gè)

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

MyISAM是MySQL的默認(rèn)數(shù)據(jù)表類型茬暇，基于了傳統(tǒng)的ISAM類型，ISAM是Indexed Sequential Access Method（有索引的順序訪問方法）的縮寫寡喝，MyISAM使用B+tree存儲(chǔ)引擎結(jié)構(gòu)糙俗，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。
MyISAM采用的是索引文件和數(shù)據(jù)文件分離存儲(chǔ)预鬓，索引文件中存儲(chǔ)的是數(shù)據(jù)文件中相應(yīng)數(shù)據(jù)的地址巧骚，只對(duì)索引采取B+tree數(shù)據(jù)結(jié)構(gòu)赊颠。

`MyISAM`索引原理圖

這里使用別人已有的教學(xué)例子

設(shè)表共有三列，假設(shè)我們以Col1為主鍵劈彪，則上圖是一個(gè)MyISAM表的主索引（Primary key）示意竣蹦。可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址沧奴。在MyISAM中痘括，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的滔吠，而輔助索引的key可以重復(fù)纲菌。如果我們?cè)贑ol2上建立一個(gè)輔助索引，則此索引的結(jié)構(gòu)如圖

輔助索引原理圖

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

InnoDB使用的也是B+tree數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)器引擎，但是和MyISAM差別比較大只冻。
首先InnoDB的數(shù)據(jù)文件本身就是索引文件庇麦。即數(shù)據(jù)文件就按照B+tree的結(jié)構(gòu)存儲(chǔ)，這棵樹的key即是InnoDB中的主鍵属愤，這棵樹的葉結(jié)點(diǎn)對(duì)應(yīng)的data域存儲(chǔ)的是完整的數(shù)據(jù)記錄女器。

輔助索引原理圖

輔助索引原理圖

由此我們清楚了InnoDB的主鍵最好使用單調(diào)有序的字段，并且不適合太長的字段乔妈，因?yàn)槊總€(gè)輔助索引都存儲(chǔ)主索引字段蝙云，太長的主鍵會(huì)造成輔助索引空間太大，一般使用的是自增的整型字段路召。

二勃刨、 索引分類

2.1 B-Tree索引及B+Tree索引

前面已經(jīng)介紹了InnoDB及MyISAM兩種最常用的存儲(chǔ)引擎所基于的數(shù)據(jù)結(jié)構(gòu)---B-Tree和B+Tree，以及是如何存儲(chǔ)索引和鍵值的股淡，基于這兩種數(shù)據(jù)結(jié)構(gòu)的索引就是B-Tree索引及B+Tree索引身隐。
本文的示例數(shù)據(jù)表People，創(chuàng)建如下表：

建表語句

接著介紹下對(duì)于這種索引有效的查詢類型唯灵。

全值匹配

全值匹配指的是和索引中的所有列進(jìn)行匹配贾铝，以上面的例子即為可查詢姓zhang,名san，出生于1960-01-01的人

匹配最左前綴

即只使用索引的第一列埠帕，上述例子中即可用索引查詢姓zhang的人

匹配列前綴

也可以只匹配某一列的值得開頭部分垢揩。上述例子中即可用索引查詢姓氏中以zh開頭的信息。也是只使用了索引的第一列敛瓷。

匹配范圍值

前面提到的索引即可范圍查詢按字母順序姓氏在Li和zhang之間的人叁巨。同樣是只使用了第一列

精確匹配某一列并范圍匹配另外一列

上述例子中即可精確匹配所有姓氏為zhang，并且按字母順序名字在san到si之中的信息琐驴。
即第一列surname全匹配俘种，第二列name范圍匹配秤标。

只訪問索引的查詢

B-Tree通常可以支持“只訪問索引的查詢”宙刘，即查詢只需要訪問索引苍姜，而無需訪問數(shù)據(jù)行。

上述中創(chuàng)建的索引叫做多列索引悬包，對(duì)應(yīng)的另一類即為單列索引衙猪，在‘高性能索引策略/多列索引’中會(huì)詳細(xì)介紹。

2.2 哈希索引 及 R-Tree索引

hash 哈希索引基于哈希表實(shí)現(xiàn)布近，只有精確匹配索引所有列的查詢才有效垫释。對(duì)于每一行數(shù)據(jù)，存儲(chǔ)引擎都會(huì)對(duì)所有的索引列計(jì)算一個(gè)哈希嗎（hash code）撑瞧，哈希嗎是一個(gè)較小的值棵譬，并且不同鍵值的行計(jì)算出來的哈希碼也不一樣。哈希索引將所有的哈希碼存儲(chǔ)在索引中预伺，同時(shí)在哈希表中保存指向每個(gè)數(shù)據(jù)行的指針订咸。 在MySQL中，只有Memory引擎顯式支持哈希索引酬诀。 InnoDB引擎有一個(gè)特殊的功能叫做“自適應(yīng)哈显嗳拢”，當(dāng)InnodeDB注意到某些索引值被使用的非常頻繁時(shí)瞒御，它會(huì)在內(nèi)存中基于B-Tree索引之上在創(chuàng)建一個(gè)哈希索引父叙，這樣就讓B-Tree索引也具有哈希索引的一些優(yōu)點(diǎn)，比如快速的哈希查找肴裙。

空間數(shù)據(jù)索引（R-Tree） MyISAM表支持空間索引趾唱，可以用做地理數(shù)據(jù)存儲(chǔ)。和B-Tree索引不同践宴，這類索引無須前綴查詢鲸匿。空間索引會(huì)從所有維度來索引數(shù)據(jù)阻肩。查詢時(shí)，可以有效地使用任意維度來組合查詢运授。必須使用mysql的GIS相關(guān)函數(shù)如MBRCONTAINS()等來維護(hù)數(shù)據(jù)烤惊。mysql的GIS支持并不完善，所以大部分人都不會(huì)使用這個(gè)特性吁朦。開源數(shù)據(jù)庫中對(duì)GIS的解決方案做的比較好的是PostgreSQL的postGIS柒室。

2.3 關(guān)于B-tree索引的限制

1. 最左前綴匹配原則，即必須按照多列索引的最左列開始查找逗宜，或者每一列索引的最左前面的幾個(gè)字符匹配查找雄右，如果不是按照索引的最左列開始查找空骚，則無法使用索引。例如上面的例子中無法用索引查找名為san的數(shù)據(jù)擂仍。類似的囤屹，也無法查找姓氏以某個(gè)字母為結(jié)尾的數(shù)據(jù)。
2. 不能跳過索引中的列逢渔，例如上述例子中的索引無法用于查詢surname = peng and birthday = 1994-05-17;的信息肋坚，因?yàn)闆]有指定name條件。
3. 如果查詢中有某一個(gè)列的范圍查詢肃廓，則其右邊所有列都無法使用索引進(jìn)行優(yōu)化查找智厌。例如上述表中，條件為where surname = peng and name = tu% and birthday = 1994-05-17的查詢無法利用到birthday索引盲赊，因?yàn)?code>name列有個(gè)模糊查詢铣鹏，屬于范圍查詢，但是范圍查詢前面的列是可以利用索引的哀蘑。

由此可以得出诚卸，類似的在where條件查詢中想進(jìn)行模糊查詢時(shí)，aaa%則可以利用上索引递礼，而%aaa%以及%aaa則無法利用上索引惨险，以及范圍查詢條件最好放到后面，或者范圍查詢列值的數(shù)量有限時(shí)脊髓，可以通過使用多個(gè)等于條件來代替范圍查詢辫愉。
還有，盡可能將需要做范圍查詢的列放到索引的后面将硝，這樣優(yōu)化器能使用盡可能多的索引列恭朗。 索引的順序很重要。

三依疼、 高性能的索引策略

3.1 獨(dú)立的列

‘獨(dú)立的列’是指索引列不能是表達(dá)式的一部分痰腮，也不能是函數(shù)的參數(shù)。
例如：mysql> select x from table where x+1 = 5;
雖然可以很容易的分辯出x的值為4律罢，但是Mysql則無法利用該索引（如果x是索引的話）膀值。盡量養(yǎng)成簡化where的習(xí)慣，始終將索引單獨(dú)的的放在符號(hào)的一側(cè)误辑，這樣Mysql才可以利用上索引沧踏。

3.2 索引選擇性 和 前綴索引

先介紹索引選擇性
索引的選擇性是指，不重復(fù)的索引值和數(shù)據(jù)表的記錄總數(shù)（T）的比值巾钉，范圍在 1/T 到 1 之間翘狱。不重復(fù)的索引值也稱為基數(shù)（cardinality）。因?yàn)檫x擇性高的索引可以讓Mysql在查找時(shí)過濾掉更多的行砰苍，所以索引的選擇性越高則查詢效率越高潦匈。唯一索引的基數(shù)即為數(shù)據(jù)的條數(shù)阱高，其選擇性為1，所以唯一索引的性能最好茬缩。
對(duì)于TEXT或是VARCHAR類型的列赤惊，當(dāng)這個(gè)列中的值長度很大又必須利用其進(jìn)行查詢時(shí)，就必須使用這個(gè)列的前幾位值以作索引寒屯，即前綴索引荐捻，因?yàn)檎麄€(gè)列的值當(dāng)做索引時(shí)B+tree會(huì)占用非常大的空間，查找也不方便寡夹。
而制定前綴索引時(shí)要注意的一點(diǎn)就是這個(gè)前綴索引的選擇性需要和整個(gè)列的選擇性接近处面，這樣性能不會(huì)影響太多，同時(shí)還不能太長而占用太多空間菩掏。
這有一種尋找最佳前綴索引的方式魂角，即根據(jù)選擇性的定義來進(jìn)行計(jì)算其完整列的選擇性及其前綴的選擇性以便對(duì)比。
假設(shè)：有一個(gè)表中的某一列智绸，名為session野揪，其值為十六進(jìn)制的ID
首先進(jìn)行完整列的選擇性的計(jì)算
mysql> SELECT COUNT(DISTINCT session) / COUNT( * ) FROM table;
如果是唯一ID，則其值應(yīng)為1瞧栗，然后計(jì)算這個(gè)列的前綴長度為x的選擇性斯稳，
mysql> SELECT COUNT(DISTINCT LEFT( session , x )) / COUNT( * ) FROM table;
得到一個(gè)小數(shù)值，可以改變x的值來計(jì)算不同前綴的選擇性迹恐，最后在多個(gè)值中挣惰，綜合考慮選擇性接近性和前綴長度的兩個(gè)方面，可以選出一個(gè)較為合適的前綴索引殴边。
創(chuàng)建一個(gè)前綴長度為x的索引：
mysql> ALTER TABLE table ADD KEY (session (x) );

小貼士：例如某個(gè)列的值存的是郵箱時(shí)憎茂，可以先字符串反轉(zhuǎn)，或者根據(jù)@標(biāo)識(shí)符前后顛倒锤岸，再存入數(shù)據(jù)庫竖幔，再建立前綴索引，這樣就可以根據(jù)前綴索引快速查出特定郵箱域名的所有信息了是偷。

3.3 多列索引

在Mysql執(zhí)行查詢時(shí)拳氢，如果是使用多列索引，則會(huì)先查詢符合第一列索引的數(shù)據(jù)集蛋铆，然后再在這一部分?jǐn)?shù)據(jù)集中查詢出符合第二列的數(shù)據(jù)饿幅，以此類推，這樣在不用掃描數(shù)據(jù)的情況下就能選出數(shù)據(jù)戒职；
而如果一個(gè)多列索引拆分成多個(gè)單列索引的話，Mysql在執(zhí)行查詢時(shí)透乾，只會(huì)從中選出一個(gè)限制最嚴(yán)格的索引以供使用洪燥，其他的索引就浪費(fèi)了磕秤，所以在上述情況中多列索引性能要好
注：在Mysql 5.0之后，Mysql添加了‘索引合并’策略捧韵，一定程度上可以使用表上的多個(gè)單列索引來定位數(shù)據(jù)市咆。
實(shí)際上，Mysql 5.0之后有種算法可以查詢能夠同時(shí)使用這兩個(gè)單列索引進(jìn)行掃描再来，并將結(jié)果合并蒙兰。
這種算法的三個(gè)變種: or條件的聯(lián)合(union)， and條件的相交(intersection) 及 組合前兩種情況的聯(lián)合及相交
例如:

`and`優(yōu)化

可見在Extra列中芒篷，顯示為兩種索引的相交優(yōu)化搜变。
雖說如此，這種處理會(huì)帶來一些負(fù)面影響:

• 當(dāng)服務(wù)器需要對(duì)多個(gè)索引做聯(lián)合操作時(shí)针炉，即有多個(gè)or條件時(shí)挠他，通常需要消耗CPU和內(nèi)存資源在算法的緩存、排序和合并操作上篡帕。當(dāng)其中一些索引的選擇性不高而導(dǎo)致數(shù)據(jù)量很大時(shí)此情況更甚殖侵。
• 其次，這些優(yōu)化計(jì)算所消耗的成本是不會(huì)被優(yōu)化器計(jì)入“查詢成本”中镰烧，當(dāng)消耗了更多的CPU和內(nèi)存資源而不知曉時(shí)拢军，還是蠻可怕的。
• 還有一個(gè)數(shù)據(jù)庫服務(wù)器有多個(gè)任務(wù)需要查詢時(shí)怔鳖，這種優(yōu)化會(huì)影響查詢的并發(fā)性茉唉，降低效率。

此外败砂，這種優(yōu)化有使用限制赌渣，例如，我的where條件中的使用的是a_id和b_id兩種單列索引昌犹，也只有在查詢這兩列的值的情況下才會(huì)運(yùn)用到優(yōu)化坚芜，當(dāng)查詢這兩列之外的值時(shí)就無法使用優(yōu)化。如下圖:

優(yōu)化失效

查詢多一個(gè)gender字段時(shí)斜姥，Extra列顯示并無優(yōu)化策略鸿竖。相同模式的sql語句，可能有時(shí)能使用索引铸敏，有時(shí)不能使用索引缚忧。是否能使用索引，取決于mysql查詢優(yōu)化器對(duì)統(tǒng)計(jì)數(shù)據(jù)分析后杈笔，是否認(rèn)為使用索引更快闪水。
所以相比之下，對(duì)于一些常用多個(gè)需要聯(lián)合查詢的條件創(chuàng)建一個(gè)多列索引更好些蒙具。

3.4 選擇合適的索引列順序

這一節(jié)主要是針對(duì) B-Tree索引球榆，常用的存儲(chǔ)引擎即為InnoDB和MyISAM朽肥。

一條經(jīng)驗(yàn)法則(從書上學(xué)來的)，即 : 將選擇性最高的列放到索引放到索引的最前列持钉。
按照上述的關(guān)于選擇性的介紹中衡招，可以用一條sql計(jì)算出所有的需要用到的索引的相對(duì)應(yīng)的選擇性，又或者在知道了該表中的大致數(shù)據(jù)記錄數(shù)的情況下每强，用show index from table來查看所有的索引對(duì)應(yīng)的基數(shù)值(Cardinality)始腾，也能大致比較出索引選擇性的高低。

查看索引

上圖可見People表中所有索引的基數(shù)空执。
也就是提醒大家浪箭，別忘了where子句中的排序、分組和范圍條件等因素脆烟，說不定你就在這踩了坑山林。

3.5 覆蓋索引

如果一個(gè)索引包含了所有需要查詢的字段的值，就稱之為“覆蓋索引”邢羔。
覆蓋索引有以下幾點(diǎn)好處:

• 覆蓋索引對(duì)于I/O密集型的應(yīng)用很有幫助驼抹，因?yàn)閿?shù)據(jù)量比較小則可以放入主存中，加快讀取速度
• 如MyISAM存儲(chǔ)引擎在內(nèi)存中只緩存了引擎拜鹤，數(shù)據(jù)則依賴操作系統(tǒng)緩存框冀，所以只查詢索引值會(huì)飛快
• InnoDB存儲(chǔ)引擎使用的聚簇索引，覆蓋索引更有用敏簿。因?yàn)?code>InnoDB的二級(jí)索引的B-Tree的葉結(jié)點(diǎn)存儲(chǔ)的是對(duì)應(yīng)的一級(jí)索引明也，所以如果二級(jí)索引覆蓋了所要查詢的值則會(huì)少一次利用一級(jí)索引查詢。效率提升很多惯裕。

當(dāng)發(fā)起一個(gè)索引覆蓋查詢時(shí)温数，在Extra列中可見“Using index”的信息。
例如:

覆蓋索引

建立的多列索引包含了所要查詢的字段蜻势，索引可直接查詢Using index而提升速度撑刺。
注:
其一:當(dāng)查詢中使用了一個(gè) * 時(shí)，肯定是無法使用覆蓋索引的握玛；
其二:如果不符合最左前綴匹配原則够傍，也無法使用索引覆蓋。

3.6 冗余索引

冗余即多余
例如挠铲，創(chuàng)建了key (a_id, b_id)索引時(shí)冕屯，如果再創(chuàng)建一個(gè)key (a_id)就是多余的，因?yàn)樗皇嵌嗔兴饕那熬Y而已
但是當(dāng)創(chuàng)建key (b_id)時(shí)拂苹，就不屬于冗余索引了安聘，因?yàn)樯鲜龅亩嗔兴饕菬o法單獨(dú)使用b_id 作索引查詢。
理論上冗余索引會(huì)帶來一定程度上的查詢影響，與當(dāng)前條查詢語句相關(guān)的索引數(shù)量越多搞挣，效率越低带迟，原因在于優(yōu)化器需要從information_schema中獲取相關(guān)索引的metadata信息并分析，索引數(shù)量越多囱桨，這個(gè)過程越漫長。雖然一般來說這個(gè)影響不太大嗅绰。

四舍肠、總結(jié)

索引太復(fù)雜，原理要理解窘面，創(chuàng)建需謹(jǐn)慎翠语，使用多思考。
(這句是給我自己說的)

以上财边。

參考文獻(xiàn)：
[1]：《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（2007年版）肌括，清華大學(xué)出版社，編著者為嚴(yán)蔚敏酣难，吳偉民谍夭。
[2]：http://blog.codinglabs.org/articles/theory-of-mysql-index.htm
[3]：《高性能MySQL》，電子工業(yè)出版社憨募，Baron Schwartz紧索，Peter Zaitsev，Vadim 著菜谣；寧海元珠漂，周振興，彭立勛等 譯