1，BTREE是多叉树，多路径搜索树。有N棵子树的节点它包含N-1个关键字，例如，有3个子树的非叶子节点，那么就有2个关键字，每个关键字不保存数据，只用来存储索引（在索引存储数据时，将索引指向关键字的值也存储进来。最终实现key = &get; value结构）。所有的数据最终都要落在叶子节点，所有的叶子节点包括关键字信息以及指向这些关键字的指针，而且叶子节点是根据关键字大小、顺序链接的。所有的叶子节点都必须有个链表指针把数据串起来。所以，所有非叶子节点可以看成索引部分，包括子树中最大值或最小值关键字等信息。在btree索引下，获取数据时只需要从索引树的最小节点，一直不断的向右进行遍历就可以快速的得到想要的数据（这种遍历有指针把数据串起来），不需要回溯到根节点， 这样就可以理解为什么innodb的主键索引不能用离散的数据。

下图为2层btree结构：

2，哈希索引建立在哈希表的基础上，它对每个值采用精确查找。每一行都需要先计算哈希码，比较好的哈希算法算出比较低的重复的度，这样效率相对高一些。如果算出来的值是一样的，那么它需要再进行判断哪个值才是想要的值，所以说在表里面采用哈希索引，但是重复度又比较高，那么哈希索引效率就比较低。 

HASH索引PK BTREE索引：大量不同数据等值精确查询，HASH索引效率通常比BTREE高；HASH索引不支持联合索引的最左匹配规则（where a =? and  b=? ,index(a,b,c)这样无法同时使用a,b,c，相当于是范围查询）；HASH索引不支持排序；HASH索引不支持模糊查找；

下图为哈希索引：

3，聚集索引，其实就是索引的组织方式，整个表存储的逻辑顺序根聚集索引的顺序是一致的，也就是说聚集索引决定了整个表的物理的存储的逻辑顺序。mysql一个表只支持一个聚集索引。在innodb里面聚集索引就是整个表，表就是聚集索引，因为innodb的聚集索引后面是整行数据，在聚集索引btree里面每个叶子节点最终存储每行数据，这就是为什么在innodb里面没有任何条件count （*），它会优先选择普通索引来完成扫描，而不是采用主键索引，因为如果扫聚集索引，扫描的数据量更大，产生的IO更大，如果扫描普通辅助索引，那么它的数据结构通常来讲比主键索引小。

innodb的普通索引叶子节点里面存储着主键索引的键值。聚集索引决定了物理表的存储顺序，如果聚集索引频繁修改，可能会导致修改存储的顺序，那么这个行数据会产生位移，产生数据离散IO。如果新增的数据太过离散，也会导致聚集索引存储的位置相应的离散，也会导致随机IO.

聚集索引的选择：

a,含有大量非重复值的列；

b,被连续（顺序）访问的列；

c,返回大量结果集的查询；

案例：

如果一个表很大，有1/3数据要删除,如果是随机删除，会产很多空洞，删完后产生的空洞不写入，没什么影响，但这种删除比较慢，因为需要对btree进行随机扫描。删完后索引树会进行自旋，如果它的page填充因子比较低，例如把2页合并成1页，在合并中进行写入会比较慢。 删完后可以执行alter  table engine=innodb 来整理碎片，但是会锁表。建议使用pt-osc来完成表空间回收。

MySQL的btree索引和hash索引&聚集索引