mysql 不同引擎索引组织方式不同
MyISAM存储引擎，MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址;InnoDB存储引擎，InnoDB是事务型数据库的首选引擎，支持事务安全表（ACID），支持行锁定和外键，InnoDB存储引擎为在主内存中缓存数据和索引而维持它自己的缓冲池。InnoDB将它的表和索引在一个逻辑表空间中，表空间可以包含数个文件（或原始磁盘文件）。这与MyISAM表不同，比如在MyISAM表中每个表被存放在分离的文件中。
当然还有其他引擎，我们只对主流的引擎进行比较
索引结构与算法
从大学的课本我们就知道二叉树的算法可以用于索引检索，但是只有B+树最适合用来作为索引的算法，目前主流的数据库都采用B+ 树索引。原因如下：
- B+ 树在2-4层之间，所以进行索引扫描时磁盘摆动不会太大，加载起来比较快，检索速度快
- B+ 树的数据都在叶子结点，并且都是有序的，这样便于进行磁盘预读，同时在索引扫描时避免排序
聚集索引和非聚集索引
聚集索引就是通过主键来组织的索引，非聚集索引为非主键索引，要查找时先找到辅助索引，然后通过辅助索引查找聚集索引，最后通过聚集索引来检索数据
可选择性
为不影响数据库性能，数据库抽样统计索引的可选择性数据，只有具有高选择性的索引才会被执行计划所采用
联合索引和覆盖索引
联合索引是指对表上的多个列进行索引。联合索引也是一棵B+树，其键值数量大于等于2。键值都是排序的，通过叶子节点可以逻辑上顺序的读出所有数据。
InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。
使用覆盖索引有啥好处？
- 可以减少大量的IO操作
MRR和ICP
MRR 「Multi-Range Read」初步理解 对where条件拆分，减少通过索引查到过多无用的数据；查询索引页叶子节点的主键ID后不是直接读取数据，而是把满足条件的主键ID进行排序，然后在进行数据查找。
MySQL 5.6开始支持Multi-Range Read(MRR)优化。目的是为了减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，这对IO-bound类型的SQL查询语句可带来性能极大的提升。MRR优化可适用于rangeref,eq_ref类型的查询
MRR优化的好处：
a)MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果按照主键进行排序，并按照主键排序的顺序进行书签查找
b)减少缓冲池中页被替换的次数
c)批量处理对键值的查询操作
对于InnoDB和MyISAM存储引擎的范围查询和JOIN查询操作，MRR工作方式如下
a)将查询得到的辅助索引键值存放在一个缓存中，这是缓存中的数据是根据辅助索引键值排序的
b)将缓存中的键值根据RowID进行排序
c)根据RowID的排序顺序来访问实际的数据文件
Index Condition Pushdown (ICP)是MySQL用索引去表里取数据的一种优化。如果禁用ICP，引擎层会穿过索引在基表中寻找数据行，然后返回给MySQL Server层，再去为这些数据行进行WHERE后的条件的过滤。ICP启用，如果部分WHERE条件能使用索引中的字段，MySQL Server 会把这部分下推到引擎层。存储引擎通过使用索引条目，然后推索引条件进行评估，使用这个索引把满足的行从表中读取出。ICP能减少引擎层访问基表的次数和MySQL Server 访问存储引擎的次数。
ICP 「Index Condition Pushdown」初步理解在通过辅助索引查询时进一步过滤where其他条件，前提是where条件的数据在该索引中可以获取到。
参考：
http://blog.itpub.net/15498/viewspace-2629899/
《MySql技术内幕SQL编程》
