MySql索引底層數(shù)據(jù)結(jié)構(gòu)
索引的本質(zhì)
索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
很多文章都講過暗赶，Mysql底層的數(shù)據(jù)結(jié)構(gòu)是通過B+Tree實(shí)現(xiàn)的肛搬，那具體為什么要用這種結(jié)構(gòu)來實(shí)現(xiàn)呢禽笑？我們從各種數(shù)據(jù)結(jié)構(gòu)分析一下阎毅。假如數(shù)據(jù)庫中的數(shù)據(jù)是這個(gè)樣子的蜜笤。
1. 不用索引的方式查找
因?yàn)閿?shù)據(jù)是存在磁盤上的靴迫，所以如果想要查找表中col2 = 89的這條記錄惕味，則需要進(jìn)行6次的磁盤IO進(jìn)行查找，效率很低
2.二叉樹
比如給col2列中使用二叉樹的方式加入索引玉锌，結(jié)構(gòu)會(huì)變成這個(gè)樣子赦拘，此時(shí)我們想查找col2 = 22的這條記錄，利用二叉樹特性芬沉，右節(jié)點(diǎn)>父節(jié)點(diǎn)>左節(jié)點(diǎn)躺同。我們只需要進(jìn)行3次IO查找即可找到數(shù)據(jù)
看起來這種方式也不錯(cuò)，但是如果我們是在col1中也使用這種方式存儲(chǔ)會(huì)是什么情況呢丸逸？下圖所示蹋艺，比如此時(shí)想查找col1 = 6的數(shù)據(jù)，還是要進(jìn)行6次的磁盤IO黄刚，這樣的方式存儲(chǔ)就沒有什么用途了吧
3.紅黑樹
紅黑樹是二叉樹的一種捎谨，但它可以自動(dòng)對一棵樹進(jìn)行平衡，例如上圖中col1的情況，它將會(huì)用這種結(jié)構(gòu)存儲(chǔ)涛救，如圖畏邢。這種方式看來，應(yīng)該沒問題了吧检吆？但是想一想舒萎，表中數(shù)據(jù)如果有上百萬條記錄，那這個(gè)樹的高度會(huì)有多高蹭沛？樹的高度也就決定了磁盤IO的次數(shù)臂寝。為解決這個(gè)問題，是不是可以考慮減少樹的高度呢摊灭？下面介紹下B-Tree
4.B Tree
圖中所示咆贬，B樹事實(shí)上是一種平衡的多叉查找樹，也就是說最多可以開m個(gè)叉（m>=2）我們稱之為m階b樹帚呼。
通過B Tree存儲(chǔ)結(jié)構(gòu)如下所示（假設(shè)是個(gè)4階B樹）掏缎。BTree是二叉樹的一種，所以也具有二叉樹的特點(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的樹灰瞻，最多可以存儲(chǔ)多少個(gè)索引呢腥例？ 15 * 15 * 15 = 3375。那有什么辦法能再次優(yōu)化呢酝润？我們來看下B+Tree的存儲(chǔ)結(jié)構(gòu)
5.B+Tree
B+Tree是B Tree的變種燎竖，形式上和BTree差不多，只是把數(shù)據(jù)做了一次冗余要销，所有的數(shù)據(jù)存在子節(jié)點(diǎn)上构回，如圖所示。通過這種冗余的方式，讓每一層中存儲(chǔ)的索引更多纤掸，假設(shè)表中的一行記錄需要1KB空間存儲(chǔ)脐供，一個(gè)高度為3的B+Tree最多可以支持多少索引數(shù)據(jù)？1170 * 1170 * 16 =?21,902,400借跪，由此可見政己，一個(gè)高度為3的B+Tree如果存滿的話，最多可以放2千萬條索引數(shù)據(jù)（因?yàn)閿?shù)據(jù)需要冗余垦梆，數(shù)值要小于計(jì)算出來的值匹颤，具體沒算），查詢時(shí)最多進(jìn)行3次磁盤IO即可定位到記錄托猩。
最下邊那個(gè)鏈表樣子的指針是做什么用的印蓖？范圍查詢（下圖中應(yīng)該是個(gè)雙向指針）。比如說我們想查找>15的索引對應(yīng)的數(shù)據(jù)京腥。如果按照BTree方式查找赦肃，需要不斷的返回父節(jié)點(diǎn)再次進(jìn)行查詢。而B+Tree通過這個(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ù)在磁盤中是分開存儲(chǔ)的，索引存儲(chǔ)的是磁盤位置剥懒。
InnoDB 索引實(shí)現(xiàn)?
在InnoDB 中,表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個(gè)索引結(jié)構(gòu),這棵樹的葉點(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 要求表中必須要有主鍵批狱，如果沒有顯式指定,則 MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列,則MySQL 自動(dòng)為 InnoDB 表生成一個(gè)隱含字段作為主鍵,類型為長整形裸准。
為什么推薦使用整型的自增主鍵？
因?yàn)槭褂肂+Tree結(jié)構(gòu)存儲(chǔ)赔硫，如果主鍵生成的沒有規(guī)律炒俱，在新增時(shí)，會(huì)引發(fā)B+Tree分裂爪膊，影響效率权悟，如果是自增類型，僅改變末尾處的指針數(shù)據(jù)即可推盛。所以我們要避免使用uuid等這些字段作為表中的主鍵字段峦阁。
