B-tree索引
mysql中btree存儲的物理文件大多是balance tree（平衡樹）結(jié)構(gòu)來存儲的。也就是實(shí)際存儲數(shù)據(jù)放在葉節(jié)點(diǎn)。而且任何一個(gè)葉節(jié)點(diǎn)的最短路徑都一樣。可能各種數(shù)據(jù)庫的在存放自己的btree索引時(shí)會對存儲結(jié)構(gòu)做改動喘落。例如：innodo的btree實(shí)際上是b+tree德崭，在原有的葉節(jié)點(diǎn)除了存放索引等關(guān)鍵信息外，還存儲了后一個(gè)葉節(jié)點(diǎn)的指針信息揖盘。這是出于加快檢索多個(gè)相鄰的葉節(jié)點(diǎn)的效率考慮的眉厨。
主鍵索引 ：
葉節(jié)點(diǎn)存放的，除了主鍵的數(shù)據(jù)外兽狭，還有其他字段數(shù)據(jù)的以主鍵的有序排列憾股。所以，通過主鍵來訪問數(shù)據(jù)效率是非常高的箕慧。
btree索引：
不僅在葉節(jié)點(diǎn)存放索引的相關(guān)信息服球，也有主鍵值。
通過secondary index訪問颠焦，通過相應(yīng)的索引檢索到leaf node斩熊，再通過leaf node中存放的主鍵信息來獲取數(shù)據(jù)行。
MyISAM的索引形式是b+tree,leaf node存放的是數(shù)據(jù)記錄地址伐庭》矍可以看的出來，myisam的索引文件僅僅保存數(shù)據(jù)記錄的地址
MyISAM索引文件和數(shù)據(jù)文件是分離的
它的主索引和輔助索引在結(jié)構(gòu)上沒有區(qū)別圾另，只是主索引要求唯一霸株，而輔助索引可以重復(fù)。
MyISAM的索引方式也叫做“非聚集”的集乔，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分去件。
MyISAM中首先按照b+tree搜索算法搜索索引，如果指定的key存在扰路，則去除data域尤溜，再通過data域的值為地址去讀取相應(yīng)的數(shù)據(jù)記錄。
InnoDB的數(shù)據(jù)文件本身就是索引文件汗唱。
InnoDB中宫莱，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄渡嚣。這個(gè)索引的key是數(shù)據(jù)表的主鍵梢睛，因此InnoDB表數(shù)據(jù)文件本身就是主索引肥印。
這種索引叫做聚集索引识椰。
因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有）深碱，如果沒有顯式指定腹鹉，則MySQL系統(tǒng)會自動選擇一個(gè)可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵
所以，innodb檢索直接通過主鍵非常地高效敷硅。
與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址功咒。換句話說：innodb的輔助索引會引用主鍵作為自己的data域愉阎。
聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效。
innodb的主鍵不宜過長力奋，以為輔助索引會引用主索引榜旦。過長的主索引會導(dǎo)致輔助索引變大。
根據(jù)b+tree的特性景殷，自增字段可以做到和b+tree的leaf node分裂順序一致溅呢。所以用自增字段做innodb的主鍵是一個(gè)很好的選擇
標(biāo)準(zhǔn)的B+tree
一個(gè)平衡的多叉樹，根節(jié)點(diǎn)到各葉節(jié)點(diǎn)的高度差不超過1猿挚，同層級節(jié)點(diǎn)之間有指針相互銜接咐旧。
這種數(shù)據(jù)結(jié)構(gòu)，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的檢索效率相當(dāng)绩蜻，基于索引的順序掃描铣墨，也可以利用雙向指針快速順序移動。效率很高办绝。
所以伊约，B+樹索引被廣泛應(yīng)用于數(shù)據(jù)庫、文件系統(tǒng)等場景孕蝉。
順便說一下碱妆，xfs文件系統(tǒng)比ext3/ext4效率高很多的原因之一就是，它的文件及目錄索引結(jié)構(gòu)全部采用B+樹索引昔驱，而ext3/ext4的文件目錄結(jié)構(gòu)則采用Linked list, hashed B-tree疹尾、Extents/Bitmap等索引數(shù)據(jù)結(jié)構(gòu)，因此在高I/O壓力下骤肛，其IOPS能力不如xfs纳本。
哈希索引就是把鍵值通過hash算法，轉(zhuǎn)化為hash值腋颠，檢索不需要像btree那樣從根節(jié)點(diǎn)到葉節(jié)點(diǎn)這樣逐級查找繁成。只需要一次hash算法就可定位。
Hash索引
hash索引的檢索效率高于btree淑玫，因?yàn)樗且淮蔚轿唤硗螅幌馼tree要從根節(jié)點(diǎn)到枝節(jié)點(diǎn)，再到頁節(jié)點(diǎn)多次的IO訪問絮蒿。
但是hash 也有很多弊端：
1.僅僅能滿足 "=","IN"和"<=>"尊搬，它不能使用范圍查詢。
因?yàn)樗峭ㄟ^比較hash值土涝，原先是有序的鍵值佛寿，經(jīng)過hash有可能變得不連續(xù)了，so只能用于等值過濾但壮。
2.同理冀泻，無法進(jìn)行數(shù)據(jù)的排序操作常侣，以及 like ‘xxx%’這樣的模糊查詢（模糊查詢，本質(zhì)上還是范圍查詢）
3.不能利用部分索引查詢
因?yàn)樗怯?jì)算組合索引合并后的hash值弹渔，而不是單獨(dú)計(jì)算胳施。對于一個(gè)或者多個(gè)的組合索引進(jìn)行查詢的時(shí)候，hash索引無法被利用肢专。
4在任何時(shí)候都不能避免掃描全表
由于不同的hash索引存在相同的hash值巾乳，所以即使?jié)M足某個(gè)hash值的記錄條數(shù)，也無法直接在hash索引中完成查詢鸟召。還是要通過表中的數(shù)據(jù)進(jìn)行實(shí)際的比較胆绊。
5.在遇到大量的重復(fù)鍵，就是hash值相等的情況下欧募，性能不一定比btree高压状。
因?yàn)榇嬖趆ash沖撞。
在MySQL中跟继，只有HEAP/MEMORY引擎表才能顯式支持哈希索引（NDB也支持种冬，但這個(gè)不常用），
InnoDB引擎的自適應(yīng)哈希索引（adaptive hash index）不在此列舔糖，因?yàn)檫@不是創(chuàng)建索引時(shí)可指定的娱两。
還需要注意到：HEAP/MEMORY引擎表在mysql實(shí)例重啟后抖所，數(shù)據(jù)會丟失崔涂。
適合用hash索引
SELECT … FROM t WHERE C1 = ?; — 僅等值查詢
大多數(shù)情況下，都會有范圍查詢耘擂，模糊查詢這些摇庙，用btree索引就行旱物。
