索引的目的是为了提高查询效率，就像一本书的目录，可以根据目录快速定位到章节。
一、索引常见的模型
索引常见的模型有三种：哈希表、有序树、搜索树。
1.1 哈希树
哈希树，是以哈希表的形式存储。如下图所示一个数据库表的存储方式。哈希表的链方式扩展。
如上图一所示：如果用户A和用户B查询计算所得哈希值都是Key1，需要遍历Key1上对应的链表，查找到对应的值。
在插入数据时，为了提高插入效率，插入的数据直接在链表后面加，所以链表上的数据是无序。但是，如果需要进行区间查找，此时的查找效率很低。
哈希表只适合等值查询。
1.2 有序表
有序表是将索引存储在数组中，数组是有序排列的。如图二所示：
假设需要查询key3的索引值，那么采用二分查找可以在log(N)的时间内查询。如果是区间查询，也可以找到最大值和最小值的区间。但是更新数据就比较麻烦，更新数据需要进行数据的移动，所以有序表索引只适用于静态存储索引，对于不更新数据的表比较实用。
1.3 二叉搜索树
二叉搜索树的特点是：每个节点的左子节点小于父节点，父节点又小于右儿子。这样如果你要查 Key1的话，按照图中的搜索顺序就是按照 Key8-> Key4-> Key2-> Key1这个路径得到。这个时间复杂度是 O(log(N))。
以 InnoDB 的一个整数字段索引为例，索引存储是个N差树，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次。
1.4 B+树索引
Innodb采用的是B+树方式的存储索引
B+树特点：
1、有k个子结点的结点必然有k个关键码。
2、非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
3、树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
B+树的索引适用于等值查询，区间查询，同样插入元素效率也比较高。
二、Inndb的索引
2.1 主键索引和普通索引
主键索引就是Sql语句查询时，查询条件是主键的值；如select* from t where id=1;id是主键，这个查询语句只需要在主键索引树查询id=1的值，主键索引表存储的数据域是id=1的主键对于的所有数据域。
普通索引就是Sql语句查询时，查询条件是普通索引；如select * from t where name='a'； name是普通索引，这个查询语句需要先在name的索引树上查询name对于的主键I的，然后再回表在主键索引上查找name对于Id的数据域。
尽量使用主键查询。显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。
2.2 覆盖索引
Sql语句select * from t where k between 3 and 5；如下语句执行过程：
1、在 k 索引树上找到 k=3 的记录，取得 ID = 300；
2、再到 ID 索引树查到 ID=300 对应的 R3；
3、在 k 索引树取下一个值 k=5，取得 ID=500；
4、再回到 ID 索引树查到 ID=500 对应的 R4；
5、在 k 索引树取下一个值 k=6，不满足条件，循环结束。
可以看到，这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）。有什么方法可以改进呢？
如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。
2.3 最左前缀原则
思考这样一个问题，如果为每一种查询都设计一个索引，索引是不是太多了。如果我现在要按照市民的身份证号去查他的家庭地址呢？虽然这个查询需求在业务中出现的概率不高，但总不能让它走全表扫描吧？反过来说，单独为一个不频繁的请求创建一个（身份证号，地址）的索引又感觉有点浪费。应该怎么做呢？
当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了，只需要再建立一个b索引。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。可以通过考虑联合索引a和b的位置。
如果一组数据(a,1)(a,2)(a,3)(b,1)(b,2)，如果要查询值为a的数据，那么根据最左匹配原则，可以通过联合索引（a,b）查询到前三个数据。
Innodb 的count(*)是全表扫描，所以只需count(*)会很慢，一般都是存储在表里，或者缓存中。
注：参考丁奇MySql实战
