目錄

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

MySQL索引是什么

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

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

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

二叉樹

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

查找流程示例圖：

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

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

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

紅黑樹

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

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

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

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

B+Tree

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

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

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

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

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

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

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

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

因為在前面的兩層節(jié)點中只存儲了索引數(shù)據(jù)和子節(jié)點的磁盤位置，大大節(jié)省了存儲空間，每個節(jié)點的存儲大小是由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";

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

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

總結(jié)

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