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

思維導(dǎo)圖

簡(jiǎn)單理解

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

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

索引模型的演變

二叉查找樹

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

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

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

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

缺點(diǎn)：

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

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

自平衡二叉樹

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

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

B樹

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

例如一個(gè)度為 d 的 B-Tree，設(shè)其索引 N 個(gè) key，則其樹高 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)，還可以很好的借助磁盤預(yù)讀的特性。

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

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

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

B+樹

Mysql普遍使用B+樹來實(shí)現(xiàn)其索引結(jié)構(gòu)，跟B樹相比，B+樹有以下幾個(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+ 樹的非葉子節(jié)點(diǎn)不存放實(shí)際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲(chǔ)即存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點(diǎn)可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點(diǎn)的磁盤 I/O次數(shù)會(huì)更少。

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

????????在數(shù)據(jù)庫中，還在B+樹的基礎(chǔ)上進(jìn)行優(yōu)化，增加了順序訪問指針。做這個(gè)優(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)，因此只能通過樹的遍歷來完成范圍查詢，這會(huì)涉及多個(gè)節(jié)點(diǎn)的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。因此，存在大量范圍檢索的場(chǎng)景，適合使用 B+樹，比如數(shù)據(jù)庫。而對(duì)于大量的單個(gè)索引查詢的場(chǎng)景，可以考慮 B 樹，比如 nosql 的MongoDB。

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

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

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

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

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

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

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

在上面兩個(gè)都沒有的情況下，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)

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

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

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

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

總結(jié)

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

最新評(píng)論