MySql索引底層數(shù)據(jù)結(jié)構(gòu)
索引的本質(zhì)
索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
很多文章都講過(guò)，Mysql底層的數(shù)據(jù)結(jié)構(gòu)是通過(guò)B+Tree實(shí)現(xiàn)的，那具體為什么要用這種結(jié)構(gòu)來(lái)實(shí)現(xiàn)呢？我們從各種數(shù)據(jù)結(jié)構(gòu)分析一下。假如數(shù)據(jù)庫(kù)中的數(shù)據(jù)是這個(gè)樣子的。
1. 不用索引的方式查找
因?yàn)閿?shù)據(jù)是存在磁盤上的，所以如果想要查找表中col2 = 89的這條記錄，則需要進(jìn)行6次的磁盤IO進(jìn)行查找，效率很低
2.二叉樹(shù)
比如給col2列中使用二叉樹(shù)的方式加入索引，結(jié)構(gòu)會(huì)變成這個(gè)樣子，此時(shí)我們想查找col2 = 22的這條記錄，利用二叉樹(shù)特性，右節(jié)點(diǎn)>父節(jié)點(diǎn)>左節(jié)點(diǎn)。我們只需要進(jìn)行3次IO查找即可找到數(shù)據(jù)
看起來(lái)這種方式也不錯(cuò)，但是如果我們是在col1中也使用這種方式存儲(chǔ)會(huì)是什么情況呢？下圖所示，比如此時(shí)想查找col1 = 6的數(shù)據(jù)，還是要進(jìn)行6次的磁盤IO，這樣的方式存儲(chǔ)就沒(méi)有什么用途了吧
3.紅黑樹(shù)
紅黑樹(shù)是二叉樹(shù)的一種，但它可以自動(dòng)對(duì)一棵樹(shù)進(jìn)行平衡，例如上圖中col1的情況，它將會(huì)用這種結(jié)構(gòu)存儲(chǔ)，如圖。這種方式看來(lái)，應(yīng)該沒(méi)問(wèn)題了吧？但是想一想，表中數(shù)據(jù)如果有上百萬(wàn)條記錄，那這個(gè)樹(shù)的高度會(huì)有多高？樹(shù)的高度也就決定了磁盤IO的次數(shù)。為解決這個(gè)問(wèn)題，是不是可以考慮減少樹(shù)的高度呢？下面介紹下B-Tree
4.B Tree
圖中所示，B樹(shù)事實(shí)上是一種平衡的多叉查找樹(shù)，也就是說(shuō)最多可以開(kāi)m個(gè)叉（m>=2）我們稱之為m階b樹(shù)。
通過(guò)B Tree存儲(chǔ)結(jié)構(gòu)如下所示（假設(shè)是個(gè)4階B樹(shù)）。BTree是二叉樹(shù)的一種，所以也具有二叉樹(shù)的特點(diǎn)（右節(jié)點(diǎn)>父節(jié)點(diǎn)>左節(jié)點(diǎn)），此時(shí)，比如我們想要查找20這個(gè)位置，則只需要進(jìn)行3次磁盤IO，即可定位到記錄。在mysql中，一排最多能存儲(chǔ)多少個(gè)呢？假設(shè)字段是BitInt類型（8字節(jié)），數(shù)據(jù)與數(shù)據(jù)之間存在指針空間（6字節(jié)），假設(shè)表中數(shù)據(jù)一行大小為1kb。Mysql默認(rèn)存儲(chǔ)空間是16KB，由此可以得知，如果用bigint類型存儲(chǔ)，一排最多可以存儲(chǔ) 16*1024/（8+6+1024） ≈ 15個(gè)索引。假設(shè)一個(gè)高度為3的樹(shù)，最多可以存儲(chǔ)多少個(gè)索引呢？ 15 * 15 * 15 = 3375。那有什么辦法能再次優(yōu)化呢？我們來(lái)看下B+Tree的存儲(chǔ)結(jié)構(gòu)
5.B+Tree
B+Tree是B Tree的變種，形式上和BTree差不多，只是把數(shù)據(jù)做了一次冗余，所有的數(shù)據(jù)存在子節(jié)點(diǎn)上，如圖所示。通過(guò)這種冗余的方式，讓每一層中存儲(chǔ)的索引更多，假設(shè)表中的一行記錄需要1KB空間存儲(chǔ)，一個(gè)高度為3的B+Tree最多可以支持多少索引數(shù)據(jù)？1170 * 1170 * 16 =?21,902,400，由此可見(jiàn)，一個(gè)高度為3的B+Tree如果存滿的話，最多可以放2千萬(wàn)條索引數(shù)據(jù)（因?yàn)閿?shù)據(jù)需要冗余，數(shù)值要小于計(jì)算出來(lái)的值，具體沒(méi)算），查詢時(shí)最多進(jìn)行3次磁盤IO即可定位到記錄。
最下邊那個(gè)鏈表樣子的指針是做什么用的？范圍查詢（下圖中應(yīng)該是個(gè)雙向指針）。比如說(shuō)我們想查找>15的索引對(duì)應(yīng)的數(shù)據(jù)。如果按照BTree方式查找，需要不斷的返回父節(jié)點(diǎn)再次進(jìn)行查詢。而B(niǎo)+Tree通過(guò)這個(gè)鏈表指針，直接獲取到下一個(gè)節(jié)點(diǎn)。
6.Hash表
Mysql支持使用Hash方式建立索引，如圖。我們都知道Hash算法是一種散列算法，查找的時(shí)間復(fù)雜度為O(1)，那這么好的辦法，Mysql為什么默認(rèn)不使用Hash存儲(chǔ)索引呢？答案是范圍查詢，如果是范圍查找，Hash表的方式就搞不定了，只能走全表查詢。所以如果表中的字段不需要用到范圍或條件查詢。那么用Hash結(jié)構(gòu)存儲(chǔ)則會(huì)快很多。
MyISAM 索引實(shí)現(xiàn)?
MyISAM 引擎使用 B+Tree 作為索引結(jié)構(gòu),葉節(jié)點(diǎn)的 data 域存放的是數(shù)據(jù)記錄的地址。下圖是 MyISAM 索引的原理圖，MyISAM是非聚集索引，索引和數(shù)據(jù)在磁盤中是分開(kāi)存儲(chǔ)的，索引存儲(chǔ)的是磁盤位置。
InnoDB 索引實(shí)現(xiàn)?
在InnoDB 中,表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個(gè)索引結(jié)構(gòu),這棵樹(shù)的葉點(diǎn)data 域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的 key 是數(shù)據(jù)表的主鍵,因此?InnoDB 表數(shù)據(jù)文件本身就是主索引。
InnoDB 與 MyISAM存儲(chǔ)數(shù)據(jù)方式是不同的，MyISAM存的是磁盤地址，而InnoDB主鍵索引存儲(chǔ)的是數(shù)據(jù)，非主鍵索引存儲(chǔ)的是主鍵數(shù)值，這就是為什么 InnoDB 要求表中必須要有主鍵，如果沒(méi)有顯式指定,則 MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列,則MySQL 自動(dòng)為 InnoDB 表生成一個(gè)隱含字段作為主鍵,類型為長(zhǎng)整形。
為什么推薦使用整型的自增主鍵？
因?yàn)槭褂肂+Tree結(jié)構(gòu)存儲(chǔ)，如果主鍵生成的沒(méi)有規(guī)律，在新增時(shí)，會(huì)引發(fā)B+Tree分裂，影響效率，如果是自增類型，僅改變末尾處的指針數(shù)據(jù)即可。所以我們要避免使用uuid等這些字段作為表中的主鍵字段。
