一、索引基本知識

1.1 索引的優(yōu)點

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

1.2 索引的用處

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

1.3  索引的分類

數(shù)據(jù)庫會默認創(chuàng)建索引，但是并不是給主鍵建立索引，而是給唯一鍵建立索引的，因為主鍵的特性是唯一且非空

• 主鍵索引： 是一種特殊的唯一索引，不允許有空值。（主鍵約束，就是一個主鍵索引）
• 唯一索引： 索引列中的值必須是唯一的，但是允許為空值。
• 普通索引： MySQL中基本索引類型，沒有什么限制，允許在定義索引的列中插入重復值和空值，純粹為了查詢數(shù)據(jù)更快一 點。
• 全文索引： 只有在MyISAM引擎上才能使用，只能在CHAR,VARCHAR,TEXT類型字段上使用全文索引
  >什么是全文索引，就是在一堆文字中，通過其中的某個關鍵字等，就能找到該字段所屬的記錄行，比如有"LOL LPL 牧小農" 通過牧小農，可能就可以找到該條記錄。這里說的是可能，因為全文索引的使用涉及了很多細節(jié)，我們只需要知道這個大概意思。一般開發(fā)中，不會用到全文索引，因為其占用很大的物理空間和降低了記錄修改性，故較為少用。
• 組合索引： 在表中的多個字段組合上創(chuàng)建的索引，只有在查詢條件中使用了這些字段的左邊字段時，索引才會被使用，使用組合索引時遵循最左前綴集合。

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

1.4  面試技術名詞

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

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

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

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提供的用某一個索引對一個特定的表從表中獲取元組”，注意我們這里特意強調了“一個”，這是因為這樣的索引優(yōu)化不是用于多表連接而是用于單表掃描，確切地說，是單表利用索引進行掃描以獲取數(shù)據(jù)的一種方式。

1.5  索引采用的數(shù)據(jù)結構

1.5.1 哈希表

缺點︰

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

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

1.5.2 二叉樹

缺點∶

無論是二叉樹還是紅黑樹，都會因為樹的深度過深而造成io次數(shù)變多，影響數(shù)據(jù)讀取的效率

1.5.3 B+樹

B樹特點:

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

2、搜索有可能在非葉子結點結束，在關鍵字全集內做一次查找,性能逼近二分查找

3、每個節(jié)點最多擁有m個子樹

4、根節(jié)點至少有2個子樹

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

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

實例圖說明∶

每個節(jié)點占用一個磁盤塊，一個節(jié)點上有兩個升序排序的關鍵字和三個指向子樹根節(jié)點的指針，指針存儲的是子節(jié)點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點為例，關鍵字為16和34，P1指針指向的子樹的數(shù)據(jù)范圍為小于16,P2指針指向的子樹的數(shù)據(jù)范圍為16~34 ,P3指針指向的子樹的數(shù)據(jù)范圍為大于34。

查找關鍵字過程:

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

缺點:

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

1.6  索引匹配方式

全值匹配： 全值匹配指的是和索引中的所有列進行匹配

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

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

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

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

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

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

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

二、哈希索引

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

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

哈希索引自身只需存儲對應的hash值，所以索引的結構十分緊湊，這讓哈希索引查找的速度非常快

2.1 哈希索引的限制

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

2.2 案例

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

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

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

三、組合索引

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

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