MySQL innodb的B+樹到底長什么樣，為什么MySQL要這樣設(shè)計(jì)？
背景
最近也許是我們公司給的活動(dòng)太給力，業(yè)務(wù)數(shù)據(jù)量劇增，于是要考慮優(yōu)化數(shù)據(jù)庫，作為程序猿的我們都知道數(shù)據(jù)是我們的命脈，我們做的工作就是處理數(shù)據(jù)，優(yōu)化數(shù)據(jù)是我們一直要面臨的問題。
MySQL優(yōu)化維度
一般優(yōu)化數(shù)據(jù)庫都需要從以下四個(gè)維度進(jìn)行：
- 硬件
- 系統(tǒng)配置
- 數(shù)據(jù)庫表結(jié)構(gòu)
- SQL 及索引
對(duì)于寫業(yè)務(wù)的我們的最直接就是SQL及索引優(yōu)化，效果最顯著性、價(jià)比最高的是索引優(yōu)化。
認(rèn)識(shí)索引
索引是幫助數(shù)據(jù)庫(Mysql)高效獲取數(shù)據(jù)的排好順序的數(shù)據(jù)結(jié)構(gòu)。
原理
通過不斷的縮小想要獲得數(shù)據(jù)的范圍來篩選出最終想要的結(jié)果，同時(shí)把隨機(jī)的事件變成順序的事件，也就是我們總是通過同一種查找方式來鎖定數(shù)據(jù)。
MySQL索引的數(shù)據(jù)結(jié)構(gòu)有以下幾種：
- Hash表
- B+樹
使用Hash算法作為索引，有以下問題，所以大部分我們選擇的是BTREE。
- 存在Hash碰撞。
- 只能精確查找，無法用于局部查找和范圍查找。
MySQL的B+樹
我們先來回顧下大學(xué)數(shù)據(jù)結(jié)構(gòu)里面的B+樹，長這個(gè)樣子。
MySQL中的B+數(shù)其實(shí)是對(duì)傳統(tǒng)的B+樹做了改進(jìn)。
將葉子節(jié)點(diǎn)的數(shù)據(jù)單向指針變成雙向指針，樹高為2。
MySQL每次查1條數(shù)據(jù)都會(huì)查出1頁數(shù)據(jù)(16K)，然后在內(nèi)存里面遍歷，減少IO，大大提高查詢效率。
Mysql 在插入數(shù)據(jù)后，會(huì)自動(dòng)給我們排序。為什么要這樣做呢?
1.先看一個(gè)例子，查詢一條不存在的數(shù)據(jù)。
如果排序后，只用遍歷到第4條記錄，就可以不用查了，如果不排序，就要遍歷所有的數(shù)據(jù)。
2.比較多的數(shù)據(jù)查詢，還是一頁數(shù)據(jù)。
在頁模式底部存儲(chǔ)的數(shù)據(jù)，采用了鏈表的結(jié)構(gòu)，插入比較快，但是查詢比較慢，數(shù)據(jù)量比較大的時(shí)候就需要用空間換時(shí)間，給頁面加個(gè)目錄，先去查頁目錄(通過二分法查找)。不加目錄則需要查13次，加了目錄只需要3次就就可以找到數(shù)據(jù)。這是排序的最主要原因。
3.隨著數(shù)據(jù)量的進(jìn)一步增大，會(huì)出現(xiàn)很多頁數(shù)據(jù)，然后再對(duì)多頁數(shù)據(jù)進(jìn)行索引，即采用了頁目錄的目錄項(xiàng)，從而管理頁，而頁目錄管理行。
目錄頁的本質(zhì)也是頁，存的數(shù)據(jù)是普通頁的地址。所以不管是目錄頁還是頁目錄，都和數(shù)據(jù)存放在一起。這就是聚簇索引的由來(即主鍵索引和數(shù)據(jù)放在一起)。這樣就形成了B+樹。
一棵樹存放的數(shù)據(jù)量
一行存放數(shù)據(jù)大小按1k算，則一頁存放16行數(shù)據(jù)。高度為3的b +樹，主鍵為BigInt(占8個(gè)字節(jié))，innodb 指針占(6個(gè)字節(jié))，就可以存放(16*1024/(8+6)*(16*1024/(8+6)*16=2千多萬行數(shù)據(jù)。這就是一般一個(gè)表的數(shù)據(jù)超過2千萬就不建議走索引，要分庫分表的原因了。這樣的結(jié)構(gòu)就可以使得2千萬的數(shù)據(jù)，只需要3次IO.
雙向指針的原因
范圍查找時(shí)，如果查找小于某個(gè)值的記錄，就需根據(jù)指針要反向查找，所以需要反向指針。
回表
當(dāng)有多個(gè)字段組成組合索引時(shí)，此時(shí)的索引是非聚簇索引，葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，存儲(chǔ)的是數(shù)據(jù)行地址，因?yàn)閿?shù)據(jù)量比較大。這樣查出后，通過記錄主鍵反查完整記錄。這就是回表。
注意
InnoDB中一定有主鍵索引，主鍵一定是聚簇索引，如果沒有則會(huì)使用一個(gè)unique索引作為主鍵索引，如果沒有unique索引，則會(huì)使用數(shù)據(jù)庫內(nèi)部的一個(gè)隱藏行id來當(dāng)作主鍵索引。有且只有一個(gè)聚簇索引。非聚簇索引都需要回表。
