索引
索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。
索引常见的模型
索引的出现是为了提高查询效率，但是实现索引的方式有很多种，常见 的 有哈希表、有序数组和搜索树。
哈希表
- hash值不是递增的，新增数据时会很快
- 因为不是有序的，所以哈希索引做区间查询的速度是很慢的
-
哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎
哈希表示意图
有序数组
- 有序数组在等值查询（二分法）和范围查询场景中的性能非常优秀
-
有序数组更新数据时比较麻烦，只适用于静态存储引擎
有序数组示意图
搜索树
二叉搜索树的特点：每个节点的左儿子小于父节点，父节点又小于右儿子。为了维持O(log(N))的查询复杂度，就需要保持这棵树是平衡二叉树，为了保证平衡，更新的时间复杂度也是O(log(N))。
树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。
InnoDB 的索引模型
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
5条记录R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)
- 根据叶子结点的内容，索引类型分为主键索引和非主键索引
- 主键索引的叶子结点存的是整行数据，在InnoDB里，主键索引也被称为聚簇索引（clustered index）
- 非主键索引的叶子节点内容 是主键的值，在InnoDB里，非主键索引也被称为二级索引（secondary index）
索引维护
当插入数据后，需要考虑叶分裂；当删除数据后，需要考虑叶合并。所以尽量使用自增主键的插入数据模式，减少索引维护的成本。并且主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。
回表
select * from T where k between 3 and 5 ;
回到主键索引树搜索的过程，称为回表。
覆盖索引
select ID from T where k between 3 and 5 ;
这是只需要查ID的值，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表，索引覆盖了查询需求，成为覆盖索引。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
CREATE TABLE `tuser` (
`id` int(11) NOT NULL,
`id_card` varchar(32) DEFAULT NULL,
`name` varchar(32) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`ismale` tinyint(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `id_card` (`id_card`),
KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB
针对上面这个表是否需要再建立一个（身份证号、姓名）的联合索引呢？
最左前缀原则
在建立联合索引的时候，合理安排索引内的字段顺序是非常重要的。如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
如果既有联合查询（a、b），又有基于a、b各自 的查询，查询条件里面只有b的语句，是无法使用(a,b)这个联合索引的，这时候就不得不同时维护 (a,b 、(b) 这两个索引。
索引下推
如果不符合最左前缀原则，会怎么处理？
例如此时的联合索引为(name,age)
mysql> select * from tuser where name like '张 %' and age=10 and ismale=1;
在 MySQL 5.6 之前，当找到name开头字符为“张”的记录时，只能回表，在主键索引上找出数据行，再对比字段age、ismale的值。
而 MySQL 5.6 引入的索引下推优化 (index condition pushdown)，可以在索引遍历 过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
