在互聯(lián)網(wǎng)行業(yè)减江，常用的關(guān)系型數(shù)據(jù)庫是MySQL泽本，所以在招聘過程中淘太，面試官一般都會問些關(guān)于MySQL的問題，比如MySQL的優(yōu)化观挎、MySQL的事物特性琴儿、隔離級別段化，以及MySQL索引相關(guān)的原理嘁捷。下面我們就來聊一下MySQL索引相關(guān)的內(nèi)容。
一显熏、索引的數(shù)據(jù)結(jié)構(gòu)
我們在線上遇到慢查詢的情況雄嚣，一般第一個想到的優(yōu)化方式就是給where語句后的字段加索引，雖然效果是立竿見影的喘蟆，但這通常是懶人做法缓升。一方面是因為索引并不是都會生效，可能出現(xiàn)加了索引蕴轨，查詢依舊慢的問題港谊，另一方面，索引會占用磁盤空間橙弱。
但是歧寺，這并不妨礙我們在遇到慢查詢的時候，第一個想到的解決方案就是加索引棘脐，那么斜筐，為什么加了索引之后，就能優(yōu)化慢查詢蛀缝，提升查詢速度顷链？
其實，索引就是一種優(yōu)化查詢的數(shù)據(jù)結(jié)構(gòu)屈梁，MySQL中的索引就是用B+樹實現(xiàn)的嗤练。那么為什么MySQL會選擇B+樹作為索引的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)呢榛了？它和哈希表、完全平衡二叉樹煞抬、B樹有什么不同忽冻？
假設(shè)，我們現(xiàn)在有下面的user表：
① 哈希表
我們知道此疹，hashMap(1.7)底層就是通過哈希表來實現(xiàn)的僧诚，即，數(shù)組+鏈表的方式蝗碎。
哈希表的缺點有兩個: 一湖笨、hash沖突，二蹦骑、只支持精確查詢慈省，不支持范圍查詢，如果我們要某個年齡大于18的用戶眠菇，如下：
select * from user where name = '關(guān)羽'; // 精確查找
select * from user where name > '關(guān)羽'; // 范圍查找
這種情況哈希表并不能實現(xiàn)边败，所以，哈希表不適合做MySQL的索引數(shù)據(jù)結(jié)構(gòu)捎废。
②完全平衡二叉樹
平衡二叉樹的每個節(jié)點都包含下面四部分信息：
- 左指針笑窜，指向左子樹
- 鍵值
- 鍵值所對應(yīng)的數(shù)據(jù)存儲地址
- 右指針，指向右子樹
另外登疗，二叉樹是有序的排截，簡而言之，就是左節(jié)點小于右節(jié)點辐益，所以断傲，平衡二叉樹是支持范圍查找的，但是智政，在精確查找的時候认罩，會涉及到多次，比如续捂，查劉備垦垂，需要查詢?nèi)尾拍苷业剑裙１淼木_查找要慢疾忍。
③ B樹
可以看到乔外，B樹在層級上比平衡二叉樹要少一層，即少一次磁盤IO一罩，原因在于杨幼，B樹中的一個節(jié)點可以存儲多個元素。
④ B+樹
B+樹比B樹要胖一些差购，原因在于B+樹中的非葉子節(jié)點會冗余一分在葉子節(jié)點中四瘫，并且葉子節(jié)點之間用指針相連。
綜上欲逃，我們可以看出找蜜，有三種數(shù)據(jù)結(jié)構(gòu)是適合做MySQL索引的數(shù)據(jù)結(jié)構(gòu)的，平衡二叉樹稳析、B樹洗做、B+樹。這三種數(shù)據(jù)結(jié)構(gòu)都支持精確查找和范圍查找彰居，那么為什么MySQL卻選中了B+樹作為索引的數(shù)據(jù)結(jié)構(gòu)呢诚纸？
其實，索引也是存儲元素的陈惰，當我們的一個表中的數(shù)據(jù)越來越多時畦徘，對應(yīng)的索引文件也會越來越大，這樣就不能把全部的索引文件放在內(nèi)存抬闯，不得不將索引文件存儲在磁盤上井辆，那么選用哪種數(shù)據(jù)結(jié)構(gòu)，能夠提高磁盤的IO效率溶握，就成了參考項杯缺。
如果使用完全平衡二叉樹來查詢“張飛”，則需要四次IO奈虾，而使用B樹的話夺谁，只要三次就可以了廉赔，提升了磁盤ＩＯ效率肉微，而Ｂ+樹和B樹的非葉子節(jié)點是一樣的，只不過是葉子節(jié)點冗余了一份非葉子節(jié)點的數(shù)據(jù)蜡塌。所以碉纳，在精確查找上，B樹和B+樹是一樣的馏艾，而B+樹在范圍查找上優(yōu)于B樹劳曹。
二、 B+樹的節(jié)點到底多大合適
B+樹的一個節(jié)點為一頁或者一頁的整數(shù)倍最為合適琅摩，因為讀取這個節(jié)點的時候铁孵，是按照一頁來讀取的，大于或小于一頁房资，會造成資源浪費蜕劝。
在MySQL的Innodb引擎中，一頁的默認大小是16K（如果操作系統(tǒng)的一頁大小是4K，那么Mysql中一頁=操作系統(tǒng)中4頁）岖沛，可以使用如下命令查看:
show global status like 'Innodbpagesize';
