一、索引基本知識(shí)

1.1 索引的優(yōu)點(diǎn)

1. 大大減少了服務(wù)器需要掃描的數(shù)據(jù)量，加快數(shù)據(jù)庫的檢索速度
2. 幫助服務(wù)器避免排序和臨時(shí)表
3. 將隨機(jī)io變成順序io

1.2 索引的用處

1. 速查找匹配WHERE子句的行
2. 從consideration中消除行,如果可以在多個(gè)索引之間進(jìn)行選擇，mysql通常會(huì)使用找到最少行的索引
3. 如果表具有多列索引，則優(yōu)化器可以使用索引的任何最左前綴來查找行
4. 當(dāng)有表連接的時(shí)候，從其他表檢索行數(shù)據(jù)
5. 查找特定索引列的min或max值
6. 如果排序或分組時(shí)在可用索引的最左前綴上完成的，則對(duì)表進(jìn)行排序和分組
7. 在某些情況下，可以優(yōu)化查詢以檢索值而無需查詢數(shù)據(jù)行

1.3 索引的分類

數(shù)據(jù)庫會(huì)默認(rèn)創(chuàng)建索引，但是并不是給主鍵建立索引，而是給唯一鍵建立索引的，因?yàn)橹麈I的特性是唯一且非空

主鍵索引： 是一種特殊的唯一索引，不允許有空值。(主鍵約束，就是一個(gè)主鍵索引)

唯一索引： 索引列中的值必須是唯一的，但是允許為空值。

普通索引： MySQL中基本索引類型，沒有什么限制，允許在定義索引的列中插入重復(fù)值和空值，純粹為了查詢數(shù)據(jù)更快一 點(diǎn)。

全文索引： 只有在MyISAM引擎上才能使用，只能在CHAR,VARCHAR,TEXT類型字段上使用全文索引

>什么是全文索引，就是在一堆文字中，通過其中的某個(gè)關(guān)鍵字等，就能找到該字段所屬的記錄行，比如有"LOL LPL 牧小農(nóng)" 通過牧小農(nóng)，可能就可以找到該條記錄。這里說的是可能，因?yàn)槿乃饕氖褂蒙婕傲撕芏嗉?xì)節(jié)，我們只需要知道這個(gè)大概意思。一般開發(fā)中，不會(huì)用到全文索引，因?yàn)槠湔加煤艽蟮奈锢砜臻g和降低了記錄修改性，故較為少用。

組合索引： 在表中的多個(gè)字段組合上創(chuàng)建的索引，只有在查詢條件中使用了這些字段的左邊字段時(shí)，索引才會(huì)被使用，使用組合索引時(shí)遵循最左前綴集合。

例如這里由id、name和age3個(gè)字段構(gòu)成的索引，索引行中就按id/name/age的順序存放，索引可以索引下面字段組合(id，name，age)、(id，name)或者(id)。如果要查詢的字段不構(gòu)成索引最左面的前綴，那么就不會(huì)使用索引，比如，age或者(name，age)組合就不會(huì)使用索引查詢。

1.4 面試技術(shù)名詞

回表： 數(shù)據(jù)庫根據(jù)索引(非主鍵)找到了指定的記錄所在行后，還需要根據(jù)主鍵再次到數(shù)據(jù)塊里獲取數(shù)據(jù)，這種稱之為回表

覆蓋索引： 看我寫的一篇文章：面試三輪我倒在了一道sql題上——sql性能優(yōu)化

最左匹配： 指在聯(lián)合索引中，如果你的 SQL 語句中用到了聯(lián)合索引中的最左邊的索引，那么這條 SQL 語句就可以利用這個(gè)聯(lián)合索引去進(jìn)行匹配，如果遇到范圍查詢(>、<、between、like)就會(huì)停止匹配。

select * from t where a=1 and b=1 and c =1;     #這樣可以利用到定義的索引（a,b,c）,用上a,b,c 
select * from t where a=1 and b=1;     #這樣可以利用到定義的索引（a,b,c）,用上a,b 
select * from t where b=1 and a=1;     #這樣可以利用到定義的索引（a,b,c）,用上a,c（mysql有查詢優(yōu)化器） 
select * from t where a=1;     #這樣也可以利用到定義的索引（a,b,c）,用上a 
select * from t where b=1 and c=1;     #這樣不可以利用到定義的索引（a,b,c） 
select * from t where a=1 and c=1;     #這樣可以利用到定義的索引（a,b,c），但只用上a索引，b,c索引用不到 

索引下推： 稱為 Index Condition Pushdown (ICP)，這是MySQL提供的用某一個(gè)索引對(duì)一個(gè)特定的表從表中獲取元組”，注意我們這里特意強(qiáng)調(diào)了“一個(gè)”，這是因?yàn)檫@樣的索引優(yōu)化不是用于多表連接而是用于單表掃描，確切地說，是單表利用索引進(jìn)行掃描以獲取數(shù)據(jù)的一種方式。

1.5 索引采用的數(shù)據(jù)結(jié)構(gòu)

1.5.1 哈希表

缺點(diǎn)︰

1、利用hash存儲(chǔ)的話需要將所有的數(shù)據(jù)文件添加到內(nèi)存，比較耗費(fèi)內(nèi)存空間

2、如果所有的查詢都是等值查詢，那么hash確實(shí)很快，但是在企業(yè)或者實(shí)際工作環(huán)境中范圍查找的數(shù)據(jù)更多，而不是等值查詢，因此hash就不太適合了

1.5.2 二叉樹

缺點(diǎn)∶

無論是二叉樹還是紅黑樹，都會(huì)因?yàn)闃涞纳疃冗^深而造成io次數(shù)變多，影響數(shù)據(jù)讀取的效率

1.5.3 B+樹

B樹特點(diǎn):

1、所有鍵值分布在整顆樹中

2、搜索有可能在非葉子結(jié)點(diǎn)結(jié)束，在關(guān)鍵字全集內(nèi)做一次查找,性能逼近二分查找

3、每個(gè)節(jié)點(diǎn)最多擁有m個(gè)子樹

4、根節(jié)點(diǎn)至少有2個(gè)子樹

5、分支節(jié)點(diǎn)至少擁有m/2顆子樹(除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外都是分支節(jié)點(diǎn))

6、所有葉子節(jié)點(diǎn)都在同一層、每個(gè)節(jié)點(diǎn)最多可以有m-1個(gè)key，并且以升序排列

實(shí)例圖說明∶

每個(gè)節(jié)點(diǎn)占用一個(gè)磁盤塊，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹根節(jié)點(diǎn)的指針，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤塊的地址。兩個(gè)關(guān)鍵詞劃分成的三個(gè)范圍域?qū)?yīng)三個(gè)指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點(diǎn)為例，關(guān)鍵字為16和34，P1指針指向的子樹的數(shù)據(jù)范圍為小于16,P2指針指向的子樹的數(shù)據(jù)范圍為16~34 ,P3指針指向的子樹的數(shù)據(jù)范圍為大于34。

查找關(guān)鍵字過程:

1. 根據(jù)根節(jié)點(diǎn)找到磁盤塊1，讀入內(nèi)存?！敬疟PI/O操作第1次】
2. 比較關(guān)鍵字28在區(qū)間(16,34 )，找到磁盤塊1的指針P2。
3. 根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存?！敬疟PI/O操作第2次】
4. 比較關(guān)鍵字28在區(qū)間(25,31 )，找到磁盤塊3的指針P2。
5. 根據(jù)P2指針找到磁盤塊8，讀入內(nèi)存?！敬疟PI/O 操作第3次】
6. 在磁盤塊8中的關(guān)健寧列表中找到關(guān)健字28。

缺點(diǎn):

• 每個(gè)節(jié)點(diǎn)都有key，同時(shí)也包含data，而每個(gè)頁存儲(chǔ)空間是有限的，如果data比較大的話會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)存儲(chǔ)的k ey數(shù)量變小
• 當(dāng)存儲(chǔ)的數(shù)據(jù)量很大的時(shí)候會(huì)導(dǎo)致深度較大，增大查詢時(shí)磁盤io次數(shù)，進(jìn)而影響查詢性能

1.6 索引匹配方式

全值匹配： 全值匹配指的是和索引中的所有列進(jìn)行匹配

explain select * from staffs where name = 'July' and age = '23' and pos = 'dev'; 

匹配最左前綴： 只匹配前面的幾列

explain select * from staffs where name = 'July' and age = '23'; 
 
explain select * from staffs where name = 'July'; 

匹配列前綴： 可以匹配某一列的值的開頭部分

explain select * from staffs where name like 'J%'; 
 
explain select * from staffs where name like '%y'; 

匹配范圍值： 可以查找某一個(gè)范圍的數(shù)據(jù)

explain select * from staffs where name > 'Mary'; 

精確匹配某一列并范圍匹配另外一列：可以查詢第一列的全部和第二列的部分

explain select * from staffs where name = 'July' and age > 25; 

只訪問索引的查詢： 查詢的時(shí)候只需要訪問索引，不需要訪問數(shù)據(jù)行，本質(zhì)上就是覆蓋索引

explain select name,age,pos from staffs where name = 'July' and age = 25 and pos = 'dev'; 

二、哈希索引

• 基于哈希表的實(shí)現(xiàn)，只有精確匹配索引所有列的查詢才有效
• 在mysql中，只有memory的存儲(chǔ)引擎顯式支持哈希索引
• 哈希索引自身只需存儲(chǔ)對(duì)應(yīng)的hash值，所以索引的結(jié)構(gòu)十分緊湊，這讓哈希索引查找的速度非?？?/li>

2.1 哈希索引的限制

1. 哈希索引只包含哈希值和行指針，而不存儲(chǔ)字段值，索引不能使用索引中的值來避免讀取行
2. 哈希索引數(shù)據(jù)并不是按照索引值順序存儲(chǔ)的，所以無法進(jìn)行排序
3. 哈希索引不支持部分列匹配查找，哈希索引是使用索引列的全部?jī)?nèi)容來計(jì)算哈希值
4. 哈希索引支持等值比較查詢，也不支持任何范圍查詢
5. 訪問哈希索引的數(shù)據(jù)非?？?，除非有很多哈希沖突，當(dāng)出現(xiàn)哈希沖突的時(shí)候，存儲(chǔ)引擎必須遍歷鏈表中的所有行指針，逐行進(jìn)行比較，直到找到所有符合條件的行
6. 哈希沖突比較多的話，維護(hù)的代價(jià)也會(huì)很高

2.2 案例

當(dāng)需要存儲(chǔ)大量的URL，并且根據(jù)URL進(jìn)行搜索查找，如果使用B+樹，存儲(chǔ)的內(nèi)容就會(huì)很大：select id from url where url=""

也可以利用將url使用CRC32做哈希，可以使用以下查詢方式：select id fom url where url="" and url_crc=CRC32("")

此查詢性能較高原因是使用體積很小的索引來完成查找

三、組合索引

當(dāng)包含多個(gè)列作為索引，需要注意的是正確的順序依賴于該索引的查詢，同時(shí)需要考慮如何更好的滿足排序和分組的需要

案例： 建立組合索引 a,b,c ，不同SQL語句使用索引情況

四、聚簇索引與非聚簇索引

4.1 聚簇索引

• 不是單獨(dú)的索引類型，而是一種數(shù)據(jù)存儲(chǔ)方式，指的是數(shù)據(jù)行跟相鄰的鍵值緊湊的存儲(chǔ)在一起，將數(shù)據(jù)存儲(chǔ)與索引放到了一塊，找到索引也就找到了數(shù)據(jù)
• 如果沒有定義主鍵，InnoDB會(huì)選擇一個(gè)唯一的非空索引代替。如果沒有唯一索引，InnoDB會(huì)隱式定義一個(gè)主鍵來作為聚簇索引。InnoDB 只聚集在同一個(gè)頁面中的記錄。包含相鄰鍵值的頁面可能相距甚遠(yuǎn)。

4.2 非聚簇索引

• 數(shù)據(jù)文件跟索引文件分開存放，將數(shù)據(jù)存儲(chǔ)于索引分開結(jié)構(gòu)，索引結(jié)構(gòu)的葉子節(jié)點(diǎn)指向了數(shù)據(jù)的對(duì)應(yīng)行，myisam通過key_buffer把索引先緩存到內(nèi)存中，當(dāng)需要訪問數(shù)據(jù)時(shí)(通過索引訪問數(shù)據(jù))，在內(nèi)存中直接搜索索引，然后通過索引找到磁盤相應(yīng)數(shù)據(jù)，這也就是為什么索引不在key buffer命中時(shí)，速度慢的原因
• 通過葉子節(jié)點(diǎn)指針找到數(shù)據(jù)頁中的數(shù)據(jù)，所以非聚簇索引是邏輯順序

五、覆蓋索引

5.1 基本介紹

1. 如果一個(gè)索引包含所有需要查詢的字段的值，我們稱之為覆蓋索引
2. 不是所有類型的索引都可以稱為覆蓋索引，覆蓋索引必須要存儲(chǔ)索引列的值
3. 不同的存儲(chǔ)實(shí)現(xiàn)覆蓋索引的方式不同，不是所有的引擎都支持覆蓋索引，memory不支持覆蓋索引

5.2 優(yōu)勢(shì)

1、索引條目通常遠(yuǎn)小于數(shù)據(jù)行大小，如果只需要讀取索引，那么mysql就會(huì)極大的較少數(shù)據(jù)訪問量

2、因?yàn)樗饕前凑樟兄淀樞虼鎯?chǔ)的，所以對(duì)于IO密集型的范圍查詢會(huì)比隨機(jī)從磁盤讀取每一行數(shù)據(jù)的IO要少的多

3、一些存儲(chǔ)引擎如MYISAM在內(nèi)存中只緩存索引，數(shù)據(jù)則依賴于操作系統(tǒng)來緩存，因此要訪問數(shù)據(jù)需要一次系統(tǒng)調(diào)用，這可能會(huì)導(dǎo)致嚴(yán)重的性能問題

4、由于INNODB的聚簇索引，覆蓋索引對(duì)INNODB表特別有用

5.3 案例演示

1、當(dāng)發(fā)起一個(gè)被索引覆蓋的查詢時(shí)，在explain的extra列可以看到using index的信息，此時(shí)就使用了覆蓋索引

2、在大多數(shù)存儲(chǔ)引擎中，覆蓋索引只能覆蓋那些只訪問索引中部分列的查詢。不過，可以進(jìn)一步的進(jìn)行優(yōu)化，可以使用innodb的二級(jí)索引來覆蓋查詢。

例如：actor使用innodb存儲(chǔ)引擎，并在last_name字段有二級(jí)索引，雖然該索引的列不包括主鍵actor_id，但也能夠用于對(duì)actor_id做覆蓋查詢

六、優(yōu)化小細(xì)節(jié)

• 當(dāng)使用索引列進(jìn)行查詢的時(shí)候盡量不要使用表達(dá)式，把計(jì)算放到業(yè)務(wù)層而不是數(shù)據(jù)庫層
• 盡量使用主鍵查詢，而不是其他索引，因?yàn)橹麈I查詢不會(huì)觸發(fā)回表查詢
• 使用前綴索引

>有時(shí)候需要索引很長(zhǎng)的字符串，這會(huì)讓索引變的大且慢，通常情況下可以使用某個(gè)列開始的部分字符串，這樣大大的節(jié)約索引空間，從而提高索引效率，但這會(huì)降低索引的選擇性，索引的選擇性是指不重復(fù)的索引值和數(shù)據(jù)表記錄總數(shù)的比值，范圍從1/#T到1之間。索引的選擇性越高則查詢效率越高，因?yàn)檫x擇性更高的索引可以讓mysql在查找的時(shí)候過濾掉更多的行。

一般情況下某個(gè)列前綴的選擇性也是足夠高的，足以滿足查詢的性能，但是對(duì)應(yīng)BLOB,TEXT,VARCHAR類型的列，必須要使用前綴索引，因?yàn)閙ysql不允許索引這些列的完整長(zhǎng)度，使用該方法的訣竅在于要選擇足夠長(zhǎng)的前綴以保證較高的選擇性，通過又不能太長(zhǎng)。

--創(chuàng)建數(shù)據(jù)表 
create table citydemo(city varchar(50) not null); 
insert into citydemo(city) select city from city; 
 
--重復(fù)執(zhí)行5次下面的sql語句 
insert into citydemo(city) select city from citydemo; 
 
--更新城市表的名稱 
update citydemo set city=(select city from city order by rand() limit 1); 
 
--查找最常見的城市列表，發(fā)現(xiàn)每個(gè)值都出現(xiàn)45-65次， 
select count(*) as cnt,city from citydemo group by city order by cnt desc limit 10; 
 
--查找最頻繁出現(xiàn)的城市前綴，先從3個(gè)前綴字母開始，發(fā)現(xiàn)比原來出現(xiàn)的次數(shù)更多，可以分別截取多個(gè)字符查看城市出現(xiàn)的次數(shù) 
select count(*) as cnt,left(city,3) as pref from citydemo group by pref order by cnt desc limit 10; 
select count(*) as cnt,left(city,7) as pref from citydemo group by pref order by cnt desc limit 10; 
--此時(shí)前綴的選擇性接近于完整列的選擇性 
 
--還可以通過另外一種方式來計(jì)算完整列的選擇性，可以看到當(dāng)前綴長(zhǎng)度到達(dá)7之后，再增加前綴長(zhǎng)度，選擇性提升的幅度已經(jīng)很小了 
select count(distinct left(city,3))/count(*) as sel3, 
count(distinct left(city,4))/count(*) as sel4, 
count(distinct left(city,5))/count(*) as sel5, 
count(distinct left(city,6))/count(*) as sel6, 
count(distinct left(city,7))/count(*) as sel7, 
count(distinct left(city,8))/count(*) as sel8  
from citydemo; 
 
--計(jì)算完成之后可以創(chuàng)建前綴索引 
alter table citydemo add key(city(7)); 
 
--注意：前綴索引是一種能使索引更小更快的有效方法，但是也包含缺點(diǎn)：mysql無法使用前綴索引做order by 和 group by。  

• 使用索引掃描來排序

mysql有兩種方式可以生成有序的結(jié)果：通過排序操作或者按索引順序掃描，如果explain出來的type列的值為index,則說明mysql使用了索引掃描來做排序

掃描索引本身是很快的，因?yàn)橹恍枰獜囊粭l索引記錄移動(dòng)到緊接著的下一條記錄。但如果索引不能覆蓋查詢所需的全部列，那么就不得不每掃描一條索引記錄就得回表查詢一次對(duì)應(yīng)的行，這基本都是隨機(jī)IO，因此按索引順序讀取數(shù)據(jù)的速度通常要比順序地全表掃描慢

mysql可以使用同一個(gè)索引即滿足排序，又用于查找行，如果可能的話，設(shè)計(jì)索引時(shí)應(yīng)該盡可能地同時(shí)滿足這兩種任務(wù)。

只有當(dāng)索引的列順序和order by子句的順序完全一致，并且所有列的排序方式都一樣時(shí)，mysql才能夠使用索引來對(duì)結(jié)果進(jìn)行排序，如果查詢需要關(guān)聯(lián)多張表，則只有當(dāng)orderby子句引用的字段全部為第一張表時(shí)，才能使用索引做排序。order by子句和查找型查詢的限制是一樣的，需要滿足索引的最左前綴的要求，否則，mysql都需要執(zhí)行順序操作，而無法利用索引排序

• union all,in,or都能夠使用索引，但是推薦使用in
• 范圍列可以用到索引，范圍條件是：<、>,范圍列可以用到索引，但是范圍列后面的列無法用到索引，索引最多用于一個(gè)范圍列
• 強(qiáng)制類型轉(zhuǎn)換會(huì)全表掃描

create table user(id int,name varchar(10),phone varchar(11)); 
alter table user add index idx_1(phone); 
explain select * from user where phone=13800001234;(不會(huì)觸發(fā)索引) 
explain select * from user where phone='13800001234';(觸發(fā)索引) 

• 更新十分頻繁，數(shù)據(jù)區(qū)分度不高的字段上不宜建立索引

更新會(huì)變更B+樹，更新頻繁的字段建議索引會(huì)大大降低數(shù)據(jù)庫性能.

類似于性別這類區(qū)分不大的屬性，建立索引是沒有意義的，不能有效的過濾數(shù)據(jù)，

一般區(qū)分度在80%以上的時(shí)候就可以建立索引，區(qū)分度可以使用 count(distinct(列名))/count(*) 來計(jì)算

• 創(chuàng)建索引的列，不允許為null，可能會(huì)得到不符合預(yù)期的結(jié)果
• 當(dāng)需要進(jìn)行表連接的時(shí)候，最好不要超過三張表，因?yàn)樾枰猨oin的字段，數(shù)據(jù)類型必須一致
• 能使用limit的時(shí)候盡量使用limit
• 單表索引建議控制在5個(gè)以內(nèi)
• 單索引字段數(shù)不允許超過5個(gè)(組合索引)
• 創(chuàng)建索引的時(shí)候應(yīng)該避免以下錯(cuò)誤概念

> 索引越多越好(錯(cuò)誤)

> 過早優(yōu)化，在不了解系統(tǒng)的情況下進(jìn)行優(yōu)化(錯(cuò)誤)