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

思維導(dǎo)圖

簡單理解

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

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

索引模型的演變

二叉查找樹

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

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

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

利用樹的特新，查找很方便

缺點(diǎn)：

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

插入的元素越多，樹的高度就會高，導(dǎo)致查詢性能下降

自平衡二叉樹

相比于二叉樹來說，自平衡二叉樹會通過左旋或者右旋來保證左子樹跟右子樹的高度差不超過一。這就很好解決了二分查找樹變成鏈表的問題

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

B樹

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

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

局部性原理

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

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

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

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

B+樹

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

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

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

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

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

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

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

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

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

聚集索引與二級索引

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

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

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

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

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

在上面兩個都沒有的情況下，InnoDB 將自動生成一個隱式自增 id 列作為聚簇索引的索引鍵；

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

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

???查詢時的區(qū)別：

如果語句是select * from T where ID=500，即主鍵查詢方式，則只需要搜索ID這棵B+樹；

如果語句是select * from T where k=5，即普通索引查詢方式，則需要先搜索k索引樹，得到ID的值為500，再到ID索引樹搜索一次。這個過程稱為回表。

????????也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應(yīng)用中應(yīng)該盡量使用主鍵查詢。

總結(jié)

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

最新評論