MySQL的索引是如何提高查詢效率的？

一.索引是什么？

索引是數(shù)據(jù)庫中用來提高查詢效率的技術(shù)，類似于目錄。如果不使用索引，數(shù)據(jù)會(huì)零散的保存在磁盤塊中，查詢數(shù)據(jù)需要挨個(gè)遍歷每一個(gè)磁盤塊，直到找到數(shù)據(jù)為止，使用索引后會(huì)將磁盤塊以樹樁結(jié)構(gòu)保存，查詢數(shù)據(jù)時(shí)會(huì)大大降低磁盤塊的訪問數(shù)量，從而提高查詢效率。如果表中的數(shù)據(jù)很少，使用索引反而會(huì)降低查詢效率。并且索引會(huì)占用磁盤空間，一般只針對(duì)查詢時(shí)常用的字段創(chuàng)建索引。索引分為聚集索引和非聚集索引，通過主鍵創(chuàng)建的索引稱為聚集索引，聚集索引中保存數(shù)據(jù)，只要給表添加主鍵約束，則會(huì)自動(dòng)創(chuàng)建聚集索引；通過非主鍵字段創(chuàng)建的索引稱為非聚集索引，非聚集索引中沒有數(shù)據(jù)。還可以通過多個(gè)字段來創(chuàng)建復(fù)合索引。

二.MySQL中存儲(chǔ)索引用的是什么結(jié)構(gòu)？

MySQL中存儲(chǔ)索引用的一般都是B+樹。它的數(shù)據(jù)都存放在葉子節(jié)點(diǎn)中，同時(shí)葉子節(jié)點(diǎn)之間還添加了指針形成了鏈表。有點(diǎn)像HashMap的底層實(shí)現(xiàn)，數(shù)組 + 鏈表的結(jié)構(gòu)。

上圖是一個(gè)4路B+樹，可以清楚的看到，所有的數(shù)據(jù)都存放在葉子節(jié)點(diǎn)上，并且葉子節(jié)點(diǎn)之間有指針鏈表相連。

三.為什么要用B+樹？

首先，B+樹是平衡樹。樹的查詢效率是log(n)，n為樹的高度。如果使用非平衡樹，如二叉樹。那么在特殊情況，如插入的數(shù)據(jù)是有序的，會(huì)出現(xiàn)什么情況呢？

二叉樹發(fā)生了退化，變成了鏈表，樹的高度變高了，影響了查詢的效率。由于B+樹是平衡樹，保證了樹的高度是最優(yōu)的，所以不會(huì)出現(xiàn)上述的退化情況。上文展示了一個(gè)4路的B+樹，可以看出當(dāng)路數(shù)越多時(shí)，樹的高度是越低的，那么問題來了，為什么不設(shè)計(jì)一個(gè)無限多路的B樹來降低樹高度，從而提升查詢效率呢？先來看看一個(gè)無限多路的B樹是什么樣的。

不限路數(shù)，B樹就退化成了一個(gè)數(shù)組。那么會(huì)出現(xiàn)什么問題呢？數(shù)據(jù)庫的索引是存儲(chǔ)在硬盤上的，如果數(shù)據(jù)量大的話，不一定可以一次性加載到內(nèi)存中。這時(shí)候，多路存儲(chǔ)的好處就體現(xiàn)出來了，可以每次加載樹的一個(gè)節(jié)點(diǎn)，然后一步步往下找。比如一個(gè)三路的B樹，每個(gè)節(jié)點(diǎn)最多有兩個(gè)數(shù)，查找的時(shí)候每次載入一個(gè)節(jié)點(diǎn)進(jìn)內(nèi)存就行，就不會(huì)出現(xiàn)數(shù)據(jù)量過大無法加載到內(nèi)存中的情況。在業(yè)務(wù)場景中查詢數(shù)據(jù)時(shí)，往往是查詢多條數(shù)據(jù)，比如查詢最近修改過的10條數(shù)據(jù)，B+樹在B樹的基礎(chǔ)上進(jìn)行了優(yōu)化，B+樹的所有數(shù)據(jù)都在葉子結(jié)點(diǎn)，同時(shí)有鏈表結(jié)構(gòu)，只需要找到首尾，就可以把所有的數(shù)據(jù)找出來了。綜上述所述，MySQL中存儲(chǔ)索引用B+樹的好處主要是降低樹高度提高查詢效率、多路設(shè)計(jì)保證硬盤到內(nèi)存的加載、葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)并且加了指針形成鏈表在范圍查找時(shí)只需定位首尾就可以取出所需數(shù)據(jù)。