一、存儲引擎的比較
注：上面提到的B樹索引并沒有指出是B-Tree和B+Tree索引耕捞，但是B-樹和B+樹的定義是有區(qū)別的衔掸。
在 MySQL 中，主要有四種類型的索引俺抽，分別為：B-Tree 索引敞映， Hash 索引， Fulltext 索引和 R-Tree 索引磷斧。
B-Tree 索引是 MySQL 數(shù)據(jù)庫中使用最為頻繁的索引類型振愿，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引弛饭，而且只支持索引單個(gè) AUTO_INCREMENT 列冕末。
不僅僅在 MySQL 中是如此，實(shí)際上在其他的很多數(shù)據(jù)庫管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型侣颂，這主要是因?yàn)?B-Tree 索引的存儲結(jié)構(gòu)在數(shù)據(jù)庫的數(shù)據(jù)檢索中有非常優(yōu)異的表現(xiàn)档桃。
一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來存儲的憔晒，也就是所有實(shí)際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node(葉子節(jié)點(diǎn)) 藻肄，而且到任何一個(gè) Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引拒担。
當(dāng)然嘹屯，可能各種數(shù)據(jù)庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時(shí)候會對存儲結(jié)構(gòu)稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實(shí)際使用的存儲結(jié)構(gòu)實(shí)際上是 B+Tree从撼，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造州弟，在每一個(gè)Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲了指向與該 Leaf Node 相鄰的后一個(gè) LeafNode 的指針信息（增加了順序訪問指針）低零，這主要是為了加快檢索多個(gè)相鄰 Leaf Node 的效率考慮呆馁。
InnoDB是Mysql的默認(rèn)存儲引擎(Mysql5.5.5之前是MyISAM）
可能對于沒有了解過索引的猿友這樣看這篇文章十分吃力，這類猿友有必要先對Mysql索引有個(gè)大體的了解毁兆。
接下來我們先看看B-樹浙滤、B+樹的概念。弄清楚气堕，為什么加了索引查詢速度會加快纺腊？
二畔咧、B-樹、B+樹概念
B樹
即二叉搜索樹：
所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)兒子（Left和Right）揖膜；
所有結(jié)點(diǎn)存儲一個(gè)關(guān)鍵字誓沸；
非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹壹粟；
如：
B-樹
是一種多路搜索樹（并不是二叉的）：
定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子拜隧；且M>2；
根結(jié)點(diǎn)的兒子數(shù)為[2, M]趁仙；
除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]洪添；
每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字；（至少2個(gè)關(guān)鍵字）
非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1雀费；
非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]干奢；且K[i] < K[i+1]；
非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]盏袄；其中P[1]指向關(guān)鍵字小于K[1]的子樹忿峻，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹辕羽；
-
所有葉子結(jié)點(diǎn)位于同一層逛尚；
如：（M=3）
image.png
B-樹的搜索，從根結(jié)點(diǎn)開始刁愿，對結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找黑低，如果命中則結(jié)束，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)酌毡；重復(fù)克握，直到所對應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)枷踏；
B-樹的特性：
關(guān)鍵字集合分布在整顆樹中菩暗；
任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；
搜索有可能在非葉子結(jié)點(diǎn)結(jié)束旭蠕；
其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找停团；
自動層次控制；
由于限制了除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)掏熬，至少含有M/2個(gè)兒子佑稠，確保了結(jié)點(diǎn)的至少利用率。
所以B-樹的性能總是等價(jià)于二分查找（與M值無關(guān)）旗芬，也就沒有B樹平衡的問題舌胶；
由于M/2的限制，在插入結(jié)點(diǎn)時(shí)疮丛，如果結(jié)點(diǎn)已滿幔嫂，需要將結(jié)點(diǎn)分裂為兩個(gè)各占M/2的結(jié)點(diǎn)辆它；刪除結(jié)點(diǎn)時(shí)，需將兩個(gè)不足M/2的兄弟結(jié)點(diǎn)合并履恩；
B+樹
B+樹是B-樹的變體锰茉，也是一種多路搜索樹：
其定義基本與B-樹同，除了：
非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同切心；
非葉子結(jié)點(diǎn)的子樹指針P[i]飒筑，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）；
為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針绽昏；
-
所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)协屡；
如：（M=3）
image.png
B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中）而涉，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找著瓶；
B+的特性：
所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引）联予，且鏈表中的關(guān)鍵字恰好是有序的啼县；
不可能在非葉子結(jié)點(diǎn)命中；
非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）沸久，葉子結(jié)點(diǎn)相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層季眷；
更適合文件索引系統(tǒng)；
三卷胯、建索引的幾大原則
最左前綴匹配原則子刮，非常重要的原則，mysql會一直向右匹配直到遇到范圍查詢(>窑睁、<挺峡、between、like)就停止匹配担钮，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)順序的索引橱赠，d是用不到索引的，如果建立(a,b,d,c)的索引則都可以用到箫津，a,b,d的順序可以任意調(diào)整狭姨。
=和in可以亂序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意順序苏遥，mysql的查詢優(yōu)化器會幫你優(yōu)化成索引可以識別的形式
盡量選擇區(qū)分度高的列作為索引,區(qū)分度的公式是count(distinct col)/count(*)饼拍，表示字段不重復(fù)的比例，比例越大我們掃描的記錄數(shù)越少田炭，唯一鍵的區(qū)分度是1师抄，而一些狀態(tài)、性別字段可能在大數(shù)據(jù)面前區(qū)分度就是0教硫，那可能有人會問司澎，這個(gè)比例有什么經(jīng)驗(yàn)值嗎欺缘？使用場景不同，這個(gè)值也很難確定挤安，一般需要join的字段我們都要求是0.1以上谚殊，即平均1條掃描10條記錄
索引列不能參與計(jì)算，保持列“干凈”蛤铜，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引嫩絮，原因很簡單，b+樹中存的都是數(shù)據(jù)表中的字段值围肥，但進(jìn)行檢索時(shí)剿干，需要把所有元素都應(yīng)用函數(shù)才能比較，顯然成本太大穆刻。所以語句應(yīng)該寫成create_time = unix_timestamp(’2014-05-29’);
盡量的擴(kuò)展索引置尔，不要新建索引。比如表中已經(jīng)有a的索引氢伟，現(xiàn)在要加(a,b)的索引榜轿，那么只需要修改原來的索引即可
