如果你想深入了解為什么mysql可以快速的進(jìn)行檢索數(shù)據(jù)，那么你一定要來(lái)了解一下mysql的索引原理

思維導(dǎo)圖

簡(jiǎn)單理解

你可以把索引理解為一本書(shū)的目錄，我們可以通過(guò)索引快速的找到我們需要的數(shù)據(jù)，大概就像下面這個(gè)圖，索引就像是右邊的二叉樹(shù)，每個(gè)節(jié)點(diǎn)指向具體的數(shù)據(jù)的物理地址，先通過(guò)二叉樹(shù)找到數(shù)據(jù)的位置，然后再去物理磁盤(pán)中獲取數(shù)據(jù)。

但是不同的二叉樹(shù)的特性不同，我們還要選擇合適的樹(shù)來(lái)作為索引，所以接下來(lái)就來(lái)學(xué)習(xí)一下各個(gè)樹(shù)的特性

索引模型的演變

二叉查找樹(shù)

二分查找樹(shù)就是在數(shù)組的基礎(chǔ)上，利用二分查找技巧，將用到的中間節(jié)點(diǎn)，作為指針。這樣他的每個(gè)節(jié)點(diǎn)的左子樹(shù)的值都小于該節(jié)點(diǎn)的值，每個(gè)節(jié)點(diǎn)右子樹(shù)的值都大于該節(jié)點(diǎn)的值。在查找元素時(shí)，我們于根節(jié)點(diǎn)進(jìn)行對(duì)比后，就能每次近乎一半的去除掉查找范圍，可以極大的加快查找速度。

優(yōu)點(diǎn)：

插入方便，不必連續(xù)排列

利用樹(shù)的特新，查找很方便

缺點(diǎn)：

如果每次都是插入都是最大值，會(huì)導(dǎo)致其變成鏈表，查找復(fù)雜度增加

插入的元素越多，樹(shù)的高度就會(huì)高，導(dǎo)致查詢(xún)性能下降

自平衡二叉樹(shù)

相比于二叉樹(shù)來(lái)說(shuō)，自平衡二叉樹(shù)會(huì)通過(guò)左旋或者右旋來(lái)保證左子樹(shù)跟右子樹(shù)的高度差不超過(guò)一。這就很好解決了二分查找樹(shù)變成鏈表的問(wèn)題

?但如果元素越多，樹(shù)的高度還是很容易變的很高，這會(huì)導(dǎo)致查詢(xún)效率變慢。為了解決這個(gè)問(wèn)題，于是就出現(xiàn)了B樹(shù)。

B樹(shù)

B樹(shù)的最大不同就是不再限制一個(gè)節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)，而是允許有多個(gè)節(jié)點(diǎn)，這就是多叉樹(shù)。并且B樹(shù)所有的葉子節(jié)點(diǎn)必須在同一層次，也就是它們具有相同的深度

例如一個(gè)度為 d 的 B-Tree，設(shè)其索引 N 個(gè) key，則其樹(shù)高 h 的上限為 logn(N/2)，檢索一個(gè) key，其查找節(jié)點(diǎn)個(gè)數(shù)的漸進(jìn)復(fù)雜度為 O(logn((N+1)/2))。從這點(diǎn)可以看出，B-Tree 是一個(gè)非常有效率的索引數(shù)據(jù)結(jié)構(gòu)。

局部性原理

????????而這種多個(gè)節(jié)點(diǎn)的結(jié)構(gòu)，還可以很好的借助磁盤(pán)預(yù)讀的特性。

????????由于存儲(chǔ)介質(zhì)的特性，磁盤(pán)本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤(pán)的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤(pán) I/O。為了達(dá)到這個(gè)目的，磁盤(pán)往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤(pán)也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。由于磁盤(pán)順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高 I/O 效率。

????????在B樹(shù)中，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B樹(shù)還需要使用如下技巧：<br />每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)只需一次I/O。

????????但是 B 樹(shù)的每個(gè)節(jié)點(diǎn)都包含數(shù)據(jù)（索引+記錄），而用戶的記錄數(shù)據(jù)的大小很有可能遠(yuǎn)遠(yuǎn)超過(guò)了索引數(shù)據(jù)，這就需要花費(fèi)更多的磁盤(pán) I/O 操作次數(shù)來(lái)讀到「有用的索引數(shù)據(jù)。而且，在我們查詢(xún)位于底層的某個(gè)節(jié)點(diǎn)（比如 A 記錄）過(guò)程中，「非 A 記錄節(jié)點(diǎn)」里的記錄數(shù)據(jù)會(huì)從磁盤(pán)加載到內(nèi)存，但是這些記錄數(shù)據(jù)是沒(méi)用的，我們只是想讀取這些節(jié)點(diǎn)的索引數(shù)據(jù)來(lái)做比較查詢(xún)，而「非 A 記錄節(jié)點(diǎn)」里的記錄數(shù)據(jù)對(duì)我們是沒(méi)用的，這樣不僅增多磁盤(pán) I/O 操作次數(shù)，也占用內(nèi)存資源。

B+樹(shù)

Mysql普遍使用B+樹(shù)來(lái)實(shí)現(xiàn)其索引結(jié)構(gòu)，跟B樹(shù)相比，B+樹(shù)有以下幾個(gè)不同點(diǎn)

葉子節(jié)點(diǎn)（最底部的節(jié)點(diǎn)）才會(huì)存放實(shí)際數(shù)據(jù)（索引+記錄），非葉子節(jié)點(diǎn)只會(huì)存放索引；

所有索引都會(huì)在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)之間構(gòu)成一個(gè)有序鏈表；

非葉子節(jié)點(diǎn)的索引也會(huì)同時(shí)存在在子節(jié)點(diǎn)中，并且是在子節(jié)點(diǎn)中所有索引的最大（或最?。?。

非葉子節(jié)點(diǎn)中有多少個(gè)子節(jié)點(diǎn)，就有多少個(gè)索引；

????????B+ 樹(shù)的非葉子節(jié)點(diǎn)不存放實(shí)際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲(chǔ)即存索引又存記錄的 B 樹(shù)，B+樹(shù)的非葉子節(jié)點(diǎn)可以存放更多的索引，因此 B+ 樹(shù)可以比 B 樹(shù)更「矮胖」，查詢(xún)底層節(jié)點(diǎn)的磁盤(pán) I/O次數(shù)會(huì)更少。

????????B+作為多叉樹(shù)，在有大量的冗余節(jié)點(diǎn)，在進(jìn)行刪除或者插入操作時(shí)都不會(huì)發(fā)生復(fù)雜的樹(shù)的變形。

????????在數(shù)據(jù)庫(kù)中，還在B+樹(shù)的基礎(chǔ)上進(jìn)行優(yōu)化，增加了順序訪問(wèn)指針。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問(wèn)的性能，例如如果要查詢(xún) key 為從 18 到 49 的所有數(shù)據(jù)記錄，當(dāng)找到 18 后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢(xún)效率。<br />而 B 樹(shù)沒(méi)有將所有葉子節(jié)點(diǎn)用鏈表串聯(lián)起來(lái)的結(jié)構(gòu)，因此只能通過(guò)樹(shù)的遍歷來(lái)完成范圍查詢(xún)，這會(huì)涉及多個(gè)節(jié)點(diǎn)的磁盤(pán) I/O 操作，范圍查詢(xún)效率不如 B+ 樹(shù)。因此，存在大量范圍檢索的場(chǎng)景，適合使用 B+樹(shù)，比如數(shù)據(jù)庫(kù)。而對(duì)于大量的單個(gè)索引查詢(xún)的場(chǎng)景，可以考慮 B 樹(shù)，比如 nosql 的MongoDB。

????????而在mysql中，B+ 樹(shù)的葉子節(jié)點(diǎn)之間是用「雙向鏈表」進(jìn)行連接，這樣的好處是既能向右遍歷，也能向左遍歷<br />?

聚集索引與二級(jí)索引

聚集索引（主鍵索引）：將數(shù)據(jù)與索引放到了一塊，索引結(jié)構(gòu)的葉子節(jié)點(diǎn)存儲(chǔ)了行數(shù)據(jù)，找到索引也就找到了數(shù)據(jù)

二級(jí)索引（非主鍵索引）：將數(shù)據(jù)與索引分開(kāi)存儲(chǔ)，索引結(jié)構(gòu)的葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵的值

InnoDB 在創(chuàng)建聚簇索引時(shí)，會(huì)根據(jù)不同的場(chǎng)景選擇不同的列作為索引：

如果有主鍵，默認(rèn)會(huì)使用主鍵作為聚簇索引的索引鍵；

如果沒(méi)有主鍵，就選擇第一個(gè)不包含 NULL 值的唯一列作為聚簇索引的索引鍵；

在上面兩個(gè)都沒(méi)有的情況下，InnoDB 將自動(dòng)生成一個(gè)隱式自增 id 列作為聚簇索引的索引鍵；

因?yàn)楸淼臄?shù)據(jù)都是存放在聚集索引的葉子節(jié)點(diǎn)里，所以 InnoDB 存儲(chǔ)引擎一定會(huì)為表創(chuàng)建一個(gè)聚集索引，且由于數(shù)據(jù)在物理上只會(huì)保存一份，所以聚簇索引只能有一個(gè)，而二級(jí)索引可以創(chuàng)建多個(gè)。

例如圖中(ID,k)值分別為(100,1)、(200,2)、(300,3)、(500,5)和(600,6)

???查詢(xún)時(shí)的區(qū)別：

如果語(yǔ)句是select * from T where ID=500，即主鍵查詢(xún)方式，則只需要搜索ID這棵B+樹(shù)；

如果語(yǔ)句是select * from T where k=5，即普通索引查詢(xún)方式，則需要先搜索k索引樹(shù)，得到ID的值為500，再到ID索引樹(shù)搜索一次。這個(gè)過(guò)程稱(chēng)為回表。

????????也就是說(shuō)，基于非主鍵索引的查詢(xún)需要多掃描一棵索引樹(shù)。因此，我們?cè)趹?yīng)用中應(yīng)該盡量使用主鍵查詢(xún)。

總結(jié)

到此這篇關(guān)于mysql數(shù)據(jù)庫(kù)之索引詳細(xì)介紹的文章就介紹到這了,更多相關(guān)mysql索引內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！