數(shù)據(jù)庫(kù)索引在平時(shí)的工作是必備的，怎么建好索引，怎么使用索引，可以提高數(shù)據(jù)的查詢效率。而且在面試過(guò)程，數(shù)據(jù)庫(kù)的索引也是必問的知識(shí)點(diǎn)，比如：

索引底層結(jié)構(gòu)選型，那為什么選擇B+樹?

不同存儲(chǔ)引擎的索引的體現(xiàn)形式有哪些?

索引的類型

• 組合索引存儲(chǔ)方式
• 查詢方式
• 最左前綴匹配原則

覆蓋索引是什么?

看著這些，能說(shuō)出多少，理解多少呢?因此我們需要去探究其內(nèi)在原理。

那索引是什么?

索引的目的為了加速檢索數(shù)據(jù)而設(shè)計(jì)的一種分散存儲(chǔ)(索引常常很大，屬于硬盤級(jí)的東西，所以是分散存儲(chǔ))的數(shù)據(jù)結(jié)構(gòu),其原理以空間換時(shí)間。

快速檢索的實(shí)現(xiàn)的本質(zhì)是數(shù)據(jù)結(jié)構(gòu)，通過(guò)不同數(shù)據(jù)結(jié)構(gòu)的選擇，實(shí)現(xiàn)各種數(shù)據(jù)快速檢索，索引有哈希索引和B+樹索引。

索引底層結(jié)構(gòu)選型，那為什么選擇B+樹?

數(shù)據(jù)庫(kù)索引底層選型歸根到底就是為提高檢索效率，那么就需要考慮幾個(gè)問題：

• 算法時(shí)間復(fù)雜度
• 是否存在排序
• 磁盤IO與預(yù)讀

NOTE： 考慮到磁盤IO是非常高昂的操作，計(jì)算機(jī)操作系統(tǒng)做了一些優(yōu)化，當(dāng)一次IO時(shí)，不光把當(dāng)前磁盤地址的數(shù)據(jù)，而是把相鄰的數(shù)據(jù)也都讀取到內(nèi)存緩沖區(qū)內(nèi)，因?yàn)榫植款A(yù)讀性原理告訴我們，當(dāng)計(jì)算機(jī)訪問一個(gè)地址的數(shù)據(jù)的時(shí)候，與其相鄰的數(shù)據(jù)也會(huì)很快被訪問到。每一次IO讀取的數(shù)據(jù)我們稱之為一頁(yè)(page)。

哈希表( Hash Table,散列表 )

哈希表是根據(jù)鍵(Key)而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。

通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問記錄，這加快了查找速度。雖然查詢時(shí)間復(fù)雜度為O(1)，但存在著碰撞問題，最壞情況會(huì)導(dǎo)致時(shí)間復(fù)雜急劇增加;

而且哈希表其只適合精準(zhǔn)key(等于)檢索，不適合范圍式檢索，范圍檢索就需要一次把所有數(shù)據(jù)找出來(lái)加載到內(nèi)存，沒有效率，因此不適合Mysql的底層索引的數(shù)據(jù)結(jié)構(gòu)。

普通的二叉查找樹

為了優(yōu)化高效范圍查詢，且時(shí)間復(fù)雜度小，引入二叉查找樹

二叉查找樹的時(shí)間復(fù)雜度是 O(lgn)，由于數(shù)據(jù)已排序好了，所以范圍查詢是可以高效查詢，

但會(huì)存在的問題：左右子節(jié)點(diǎn)的深度可能相差很大，最極端的情況只有左子樹或者右子樹，此時(shí)查找的效率為O(n)，檢索性能急劇下降，因此也不適合Mysql的底層索引的數(shù)據(jù)結(jié)構(gòu)。

平衡二叉樹(AVL樹)

為了優(yōu)化二叉樹左右子樹深度相差太大的問題，我們引入了平衡二叉樹，即左右子節(jié)點(diǎn)的深度差不超過(guò)1，平衡二叉樹看來(lái)好像適合，實(shí)現(xiàn)了：

• 范圍查找、數(shù)據(jù)排序
• 查詢性能良好O(logn)

NOTE:上圖中一個(gè)磁盤塊，代表硬盤上的一個(gè)存儲(chǔ)位置

但是我們還有一個(gè)最重要因素需要考慮，磁盤IO與預(yù)讀，且數(shù)據(jù)庫(kù)查詢數(shù)據(jù)的瓶頸在于磁盤 IO,使用平衡二叉樹根據(jù)索引進(jìn)行查找時(shí)，每讀一個(gè)磁盤塊就進(jìn)行一次IO，這樣沒有實(shí)現(xiàn)計(jì)算機(jī)的預(yù)讀能力，導(dǎo)致檢索效率下降，總結(jié)出平衡二叉樹作為索引的問題

• 太深了(即它只有二條路)，深度越大進(jìn)行的IO操作也就越多
• 太小了，每一次IO才查詢磁盤塊這么一點(diǎn)數(shù)據(jù)，太浪費(fèi)IO了。操作系統(tǒng)規(guī)定一次IO最小4K，Mysql一次IO 16K，而圖上的磁盤塊能明顯達(dá)不到4K

B+樹

為了優(yōu)化磁盤IO和預(yù)讀，減少IO操作，條路太少了，那么換成多條路，那么會(huì)想到使用B樹和B+樹，但B樹每個(gè)節(jié)點(diǎn)限制最多存儲(chǔ)兩個(gè) key，也會(huì)造成IO操作過(guò)于頻繁，因此優(yōu)化思路為：盡可能在一次磁盤 IO 中多讀一點(diǎn)數(shù)據(jù)到內(nèi)存，那么B+樹也該出場(chǎng)：

• B+樹一個(gè)節(jié)點(diǎn)能存很多索引，且只有B+樹葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)
• 相鄰節(jié)點(diǎn)之間有一些前驅(qū)后繼關(guān)系
• 葉子節(jié)點(diǎn)是順序排列的

相對(duì)于B樹，B+樹的優(yōu)勢(shì)有：

• B+樹掃庫(kù)掃表的能力更強(qiáng)
• B樹的數(shù)據(jù)是存放在每一個(gè)節(jié)點(diǎn)中的，節(jié)點(diǎn)所在的物理地址又是隨機(jī)的，所以掃表的話，進(jìn)行的是隨機(jī)IO
• B+樹的數(shù)據(jù)是存放在葉子節(jié)點(diǎn)的，且在一個(gè)葉子節(jié)點(diǎn)中的數(shù)據(jù)是連續(xù)的，所以掃表的話，進(jìn)行的相對(duì)的順序IO
• B+樹的磁盤讀寫能力更強(qiáng)，枝節(jié)點(diǎn)不保存數(shù)據(jù)，而保存更多的關(guān)鍵字。一次IO就能讀出更多的關(guān)鍵字
• B+樹的排序能力更強(qiáng)，B+樹的葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是已經(jīng)排好序的

索引的體現(xiàn)形式

索引在不同的存儲(chǔ)引擎中體現(xiàn)形式步一樣， 最常見的是：

• Innodb 引擎中體現(xiàn)為聚集索引方式 (索引和數(shù)據(jù)是存放在同一個(gè)文件的)
• Myisam引擎中體現(xiàn)為非聚集索引方式 (索引和數(shù)據(jù)是存放在兩個(gè)文件中的)

聚集索引方式(InnoDB存儲(chǔ)引擎)

InnoDB存儲(chǔ)引擎中，索引和數(shù)據(jù)是存放在同一個(gè)文件的，屬于聚集索引 。而且InnoDB會(huì)自動(dòng)建立好主鍵 ID 索引樹, 因此建表時(shí)要求必須指定主鍵的原因。

其中，主鍵索引(聚集索引)的葉子節(jié)點(diǎn)記錄了數(shù)據(jù)，而不是數(shù)據(jù)的物理地址。輔助索引的葉子節(jié)點(diǎn)存放的是主鍵key。所以當(dāng)利用輔助索引查找數(shù)據(jù)時(shí)，實(shí)際上查了兩遍索引(輔助索引和主鍵索引):

• 先查詢輔助索引樹找出主鍵
• 然后在主鍵索引樹中根據(jù)主鍵查詢數(shù)據(jù)

非聚集索引方式(Myisam存儲(chǔ)引擎)

Myisam存儲(chǔ)引擎中，索引和數(shù)據(jù)是存放在兩個(gè)文件中的，屬于非聚集索引 。不管是主鍵索引還是輔助索引，其葉子節(jié)點(diǎn)都是記錄了數(shù)據(jù)的物理地址。

MySQL的索引類型

MySQL索引可以分為：

• 普通索引(index): 加速查找

唯一索引：

• 主鍵索引：primary key ：加速查找+約束(不為空且唯一)
• 唯一索引：unique：加速查找+約束 (唯一)

聯(lián)合索引：

• primary key(id,name):聯(lián)合主鍵索引
• unique(id,name):聯(lián)合唯一索引
• index(id,name):聯(lián)合普通索引

全文索引full text :用于搜索很長(zhǎng)一篇文章的時(shí)候，效果最好。

其中，主要理解一下聯(lián)合索引的問題，存儲(chǔ)結(jié)構(gòu)，查詢方式。

聯(lián)合索引

聯(lián)合索引，多個(gè)列組成的索引叫做聯(lián)合索引，單列索引是特殊的聯(lián)合索引。其存儲(chǔ)結(jié)構(gòu)如下：

對(duì)于聯(lián)合索引來(lái)說(shuō)其存儲(chǔ)結(jié)構(gòu)只不過(guò)比單值索引多了幾列，組合索引列數(shù)據(jù)都記錄在索引樹上，(不同的組合索引，B+樹也是不同的)，且存儲(chǔ)引擎會(huì)首先根據(jù)第一個(gè)索引列排序后，其他列再依次將相等值的進(jìn)行排序。

NOTE:葉節(jié)點(diǎn)第一排，按順序排序好，第二列，會(huì)基于第一列排序好的，將第一列相等的再下一列再排序，依次類推。

聯(lián)合索引查詢方式，存儲(chǔ)引擎首先從根節(jié)點(diǎn)(一般常駐內(nèi)存)開始查找，然后再依次在其他列中查詢，直到找到該索引下的data元素即ID值，再?gòu)闹麈I索引樹上找到最終數(shù)據(jù)。

而且聯(lián)合索引其選擇的原則：

• 最左前綴匹配原則(經(jīng)常使用的列優(yōu)先)
• 離散度高的列優(yōu)先
• 寬度小的列優(yōu)先

最左前綴匹配原則

最左前綴匹配原則和聯(lián)合索引的索引構(gòu)建方式及存儲(chǔ)結(jié)構(gòu)是有關(guān)系的。根據(jù)上述理解分析，可以得出聯(lián)合索引只能從多列索引的第一列開始查找索引才會(huì)生效，比如:

• 假設(shè)表user上有個(gè)聯(lián)合索引(a,b,c)，那么 select * from user where b = 1 and c = 2將不會(huì)命中索引
• 原因是聯(lián)合索引的是存儲(chǔ)引擎先按第一個(gè)字段排序，再按第二個(gè)字段排序，依次排序。

離散度

當(dāng)索引中的一列離散度過(guò)低時(shí)，優(yōu)化器可能直接不走索引，離散度計(jì)算方法：

• 離散度 = 列中不重復(fù)的數(shù)據(jù)量 / 這一列的總數(shù)據(jù)量

覆蓋索引

如果一個(gè)索引包含(或覆蓋)所有需要查詢的字段的值，稱為覆蓋索，即只需掃描索引而無(wú)須回表查詢 。覆蓋索引可減少數(shù)據(jù)庫(kù)IO，將隨機(jī)IO變?yōu)轫樞騃O，可提高查詢性能。

對(duì)于InnoDB輔助索引在葉子節(jié)點(diǎn)中保存了行的主鍵值，所以如果輔助索引(包括聯(lián)合索引)能夠覆蓋查詢，則可以避免對(duì)主鍵索引的二次查詢。比如：

--創(chuàng)建聯(lián)合索引 
create index name_phone_idx on user(name,phoneNum); 
--此時(shí)是覆蓋索引，原因是根據(jù)name來(lái)查，命中索引name_phone_idx， 
--其關(guān)鍵字為name,phoneNum，本身就已經(jīng)包含了查詢的列。 
select name,phoneNum where name = "張三";   
--如果id為主鍵的話，此時(shí)也稱作覆蓋索引，原因：輔助索引的葉子節(jié)點(diǎn)存的就是主鍵 
select id,name,phoneNum where name = "張三"; 

總結(jié)

MySQL的索引有很多知識(shí)點(diǎn)要掌握，已學(xué)習(xí)了索引的底層存儲(chǔ)結(jié)構(gòu)，不同存儲(chǔ)引擎中的索引體現(xiàn)，以及索引類型的基礎(chǔ)原理知識(shí)分析，可以為后續(xù)的數(shù)據(jù)庫(kù)優(yōu)化提供理論知識(shí)的支撐，也會(huì)更好的理解優(yōu)化方案。