从一条sql来理解数据库索引
1示例
可以看到这个表采用了联合主键，我们知道数据库主键默认给创建索引的，那么已经插入了5条数据，我采用两种方式查询来查看查询效率。
sql1:
sql2:
通过执行计划查看sql2中的key是null,意思是没有用到索引，所以sql2的查找效率没有sql1的高。同一个索引，为何1比2效率高？有过优化经验的都知道，这是mysql查询优化中最重要的原则，最左匹配。那么为何会如此，原理是什么？
我们从三个地方来理解:
磁盘的读写原理
B+树
B+树在mysql中应用
2磁盘读写原理
以上是磁盘的构造，当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。
为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点：
1）首先必须找到柱面，即磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，
2）然后目标扇区旋转到磁头下，即磁盘旋转将目标扇区旋转到磁头下。这个过程耗费的时间叫做旋转时间。
这就是一个机械硬盘的大概寻找过程，具体构造原理我们不再多说，我们看读取一个数据的流程。
一次访盘请求（读/写）完成过程由三个动作组成：
1）寻道（时间）：磁头移动定位到指定磁道
2）旋转延迟（时间）：等待指定扇区从磁头下旋转经过
3）数据传输（时间）：数据在磁盘与内存之间的实际传输
因此在磁盘上读取扇区数据（一块数据）所需时间：
Ti/o=tseek +tla + n *twm
tseek 为寻道时间
tla为旋转时间
twm 为传输时间
以上中磁盘IO代价主要花费在查找时间tseek上，如果进行随机读取的话，因为要不断的寻道，所以过度的时间消耗在寻道上了，因此保证磁盘顺序读取的很重要，摇臂只需要寻找1次磁道并由磁头进行读取,只需要1次就可以成功读取。
我们应该尽量将相关信息存放在同一盘块，同一磁道中，或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间tseek。因此
要磁盘读写快需要保证2点:
1、查找次数少
2、读取的信息连续
3B-Tree&B+Tree
在了解了磁盘读取原理之后，我需要基于此原理来找到适合这种存储的数据结构，以此在有限的条件下，更高和更快的利用磁盘物理性能。
定义:
我们先看下B树的定义，然后图解分析:
1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字是有序的：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；
基于上面的定义，我们看出3个关键点:
1、根节点的儿子最少需要2个
2、每个节点都会有关键字，非叶子节点还有儿子，且儿子数量=关键字数量+1
3、同一层关键字从左树到右树顺序升序排序
图例:
基于上面的几个关键点，我们可以看到B-Tree很符合磁盘的读取物理结构.
保持键值有序，以顺序遍历
使用层次化的索引来最小化磁盘读取
上文说过一般使用磁盘I/O次数评价索引结构的优劣，所以，B-Tree在搜索数据方面很高效，假设有N个key,平均检索单个key的渐进复杂度为O(logdN)。B-tree很适合文件索引和数据存储，而B+Tree在索引方面会比B-Tree更有优势，下面我们再看下B-Tree的一份变种，B+Tree。
B+树定义B+Tree其定义基本与B-Tree相同，同时有一些区别:
１. 非叶子结点的儿子数=关键字个数，而B-tree是儿子数=关键字数+1；
２. B+树中只有叶子节点会带有指向记录的指针，所有数据都保存在叶子节点，而B树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点中。
３. 为所有叶子结点增加一个链指针,把所有的叶子节点连接在一起；
４. 所有关键字都在叶子结点出现；
基于这个对比我们很容易看到B+Tree的优点:
1. 非叶子节点不会带上data，这样，一个块中可以容纳更多的索引项，一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。
2. 叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。
那么基于此，我们可以看出B+Tree更适合外存索引，因为B+Tree内节点去掉了data域，在更低深度的基础上存储更多的数据，如此磁盘查找次数以及单个块的利用率上要更高。
这就是为何多数数据库的索引采用B+Tree了:
B+树更适合外部存储,由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B+树单次磁盘IO的信息量大于B-树,I/O效率更高。
4mysql的索引
MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，比如MyISAM中，索引和数据是分离的，叶子的data节点存储数据地址，而InnoDB是采用聚集索引。
MyISAM索引实现
MyISAM的索引方式也叫做“非聚集”的,索引和数据是分离的，就是说使用B+Tree作为索引结构，索引文件仅仅保存数据记录的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
InnoDB的索引也是采用B+Tree作为索引结构，不过它主要有以下2个特点：
1、聚集索引
InnoDB的数据文件本身就是索引文件，即表中数据按主键顺序存放，树的叶节点data域保存了完整的数据记录。而聚集索引就是按每张表的主键构造一颗B+树，并且每个叶节点直接存表的行数据。每张表只能有一个聚集索引（一个主键）。
聚集索引的另一个好处是它对于主键的排序查找和范围的速度非常快。叶节点的数据就是我们要找的数据。
2、辅助索引
InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。
辅助索引的存在并不影响数据再聚集索引中的组织，因此一个表可以有多个辅助索引。当通过辅助索引查找数据时，innodb会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键。然后再通过主键索引找到一行完整的数据。
辅助索引叶级别不包含行的全部数据，叶级别除了包含行的键值以外，每个索引行还包含了一个书签（bookmark），该书签告诉innodb存储引擎，哪里可以找到与索引对应的数据。
因此不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
1、什么时候使用索引
只有访问高选择性字段并取出很少一部分数据时，该字段加B+索引是非常有效的。但是当取出的数据行占表中大部分数据时，数据库就不会使用B+索引了。
比如对于性别，地区类型字段，他们取值范围很小，即低选择性。这时加B+索引是没有必要的。相反，某个字段取值范围很广，如姓名，几乎没有重复，即高选择性，则使用B+索引是比较合适的。
2、辅助索引的优化
辅助索引的页节点包含主键，但是辅助索引的叶节点并不包含完整的行数据信息，因此，innodb存储引擎总是会从辅助索引的叶节点判断是否能得到数据。
3、联合索引的优化
在第一部分的示例中，采用的是联合索引，联合索引还是一个B+树，不同的是联合索引键值的数量不是1，而是大于等于2，索引的数据包含多列(col1, col2, col3…)，在索引中依次按照col1, col2, col3排序。比如我基于示例1中索引存储的方式:
图中每个节点上有两个键值，(1,1),(1,2),(2,1),(2,4),(3,1),(3,2), 数据按(a,b)顺序进行排列，同时a的值是有序的1、2、3、4而b的值是无序的1、2、1、4、1、2.
因此在以下情况下，针对联合查询的效率是最高的,能够用到B+Tree树:
全列匹配如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀
•查询条件没有指定索引第一列
•查询条件中含有函数或表达式
参考
MySQL5.1参考手册 - http://dev.mysql.com/doc/refman/5.1/zh/index.html
MySQL索引背后的数据结构及算法原理 -http://blog.codinglabs.org/articles/theory-of-mysql-index.html
理解B+树算法和Innodb索引