預(yù)熱

比較喜歡的一段話：不經(jīng)一番寒徹骨，怎得梅花撲鼻香，學(xué)習(xí)是枯燥的請大家堅持！這篇文章的是向丁奇老師學(xué)習(xí)的。不懂的自己搜一下哈！閱讀這篇文章大概需要25分鐘！

大家好前面我們大概了解了事務(wù)隔離級別的區(qū)別與實現(xiàn)，應(yīng)用技巧等。今天我們介紹一下數(shù)據(jù)庫的索引！

開始

MySQL為什么選擇Innodb？

首先我們介紹一下MySQL的默認引擎為什么會使用Innodb。

5.1之前MySQL使用的一直都是MyISAM，MyISAM存儲方式是非聚集索引，也就是說索引與行記錄分開存儲的。5.1之后MySQL換成了Innodb，Innodb存儲方式是聚集索引，也就是索引與記錄是存在一起的。通過這一點可以看出從查詢效率上Innodb優(yōu)于MyISAM。一定程序上節(jié)省了很多磁盤IO的消耗問題

隨著數(shù)據(jù)庫的發(fā)展對數(shù)據(jù)一致性要求越來越高，事務(wù)就出現(xiàn)了，MySQL選擇Innodb有很大的原因則是因為事務(wù)的支持問題。而且也沒有事務(wù)的日志。無法保證數(shù)據(jù)的安全性

innodb支持行級鎖，MyISAM只支持表鎖，在數(shù)據(jù)量稍大的時候無法滿足并發(fā)的要求。

最主要的還是隨著現(xiàn)在的發(fā)展事務(wù)是比較重要的因素。

Innodb的底層算法又是如何抉擇

哈希索引

我們先來了解一下哈希索引，哈希索引不管是存還是取的時候，都會進行一遍哈希值處理，會把key換算成一個一串計算機地址進行存儲。在進行查詢?nèi)≈档臅r候也是一樣的。所以查詢效率是非常高的，但是不支持范圍查找，所以無法滿足當前數(shù)據(jù)查詢的需求。但是如果查單個數(shù)值的時候利用哈希索引查找是非常優(yōu)秀的。

有序數(shù)組

這個有序數(shù)組就是類似于鏈表一樣，如果數(shù)據(jù)量過于龐大的話，查詢數(shù)據(jù)要一個一個遍歷之后才可以。這樣的效率是非常慢的。所以不完成采用這種方式。

二叉樹索引

平時我們遍歷數(shù)據(jù)的時候會遍歷一個鏈表，數(shù)組等操作。從0開始的效率是比較慢的。為了提升查詢效率，采用二叉樹的查詢方式極大的優(yōu)化的查詢性能。但是的新增數(shù)據(jù)的時候會有一種極端的情況。以下就是舉個一個例子，按照二叉樹的特性，新增節(jié)點之前會先判斷一下當前節(jié)點應(yīng)該歸到哪個節(jié)點上。如果新增的數(shù)據(jù)一個比一個大那么就會出現(xiàn)二叉樹傾斜的場景。

傾斜的二叉樹和鏈表的查詢性能是一樣的，這顯然不是我們要的效果。于是二叉樹pass

1,2,3,4,5,6,8,9

紅黑樹

隨著二叉樹的演變，最終采用了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。

紅黑樹是一個平衡二叉樹，可以完美的解決二叉樹遺留下來的不足。但是也正是因為平衡這一特性，導(dǎo)致紅黑樹也同樣不適合作為默認的數(shù)據(jù)結(jié)構(gòu)，因為，平衡后的樹過于龐大，這一對數(shù)據(jù)的存儲非常的不利。因為樹過高在查詢數(shù)據(jù)的時候，會采用多次磁盤IO，因為一個數(shù)據(jù)頁只有4K，不可能存儲所有的數(shù)據(jù)。

據(jù)我們所知，磁盤IO尋址時間大概在10ms，如果數(shù)據(jù)量上了一定百萬級。這樣的查詢速度是有點頭疼的。所以為了繼續(xù)優(yōu)化底層數(shù)據(jù)結(jié)構(gòu)。最終轉(zhuǎn)移到了B樹上。

B樹

B樹的出現(xiàn)，解決了紅黑樹(平衡二叉樹)，樹高的問題。他的實現(xiàn)方式是使葉子節(jié)點具有相同的深度，但是有出現(xiàn)了一個查詢數(shù)據(jù)的毛病，在查詢一段時間的時候往往要通過上層的節(jié)點進行反查，這樣極大的降低了查詢數(shù)據(jù)的效率。于是B樹pass

B+樹

開發(fā)人員兜兜轉(zhuǎn)轉(zhuǎn)最終到了B+樹上，B+樹是在B樹上做的擴展。兼容B樹的同時使底層節(jié)點類似于鏈表那樣一一串起來。這樣最終解決了上面所有數(shù)據(jù)結(jié)構(gòu)中的問題。

索引類型

主鍵索引

它是一種特殊的唯一索引，不允許有空值。一般是在建表的時候指定了主鍵，就會創(chuàng)建主鍵索引， CREATE INDEX不能用來創(chuàng)建主鍵索引，使用 ALTER TABLE來代替。

聚集索引其實就是主鍵索引

舉例看一下

create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

ID是一個主鍵所以會有一個主鍵樹，k是一個索引字段，name是一個普通字段。

從圖中不難看出，根據(jù)葉子節(jié)點的內(nèi)容，索引類型分為主鍵索引和非主鍵索引。主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)。在 InnoDB 里，主鍵索引也被稱為聚簇索引。非主鍵索引的葉子節(jié)點內(nèi)容是主鍵的值。在 InnoDB 里，非主鍵索引也被稱為二級索引。

首先我們執(zhí)行以下SQL，因為這里的ID是主鍵，根據(jù)數(shù)據(jù)存儲的結(jié)構(gòu)，我們只需要查詢ID這顆B+樹就好了，因為這顆B+樹上存儲著這個數(shù)據(jù)表中ID=500的所有列名數(shù)據(jù)。如果節(jié)點中有些數(shù)據(jù)不在這顆樹上的時候，就無法實現(xiàn)這樣的效果了。必須通過回表的方式查詢對應(yīng)的列名數(shù)據(jù)才可以返回數(shù)據(jù)到客戶端。

select * from T where ID=500  主鍵索引查詢

我們再講述一下這條SQL，因為這里查詢的是k這個字段的值，k這個字段是普通索引，所以數(shù)據(jù)結(jié)構(gòu)的存儲方式是如右圖的。如果用戶想查出所有 T 表中的所有列名數(shù)據(jù)，就必須先查 k 樹上的 k=5 的數(shù)據(jù)，得到 ID等于 500 之后，再帶著 500 回到 ID 樹上進行查詢 R4 這個數(shù)據(jù)。這個過程就是回表，回表次數(shù)越多，耗時越慢。

select * from T where k=5 普通索引查詢

綜上所述，工作過程中很多人在解決數(shù)據(jù)查詢慢的時候往往是通過加一個索引達到提高查詢效率的原因就是這個。所以開發(fā)過程中盡量采用主鍵查詢。

唯一索引

與普通索引類似，不同的就是：索引列的值必須唯一，但允許有空值。如果是組合索引，則列值的組合必須一

普通索引

這是最基本的索引，它沒有任何限制

全文索引

FULLTEXT索引用于全文搜索。只有InnoDB和 MyISAM存儲引擎支持 FULLTEXT索引和僅適用于 CHAR， VARCHAR和 TEXT列

索引維護

工作中，通常為了提升性能，隨隨便便的就加了一些索引，會導(dǎo)致索引過多，適得其所。所以平時我們要對索引有一個維護的過程。

索引維護的常見問題是：如果插入新的行 ID 值為 700，則只需要在 R5 的記錄后面插入一個新記錄。如果新插入的 ID 值為 400，就相對麻煩了，需要邏輯上挪動后面的數(shù)據(jù)，空出位置。而更糟的情況是，如果 R5 所在的數(shù)據(jù)頁已經(jīng)滿了，根據(jù) B+ 樹的算法，這時候需要申請一個新的數(shù)據(jù)頁，然后挪動部分數(shù)據(jù)過去。這個過程稱為頁分裂。在這種情況下，性能自然會受影響。

相反，如果一條數(shù)據(jù)在刪除的時候，利用率很低的時候，會有一個數(shù)據(jù)合并的過程，這個過程就是分裂過程的逆工程。

不管是頁分裂還是分裂逆工程，除了性能外，整體空間的利用率降低大概50%。

覆蓋索引

這個不太好說，舉個例子自己體會一下吧。

我們要查詢 user 這個表上的 k 在 3 - 7 的范圍上的ID所有數(shù)據(jù)。這個時候 k 是一個索引，所以存在一個索引樹。這個索引樹上剛好存有ID的這個葉子節(jié)點的數(shù)據(jù)。所以就可以直接在這顆k索引樹上查詢，不需要回到主鍵索引樹上查詢，也就是回表操作。

這樣就是大概的覆蓋索引！

select ID from user where k between 3 and 7

核心：覆蓋索引可以完美的解決回表的操作。可以顯著的提升查詢性能。所以覆蓋索引往往是一個性能優(yōu)化比較實用的手段之一。

最左前綴索引

這里就是大家常說的最左前綴原則。那么到底是一個什么東西呢？

這個是B+樹索引結(jié)構(gòu)，可以利用最左前綴原則來定位記錄。

這里我們舉一個聯(lián)合索引的例子，性能和年齡都是索引的情況，如果我們要查詢姓名為張三的人，那么很快就能定位到ID4并且后面的所有數(shù)據(jù)。如果要查姓名是張開頭的人，那么我們也能很快定位到ID3之后的所有數(shù)據(jù)。這個就是最左前綴原則的好處。他可以減少很多不必要的索引。

索引下推

上面我們介紹了最左前綴索引，這里的索引下推跟上文是息息相關(guān)的。索引下推這個概念是在MySQL5.6版本引入的，屬于是一個查詢內(nèi)部的優(yōu)化。

舉個例子吧。我們要查詢 tuser 表中哪些是姓張的人，并且年齡是20歲的人，沒有被刪除過的人。

select * from tuser where name like '張%' and age=20 and isdelete=1;

5.6之前的版本會通過 name 樹查詢姓張的。然后數(shù)據(jù)查詢之后就要開始判斷，當前數(shù)據(jù)是否滿足后面的條件，age是否等于20以及是否處于未刪除的狀態(tài)。只有這樣這條SQL也完成。那么判斷age=20，需要進行回表。回表的操作就是拿著當前這條數(shù)據(jù)的ID號，去主鍵索引查詢這個ID對應(yīng)的age。判斷滿足之后這條數(shù)據(jù)也完全匹配。然后繼續(xù)下一條操作。

5.6之后的版本,引入了索引下推這個概念。會優(yōu)先判斷當前這條記錄是否滿足age=20，并且是沒有被刪除過后的。判斷結(jié)果成立之后再進行回表操作。這樣減少了回表次數(shù)，優(yōu)化了查詢效率。

深入淺出索引