目錄

• MySQL索引是什么
• 二叉樹
• 紅黑樹
• B+Tree
• 總結(jié)

MySQL索引是什么

MySQL索引就是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

這個(gè)數(shù)據(jù)結(jié)構(gòu)也就是我們常說的二叉樹、紅黑樹、Hash表等索引數(shù)據(jù)結(jié)構(gòu)，借助這樣的數(shù)據(jù)結(jié)構(gòu)，相較于之前的全局遍歷查詢，能夠更高效的進(jìn)行查詢。

簡單復(fù)習(xí)一下一些常見的索引數(shù)據(jù)結(jié)構(gòu)：

二叉樹

上圖是一個(gè)二叉樹，他根據(jù)我們存放數(shù)據(jù)的順序依次填充這個(gè)樹結(jié)構(gòu)，比根節(jié)點(diǎn)小的數(shù)放到左邊，比根節(jié)點(diǎn)大的放在右邊，這樣我們?nèi)ゲ檎业臅r(shí)候不需要遍歷所有數(shù)據(jù)，只需要依次與根節(jié)點(diǎn)以及下面的子節(jié)點(diǎn)對比就可以查找到我們要找的元素。

查找流程示例圖：

根據(jù)這個(gè)動態(tài)圖左上角的比對信息，可以很清楚的看到二叉樹的查詢邏輯，感興趣的可以去這個(gè)網(wǎng)址實(shí)際模擬下：Data Structure Visualization

但是上述查詢邏輯是在數(shù)據(jù)無大小規(guī)律存儲的情況下進(jìn)行查詢的，如果我們的數(shù)據(jù)按照大小順序存儲會出現(xiàn)以下情況：這其實(shí)雖然叫二叉樹但實(shí)際上已經(jīng)是鏈表結(jié)構(gòu)了，假如我們要查詢較為底層的數(shù)據(jù)，還是要遍歷全局。

MySQL底層不是使用的二叉樹結(jié)構(gòu)。

紅黑樹

相較于上述的二叉樹，紅黑樹做了相應(yīng)的優(yōu)化，他會根據(jù)存儲的數(shù)據(jù)動態(tài)調(diào)整根節(jié)點(diǎn)保證樹左右兩邊的平衡，紅黑樹也是一種平衡樹。

下面來動態(tài)的看下他是如何存儲數(shù)據(jù)的：

可以明顯的看到他動態(tài)調(diào)整樹的結(jié)構(gòu)，其實(shí)也就是減少了樹的深度，相較于上面變?yōu)殒準(zhǔn)降亩鏄洌男蔬€是較高的，但是這僅僅適用于數(shù)據(jù)量不是很大的情況，如果數(shù)據(jù)量百萬甚至千萬，這個(gè)樹的深度一樣很深，查詢起來效率依舊不高。所以MySQL底層也不是使用的紅黑樹結(jié)構(gòu)。

那MySQL使用的那種數(shù)據(jù)結(jié)構(gòu)來存儲索引數(shù)據(jù)的呢？

B+Tree

MySQL底層其實(shí)是使用的B+Tree的數(shù)據(jù)結(jié)構(gòu)存儲的

這個(gè)結(jié)構(gòu)相對于上述兩種結(jié)構(gòu)都有點(diǎn)復(fù)雜了，用更詳細(xì)一點(diǎn)的圖來表達(dá)可以這么看，他實(shí)際上還是樹，但是一個(gè)樹節(jié)點(diǎn)上不只有一個(gè)索引數(shù)據(jù)，只有最底層的葉子節(jié)點(diǎn)上才有數(shù)據(jù)（這個(gè)數(shù)據(jù)就是我們mysql表中的一列數(shù)據(jù)或者是mysql數(shù)據(jù)對應(yīng)的磁盤地址），而其他節(jié)點(diǎn)只存儲索引，也叫作冗余索引。

這樣的索引結(jié)構(gòu)有什么好處呢？

在我們創(chuàng)建數(shù)據(jù)庫索引的時(shí)候，他會自動幫我們建立這樣的B+Tree數(shù)據(jù)結(jié)構(gòu)，上圖假如我們要查詢30那條數(shù)據(jù)（select * from table where column = 30）,這個(gè)column就是我們創(chuàng)建索引的那一列，這樣他會把根節(jié)點(diǎn)加載到內(nèi)存中，根據(jù)二分法或者其他方式查找到30對應(yīng)的區(qū)間地址，因?yàn)樵趦?nèi)存中的查找運(yùn)算要比查詢磁盤要快的多

然后相應(yīng)的再往下找到30所在的區(qū)間位置，遍歷最后一個(gè)葉子節(jié)點(diǎn)就可以獲取到30那條數(shù)據(jù)

那如果數(shù)據(jù)量過大，百萬千萬，樹還會不會變得很深？

我們說樹的查詢效率取決于樹的深度，那這個(gè)在千萬級數(shù)據(jù)量下會不會還有二叉樹和紅黑樹一樣的問題呢？

其實(shí)沒有了，B+Tree是可以設(shè)置樹的最大深度的，我們假設(shè)深度設(shè)置為3，看看能進(jìn)行多少量級的數(shù)據(jù)查詢。

因?yàn)樵谇懊娴膬蓪庸?jié)點(diǎn)中只存儲了索引數(shù)據(jù)和子節(jié)點(diǎn)的磁盤位置，大大節(jié)省了存儲空間，每個(gè)節(jié)點(diǎn)的存儲大小是由mysql設(shè)置的分頁參數(shù)決定的：一般是16kb

ps：頁是InnoDB訪問的最小單位，默認(rèn)16KB。緩沖池是以頁為管理單位，每次讀取或刷新一頁數(shù)據(jù)。參數(shù): innodb_page_size，可以將頁大小設(shè)置為4K，8K.

SHOW GLOBAL STATUS LIKE "Innodb_page_size";

而一個(gè)索引數(shù)據(jù)假設(shè)我們用的bigInt占用8個(gè)字節(jié)，兩個(gè)索引元素之間的空間是下個(gè)節(jié)點(diǎn)的磁盤空間地址，占用6個(gè)字節(jié)，也就是一個(gè)索引+節(jié)點(diǎn)地址占用14b，那么16kb的空間可以存儲數(shù)據(jù)量是1170個(gè)索引，同理第二個(gè)層級的每個(gè)節(jié)點(diǎn)是也是可以存儲1170個(gè)索引，最后一層也就是第三層的節(jié)點(diǎn)因?yàn)榇鎯Φ氖菍?shí)際每一列的數(shù)據(jù)，假設(shè)每列數(shù)據(jù)占用1kb，那每個(gè)節(jié)點(diǎn)占存儲16個(gè)索引數(shù)據(jù)。

整個(gè)樹的數(shù)據(jù)存儲量為1170*1170*16=21,902,400，是個(gè)兩千萬量級的數(shù)據(jù)量。完全滿足大數(shù)據(jù)量的需求。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持。