B-tree索引
mysql中btree存儲的物理文件大多是balance tree（平衡樹）結(jié)構(gòu)來存儲的。也就是實際存儲數(shù)據(jù)放在葉節(jié)點。而且任何一個葉節(jié)點的最短路徑都一樣?？赡芨鞣N數(shù)據(jù)庫的在存放自己的btree索引時會對存儲結(jié)構(gòu)做改動。例如：innodo的btree實際上是b+tree，在原有的葉節(jié)點除了存放索引等關(guān)鍵信息外，還存儲了后一個葉節(jié)點的指針信息。這是出于加快檢索多個相鄰的葉節(jié)點的效率考慮的。
主鍵索引 ：
葉節(jié)點存放的，除了主鍵的數(shù)據(jù)外，還有其他字段數(shù)據(jù)的以主鍵的有序排列。所以，通過主鍵來訪問數(shù)據(jù)效率是非常高的。
btree索引：
不僅在葉節(jié)點存放索引的相關(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組織的一個索引結(jié)構(gòu)，這棵樹的葉節(jié)點data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。
這種索引叫做聚集索引。
因為InnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個可以唯一標識數(shù)據(jù)記錄的列作為主鍵
所以，innodb檢索直接通過主鍵非常地高效。
與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。換句話說：innodb的輔助索引會引用主鍵作為自己的data域。
聚集索引這種實現(xiàn)方式使得按主鍵的搜索十分高效。
innodb的主鍵不宜過長，以為輔助索引會引用主索引。過長的主索引會導(dǎo)致輔助索引變大。
根據(jù)b+tree的特性，自增字段可以做到和b+tree的leaf node分裂順序一致。所以用自增字段做innodb的主鍵是一個很好的選擇
標準的B+tree
一個平衡的多叉樹，根節(jié)點到各葉節(jié)點的高度差不超過1，同層級節(jié)點之間有指針相互銜接。
這種數(shù)據(jù)結(jié)構(gòu)，從根節(jié)點到葉節(jié)點的檢索效率相當，基于索引的順序掃描，也可以利用雙向指針快速順序移動。效率很高。
所以，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é)點到葉節(jié)點這樣逐級查找。只需要一次hash算法就可定位。
Hash索引
hash索引的檢索效率高于btree，因為它是一次到位，不像btree要從根節(jié)點到枝節(jié)點，再到頁節(jié)點多次的IO訪問。
但是hash 也有很多弊端：
1.僅僅能滿足 "=","IN"和"<=>"，它不能使用范圍查詢。
因為他是通過比較hash值，原先是有序的鍵值，經(jīng)過hash有可能變得不連續(xù)了，so只能用于等值過濾。
2.同理，無法進行數(shù)據(jù)的排序操作，以及 like ‘xxx%’這樣的模糊查詢（模糊查詢，本質(zhì)上還是范圍查詢）
3.不能利用部分索引查詢
因為它是計算組合索引合并后的hash值，而不是單獨計算。對于一個或者多個的組合索引進行查詢的時候，hash索引無法被利用。
4在任何時候都不能避免掃描全表
由于不同的hash索引存在相同的hash值，所以即使?jié)M足某個hash值的記錄條數(shù)，也無法直接在hash索引中完成查詢。還是要通過表中的數(shù)據(jù)進行實際的比較。
5.在遇到大量的重復(fù)鍵，就是hash值相等的情況下，性能不一定比btree高。
因為存在hash沖撞。
在MySQL中，只有HEAP/MEMORY引擎表才能顯式支持哈希索引（NDB也支持，但這個不常用），
InnoDB引擎的自適應(yīng)哈希索引（adaptive hash index）不在此列，因為這不是創(chuàng)建索引時可指定的。
還需要注意到：HEAP/MEMORY引擎表在mysql實例重啟后，數(shù)據(jù)會丟失。
適合用hash索引
SELECT … FROM t WHERE C1 = ?; — 僅等值查詢
大多數(shù)情況下，都會有范圍查詢，模糊查詢這些，用btree索引就行。
