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

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

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

1.2 索引的用處

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

1.3  索引的分類(lèi)

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

• 主鍵索引： 是一種特殊的唯一索引，不允許有空值。（主鍵約束，就是一個(gè)主鍵索引）
• 唯一索引： 索引列中的值必須是唯一的，但是允許為空值。
• 普通索引： MySQL中基本索引類(lèi)型，沒(méi)有什么限制，允許在定義索引的列中插入重復(fù)值和空值，純粹為了查詢(xún)數(shù)據(jù)更快一 點(diǎn)。
• 全文索引： 只有在MyISAM引擎上才能使用，只能在CHAR,VARCHAR,TEXT類(lèi)型字段上使用全文索引
  >什么是全文索引，就是在一堆文字中，通過(guò)其中的某個(gè)關(guān)鍵字等，就能找到該字段所屬的記錄行，比如有"LOL LPL 牧小農(nóng)" 通過(guò)牧小農(nóng)，可能就可以找到該條記錄。這里說(shuō)的是可能，因?yàn)槿乃饕氖褂蒙婕傲撕芏嗉?xì)節(jié)，我們只需要知道這個(gè)大概意思。一般開(kāi)發(fā)中，不會(huì)用到全文索引，因?yàn)槠湔加煤艽蟮奈锢砜臻g和降低了記錄修改性，故較為少用。
• 組合索引： 在表中的多個(gè)字段組合上創(chuàng)建的索引，只有在查詢(xún)條件中使用了這些字段的左邊字段時(shí)，索引才會(huì)被使用，使用組合索引時(shí)遵循最左前綴集合。

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

1.4  面試技術(shù)名詞

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

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

最左匹配： 指在聯(lián)合索引中，如果你的 SQL 語(yǔ)句中用到了聯(lián)合索引中的最左邊的索引，那么這條 SQL 語(yǔ)句就可以利用這個(gè)聯(lián)合索引去進(jìn)行匹配，如果遇到范圍查詢(xú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有查詢(xún)優(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索引用不到

索引下推： 稱(chēng)為 Index Condition Pushdown (ICP)，這是MySQL提供的用某一個(gè)索引對(duì)一個(gè)特定的表從表中獲取元組”，注意我們這里特意強(qiáng)調(diào)了“一個(gè)”，這是因?yàn)檫@樣的索引優(yōu)化不是用于多表連接而是用于單表掃描，確切地說(shuō)，是單表利用索引進(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、如果所有的查詢(xún)都是等值查詢(xún)，那么hash確實(shí)很快，但是在企業(yè)或者實(shí)際工作環(huán)境中范圍查找的數(shù)據(jù)更多，而不是等值查詢(xún)，因此hash就不太適合了

1.5.2 二叉樹(shù)

缺點(diǎn)∶

無(wú)論是二叉樹(shù)還是紅黑樹(shù)，都會(huì)因?yàn)闃?shù)的深度過(guò)深而造成io次數(shù)變多，影響數(shù)據(jù)讀取的效率

1.5.3 B+樹(shù)

B樹(shù)特點(diǎn):

1、所有鍵值分布在整顆樹(shù)中

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

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

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

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

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

實(shí)例圖說(shuō)明∶

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

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

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

缺點(diǎn):

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

匹配列前綴： 可以匹配某一列的值的開(kāi)頭部分

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';

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

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

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

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

二、哈希索引

基于哈希表的實(shí)現(xiàn)，只有精確匹配索引所有列的查詢(xún)才有效

在mysql中，只有memory的存儲(chǔ)引擎顯式支持哈希索引

哈希索引自身只需存儲(chǔ)對(duì)應(yīng)的hash值，所以索引的結(jié)構(gòu)十分緊湊，這讓哈希索引查找的速度非?？?/p>

2.1 哈希索引的限制

1. 哈希索引只包含哈希值和行指針，而不存儲(chǔ)字段值，索引不能使用索引中的值來(lái)避免讀取行
2. 哈希索引數(shù)據(jù)并不是按照索引值順序存儲(chǔ)的，所以無(wú)法進(jìn)行排序
3. 哈希索引不支持部分列匹配查找，哈希索引是使用索引列的全部?jī)?nèi)容來(lái)計(jì)算哈希值
4. 哈希索引支持等值比較查詢(xún)，也不支持任何范圍查詢(xún)
5. 訪問(wèn)哈希索引的數(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+樹(shù)，存儲(chǔ)的內(nèi)容就會(huì)很大：select id from url where url=""

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

此查詢(xún)性能較高原因是使用體積很小的索引來(lái)完成查找

三、組合索引

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

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