1、索引組織表

在InnoDB中，表都是根據(jù)主鍵順序組織存放的代态，稱為索引組織表（index organized table）。

每張表都有個主鍵疹吃，如果沒有顯示地定義主鍵蹦疑，則會按照如下方式選擇或創(chuàng)建主鍵：

• 如果有非空唯一索引，以建表時(shí)第一個定義的非空唯一索引作為主鍵
• 如果沒有非空唯一索引萨驶，InnoDB會自動創(chuàng)建一個6字節(jié)大小的rowid作為主鍵

InnoDB 存儲引擎在絕大多數(shù)情況下使用 B+ 樹建立索引歉摧，這是關(guān)系型數(shù)據(jù)庫中查找最為常用和有效的索引，但是 B+ 樹索引并不能找到一個給定鍵對應(yīng)的具體值腔呜，它只能找到數(shù)據(jù)行對應(yīng)的頁叁温，數(shù)據(jù)庫把整個頁讀入到內(nèi)存中，并在內(nèi)存中查找具體的數(shù)據(jù)行核畴。

2膝但、聚集索引與輔助索引

數(shù)據(jù)庫中的 B+ 樹索引可以分為聚集索引（clustered index）和輔助索引（secondary index），它們之間的最大區(qū)別就是谤草，聚集索引中存放著一條行記錄的全部信息跟束，而輔助索引中只包含索引列和一個用于查找對應(yīng)行記錄的“書簽”。

2.1 聚集索引

聚集索引就是按照每張表的主鍵構(gòu)造一棵B+樹丑孩，同時(shí)葉子節(jié)點(diǎn)中存放的即為整張表的行記錄數(shù)據(jù)泳炉，也將聚集索引的葉子節(jié)點(diǎn)成為數(shù)據(jù)頁。

如果使用下面的 SQL 在數(shù)據(jù)庫中創(chuàng)建一張：

CREATE TABLE users( 

id INT NOT NULL, 

first_name VARCHAR(20) NOT NULL, 

last_name VARCHAR(20) NOT NULL, 

age INT NOT NULL, 

PRIMARY KEY(id), 

KEY(last_name, first_name, age) 

KEY(first_name) 

)

B+ 樹就會使用 id 作為索引的鍵嚎杨，并在葉子節(jié)點(diǎn)中存儲一條記錄中的所有信息:

1.png

聚集索引決定了數(shù)據(jù)的物理順序花鹅，所以每張表應(yīng)該有且僅有一個聚集索引（絕大多數(shù)情況下都是主鍵），表中的所有行記錄數(shù)據(jù)都是按照聚集索引的順序存放的枫浙，即只要索引是相鄰的刨肃，那么對應(yīng)的數(shù)據(jù)一定也是相鄰地存放在磁盤上的古拴。

在多數(shù)情況下，查詢優(yōu)化器傾向于采用聚集索引真友，因?yàn)榫奂饕軌蛟贐+樹索引的葉子節(jié)點(diǎn)上直接找到數(shù)據(jù)黄痪，不需要進(jìn)行第二次操作。此外盔然，由于定義了數(shù)據(jù)的邏輯順序桅打，聚集索引對于主鍵的排序查找和范圍查找非常快愈案。

2.2 輔助索引

所有的非聚集索引都稱為為輔助索引挺尾。

輔助索引也是通過 B+ 樹實(shí)現(xiàn)的，但是它的葉節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)站绪，僅包含索引中的所有鍵和一個用于查找對應(yīng)行記錄的“書簽”遭铺，在 InnoDB 中這個書簽就是當(dāng)前記錄的主鍵。

輔助索引的存在并不會影響聚集索引恢准，因?yàn)榫奂饕龢?gòu)成的 B+ 樹是數(shù)據(jù)實(shí)際存儲的形式魂挂，而輔助索引只用于加速數(shù)據(jù)的查找，所以一張表上往往有多個輔助索引以此來提升數(shù)據(jù)庫的性能馁筐。

如果在表 users 中存在一個輔助索引 (first_name, age)涂召，那么它構(gòu)成的 B+ 樹大致就是下圖這樣：

2.png

按照 (first_name, age) 的字母順序?qū)Ρ碇械臄?shù)據(jù)進(jìn)行排序，當(dāng)查找到主鍵時(shí)敏沉，再通過聚集索引獲取到整條行記錄芹扭。

例如執(zhí)行下面的查詢語句：

select * from users where first_name = "Jones" and age <=30

數(shù)據(jù)庫首先通過輔助索引查找到對應(yīng)的主鍵，然后在聚集索引中使用主鍵獲取對應(yīng)的行記錄赦抖。

示意圖如下：

3.png

2.3 總結(jié)

聚集索引表記錄的排列順序與索引的排列順序一致舱卡，優(yōu)點(diǎn)是查詢速度快，因?yàn)橐坏┚哂械谝粋€索引值的紀(jì)錄被找到队萤，具有連續(xù)索引值的記錄也一定物理的緊跟其后轮锥。

聚集索引的缺點(diǎn)是對表進(jìn)行修改速度較慢。為了保持表中的記錄的物理順序與索引的順序一致要尔，必須在數(shù)據(jù)頁中進(jìn)行數(shù)據(jù)重排舍杜，降低了執(zhí)行速度。

建議使用聚集索引的場合為：

• 此列包含有限數(shù)目的不同值
• 查詢的結(jié)果返回一個區(qū)間的值
• 查詢的結(jié)果返回某值相同的大量結(jié)果集

非聚集索引指定了表中記錄的邏輯順序赵辕，物理順序和索引的順序不一致既绩，所以往往需要回表進(jìn)行二次查詢才能定位到真正的記錄。

非聚集索引比聚集索引層次多还惠，添加記錄不會引起數(shù)據(jù)順序的重組饲握，所以修改操作要比聚集索引更加快速。

建議使用非聚集索引的場合為：

• 此列包含了大量數(shù)目不同的值
• 查詢的結(jié)束返回的是少量的結(jié)果集
• order by 子句中使用了該列

3、聯(lián)合索引

3.1 聯(lián)合索引的特性

聯(lián)合索引救欧，也稱復(fù)合索引衰粹，指由兩個或以上的字段共同構(gòu)成一個索引。

從本質(zhì)上來說笆怠，聯(lián)合索引也是一棵B+樹铝耻，不同的是聯(lián)合索引的鍵值數(shù)量不是1，而是大于等于2蹬刷。

例如瓢捉，有一個表使用兩個整形列a和b建立了聯(lián)合索引：

4.png

其實(shí)和單個鍵值的B+樹沒什么不同，鍵值都是排序的办成，通過葉子節(jié)點(diǎn)可以邏輯上順序地讀出所有數(shù)據(jù)泡态，就上面的例子來說，即(1,1)诈火、(1,2)兽赁、(2,1)状答、(2,4)冷守、(3,1)、(3,2)是按照先a后b的順序排列惊科。

3.2 最左前綴匹配原則

MySQL 建立聯(lián)合索引的規(guī)則是這樣的：它會首先根據(jù)聯(lián)合索引中最左邊的拍摇、也就是第一個字段進(jìn)行排序，在第一個字段排序的基礎(chǔ)上馆截，再對聯(lián)合索引中后面的第二個字段進(jìn)行排序充活，依此類推。

因此蜡娶，對于查詢

select * from table where a = xxx and b = xxx

顯然可以使用(a,b)這個聯(lián)合索引混卵。對于單個的a列查詢

select * from table where a = xxx

也可以使用這個聯(lián)合索引。但是對于b列的查詢

select * from table where b = xxx

則不可以使用這棵B+樹索引窖张，因?yàn)閎列的值1幕随、2、1宿接、4赘淮、1、2不是有序的睦霎。

綜上梢卸，第一個字段是絕對有序的，從第二個字段開始是無序的副女，這就解釋了為什么直接使用第二字段進(jìn)行條件判斷用不到索引了：從第二個字段開始蛤高，無序，無法走 B+ Tree 索引。

以上可以歸納為聯(lián)合索引的最左前綴匹配原則：

當(dāng)查詢條件精確匹配左邊連續(xù)一個或多個列時(shí)襟齿，索引可以被使用姻锁，但只能使用一部分

描述比較抽象，下面通過一個更詳細(xì)的例子來說明猜欺。

一個表test建有聯(lián)合索引index(a, b, c)位隶，則相當(dāng)于同時(shí)生效了index(1)、index(a, b)开皿、index(a, b, c)三個索引涧黄。不同查詢語句對應(yīng)的索引使用情況如下：

從形式上看就是索引向左側(cè)聚集，所以叫做最左前綴匹配原則赋荆，因此最常用的條件應(yīng)該放到聯(lián)合索引的最左側(cè)笋妥。

最左前綴匹配原則可以通過以下這幾個特性來理解：

• 聯(lián)合查詢條件符合“交換律”，也就是where a = 1 and b = 1 等價(jià)于 where b = 1 and a = 1窄潭。

• = 和 in 可以亂序春宣，比如針對查詢條件a = 3 and b = 4 and c = 5 ，index（a嫉你，b月帝，c）可以任意順序。

• 對于聯(lián)合索引幽污，MySQL 會一直向右匹配直到遇到范圍查詢（> 嚷辅， < ，between距误，like）就停止匹配簸搞。比如 a = 3 and b = 4 and c > 5 and d = 6，如果建立的是（a,b,c,d）這種順序的索引准潭，那么 d 是用不到索引的趁俊，但是如果建立的是 （a,b,d,c）這種順序的索引的話，那么就沒問題刑然，而且 a寺擂，b，d 的順序可以隨意調(diào)換闰集。

• 如果建立的索引順序是 （a沽讹，b）那么直接采用 where b = 5 這種查詢條件是無法利用到索引的，這一條最能體現(xiàn)最左匹配的特性武鲁。

3.3 ref與index

有點(diǎn)需要特別注意爽雄，針對上面的第4點(diǎn)，無法利用索引不是說查詢過程不會使用聯(lián)合索引沐鼠，而是達(dá)不到索引預(yù)期的效果挚瘟。仍然用一個例子說明叹谁。

對于聯(lián)合索引(col1,col2,col3)，查詢語句SELECT * FROM test WHERE col2=2;是否能夠觸發(fā)索引乘盖？
大多數(shù)人都會說NO焰檩，實(shí)際上卻是YES。

使用EXPLAIN來分析以下兩個語句：

`EXPLAIN ``SELECT` `* ``FROM` `test ``WHERE` `col2=2;``EXPLAIN ``SELECT` `* ``FROM` `test ``WHERE` `col1=1;`

觀察上述兩個explain結(jié)果中的type字段订框。查詢中分別是：

• type: index

  這種類型表示MySQL會對整個該索引進(jìn)行掃描析苫。只要是索引，或者某個聯(lián)合索引的一部分穿扳，MySQL都可能會采用index類型的方式掃描衩侥。不過效率不高，按索引次序掃描矛物，先讀索引茫死，再讀實(shí)際的行，結(jié)果還是全表掃描履羞，主要優(yōu)點(diǎn)是避免了排序峦萎，因?yàn)樗饕桥藕玫摹?/p>

• type: ref

  這種類型表示MySQL會根據(jù)特定的算法快速查找到某個符合條件的索引，而不是會對索引中每一個數(shù)據(jù)都進(jìn)行一一的掃描判斷忆首。而要想實(shí)現(xiàn)這種效果爱榔，索引索引就要滿足特定的數(shù)據(jù)結(jié)構(gòu)。簡單說雄卷，也就是索引字段的數(shù)據(jù)必須是有序的搓蚪，才能實(shí)現(xiàn)這種類型的查找蛤售，才能利用到索引丁鹉。

我們通常所說的“用到了索引”是狹義地指ref這種情況，也就是達(dá)到了快速查找的效果悴能。而index也會觸發(fā)索引揣钦，只是達(dá)不到快速查找的效果而已。

3.4 為什么要使用聯(lián)合索引

• 減少開銷

  建一個聯(lián)合索引(col1,col2,col3)漠酿，實(shí)際相當(dāng)于建了(col1),(col1,col2),(col1,col2,col3)三個索引冯凹。每多一個索引，都會增加寫操作的開銷和磁盤空間的開銷炒嘲。對于大量數(shù)據(jù)的表宇姚，使用聯(lián)合索引會大大的減少開銷

• 覆蓋索引

  對聯(lián)合索引(col1,col2,col3)，如果有如下的sql: select col1,col2,col3 from test where col1=1 and col2=2夫凸，那么MySQL可以直接通過遍歷索引取得數(shù)據(jù)浑劳，而無需回表，這減少了很多的隨機(jī)io操作夭拌。減少io操作魔熏，特別的隨機(jī)io其實(shí)是DBA主要的優(yōu)化策略衷咽。所以，在真正的實(shí)際應(yīng)用中蒜绽，覆蓋索引是主要的提升性能的優(yōu)化手段之一镶骗。

• 效率高

  索引列越多，通過索引篩選出的數(shù)據(jù)越少躲雅。有1000W條數(shù)據(jù)的表鼎姊，有如下sql:select from table where col1=1 and col2=2 and col3=3，假設(shè)假設(shè)每個條件可以篩選出10%的數(shù)據(jù)相赁，如果只有單值索引此蜈，那么通過該索引能篩選出1000w乘10%=100w條數(shù)據(jù)，然后再回表從100w條數(shù)據(jù)中找到符合col2=2 and col3= 3的數(shù)據(jù)噪生，然后再排序裆赵，再分頁；如果是聯(lián)合索引跺嗽，通過索引篩選出1000w乘10%乘10% 乘10%=1w战授，效率提升可想而知。

聯(lián)合索引的另一個好處是桨嫁，第二個列在小范圍內(nèi)有序植兰。雖然b列的值整體無序，但是當(dāng)a列限定為一個定值的時(shí)候璃吧，b列相對有序楣导。利用這個特性，在查詢中使用排序(DESC畜挨、ASC)筒繁、分組（GROUP BY）等語句時(shí)，可以免去一次filesort排序操作巴元。

對于聯(lián)合索引(a,b)毡咏，下列語句可以直接通過索引得到結(jié)果：

select ... from table where a = xxx order by b

對于聯(lián)合索引(a,b,c)來說，下列語句同樣可以直接通過索引得到結(jié)果：

select ... from table where a = xxx order by b

select ... from table where a = xxx and b = xxx order by c

但是對于下面的語句逮刨，聯(lián)合索引不能直接得到結(jié)果呕缭，還需要執(zhí)行一次filesort排序操作，因?yàn)樗饕?code>(a,c)并未排序：

select ... from table where a = xxx order by c

4修己、索引覆蓋

InnoDB支持索引覆蓋（covering index）恢总，即從輔助索引中就可以查詢到記錄，而不需要查詢聚集索引中的記錄睬愤。使用索引覆蓋的一個好處是輔助索引不包含整行記錄的所有信息片仿，故其大小要遠(yuǎn)小于聚集索引，可以減少大量的IO操作戴涝。

索引覆蓋的另一個好處是對于某些統(tǒng)計(jì)問題滋戳，如

select count(*) from table

如果有輔助索引钻蔑，InnoDB更傾向于選擇輔助索引，而非聚集索引來進(jìn)行統(tǒng)計(jì)奸鸯。

mysql> explain select count(*) from t\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t
   partitions: NULL
         type: index
possible_keys: NULL
          key: idx_c
      key_len: 4
          ref: NULL
         rows: 2
     filtered: 100.00
        Extra: Using index

possible_keys為NULL咪笑，但是實(shí)際執(zhí)行時(shí)優(yōu)化器卻選擇了indx_c索引，而Extra中的Using index表明優(yōu)化器進(jìn)行了索引覆蓋操作娄涩。

表中有a窗怒、b列的聯(lián)合索引時(shí)，如果對b列進(jìn)行了查詢過濾蓄拣，一般是無法利用索引的扬虚，但是如果是統(tǒng)計(jì)操作，并且可以利用索引覆蓋球恤，優(yōu)化器會選擇該聯(lián)合索引辜昵，如

select count(*) from table where b < 100 and b> 0

5、 Cardinality

對于什么時(shí)候添加B+樹索引咽斧，一般的經(jīng)驗(yàn)是堪置，在訪問表中很少一部分時(shí)使用B+樹索引才有意義。比如對于性別、省份、學(xué)歷等字段可取值范圍很小幽崩，稱為低選擇性。如

SELECT * FROM student WHERE sex='M'

按性別進(jìn)行查詢時(shí)坎匿，可取值一般只有M、F雷激。因此SQL語句得到的結(jié)果可能是該表50%的數(shù)據(jù)替蔬，這時(shí)添加B+樹索引是完全沒有必要的。相反侥锦，如果某個字段的取值范圍很廣进栽，幾乎沒有重復(fù)德挣，屬于高選擇性恭垦。則此時(shí)使用B+樹的索引是最合適的。例如手機(jī)號格嗅、郵箱番挺，基本上在一個應(yīng)用中不允許重復(fù)出現(xiàn)。

可以使用命令show index查看Cardinality信息：

mysql> show index from t\G;
*************************** 1. row ***************************
        Table: t
   Non_unique: 0
     Key_name: PRIMARY
 Seq_in_index: 1
  Column_name: a
    Collation: A
  Cardinality: 2
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:

• Table：表的名稱
• Non_unique：索引是否唯一屯掖，如果可以玄柏，則為1的，否則贴铜，為0
• Key_name：索引的名稱
• Seq_in_index：索引中的列序列號粪摘，從1開始
• Column_name：列名稱
• Collation：列以什么方式存儲在索引中瀑晒。在MySQL中，有值‘A’（升序）或NULL（無分類）
• Cardinality：索引中唯一值的估計(jì)數(shù)量徘意。通過運(yùn)行ANALYZE TABLE可以更新
• Sub_part：如果列只是被部分地編入索引苔悦，則為被編入索引的字符的數(shù)目。如果整列被編入索引椎咧，則為NULL
• Packed：關(guān)鍵字如何被壓縮玖详。如果沒有被壓縮，則為NULL
• Null：如果列含有NULL勤讽，則含有YES蟋座。如果沒有，則該列含有NO
• Index_type：索引類型脚牍，InnoDB只會是BTREE
• Comment ：注釋

Cardinality值非常關(guān)鍵向臀，表示索引中不重復(fù)記錄數(shù)量的預(yù)估值，優(yōu)化器會根據(jù)這個值來判斷是否使用這個索引诸狭。在實(shí)際應(yīng)用中飒硅，Cardinality應(yīng)該盡可能接近數(shù)據(jù)行的總數(shù)，如果遠(yuǎn)小于數(shù)據(jù)行總數(shù)作谚，那么就需要考慮是否還有必要創(chuàng)建這個索引三娩。

如果每次索引在發(fā)生更改就對Cardinality進(jìn)行更新，將會給數(shù)據(jù)庫帶來很大的負(fù)擔(dān)妹懒。因此雀监，數(shù)據(jù)庫對于Cardinality的統(tǒng)計(jì)都是通過采樣的方法來完成的。

InnoDB對更新Cardinality的策略為：

• 表中1/16的數(shù)據(jù)已發(fā)生過變化
• stat_modified_counter > 20億眨唬。

第二種情況考慮的是会前，如果對表中某一行數(shù)據(jù)頻繁地更新操作，表中有過改變的行記錄總數(shù)并沒有發(fā)生變化匾竿。故在InnoDB內(nèi)部有一個stat_modified_counter 計(jì)數(shù)器瓦宜，用來表示發(fā)生變化的次數(shù)。

在InnoDB中岭妖，Cardinality的采樣方法為：隨機(jī)選取8個葉子節(jié)點(diǎn)临庇，計(jì)算其平均數(shù)據(jù)量，然后乘以葉子節(jié)點(diǎn)總數(shù)昵慌。