一、MySQL索引
在 MySQL 中，索引是在存储引擎层实现的，所以不同存储引擎的索引的工作方式并不一样。
1.索引数据结构
- 哈希表：哈希表这种结构适用于只有等值查询的场景，不适合做区间查询，因为哈希表是无序的，区间查询要全表扫描。
- 有序数组：查询效率高，但是更新数据比较麻烦，往中间插入一个记录就必须得挪动后面所有的记录。所以，有序数组索引只适用于静态存储引擎。
- 二叉搜索树：查询和更新的时间复杂度都是 O(log(N))，但是存在树太“高”的问题。二叉树搜索效率最高，但是因为索引会存储在磁盘，树太高会导致磁盘寻址（找对应数据块）次数太多（查询一条数据需要多次磁盘寻址找节点）。
- B+树（“N叉树”）：为了让一个查询尽量少地读磁盘，所以就让树尽量“矮”，就要多分叉。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
2.InnoDB 的索引模型
InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的，每一个索引在 InnoDB 里面对应一棵 B+ 树。
表T：ID为主键， k 上有索引。
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
左边为主键索引（聚簇索引），主键索引叶子节点存储的是整行数据；右边为非主键索引（普通索引、二级索引），叶子节点存储内容是主键的值。使用主键索引查询可以直接获得数据，而使用普通索引需要先搜索得到主键的值，然后再根据主键查询主键索引得到数据（这个过程叫回表）。
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
3.索引维护
当更新或删除数据时，需要更新索引。当在一个已满的数据页插入数据时，则需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。页分裂将原本放在一个页的数据，分到两个页中，整体空间利用率降低大约 50%。
当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。
注：在 InnoDB 中，每个数据页的大小默认是 16KB。
4.为什么建表语句里一定要有自增主键
可以保证每次插入一条新记录，都是追加操作（递增），不会触发叶子节点的分裂，而用业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。此外，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
二、覆盖索引及索引下推
1.覆盖索引
对于T中k作为普通索引，select * from T where k between 3 and 5 该语句会先查找k索引的B+树，找到满足条件的节点后依次回表，所以需要查找N次k的索引B+树，查找N-1次的主键索引B+树（比普通索引少一次）。
为了减少回表次数，对于高频的查询，可以建立联合索引（为了满足覆盖索引）来优化性能。假如（a，b）作为普通索引，如果有许多根据a查询b的需求，则可以建立该索引来提高性能，因为这个请求可以用到覆盖索引，不需要再回表查询整行数据。
2.索引下推
select * from user where name like '张 %' and age=10; 假如存在联合索引（name，age）。
对于该语句，MySQL 5.6 之前，找到满足条件的name后（不查看普通索引B+树中age的值），依次回表。而在MySQL 5.6 引入了索引下推优化（index condition pushdown)， 对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数（也就是在普通索引B+树中判断age是10的记录，才会回表）。
三、MySQL索引选择
1.基数（cardinality）
一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好。
理论上来说假设该索引上没有重复的数据，则基数就是数据的行数，但是实际并不是。因为全部扫描后统计太消耗性能，所以InnoDB采用采样统计，InnoDB 默认会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。
注：使用show index from table命令可以看到索引的基数。当数据行数的修改超过一定值后，会再次重新统计基数。
2.索引选择原则
InnoDB选择索引的时候，MySQL优化器会根据预计扫描的行数来判断选择哪个索引。而预计扫描的行数则根据基数来确定。
注：获取预计扫描行数用explain select …可以看到。
3.重新统计索引信息
如果发现 explain 的结果预估的 rows 值跟实际情况差距比较大，可以使用analyze table xxx 命令来重新统计索引信息。
四、前缀索引（适用于给字符串字段加索引）
1.语句：
alter table SUser add index index2(email(6)); // email前六个字节作为索引
注：使用前缀索引会用不上覆盖索引对查询性能的优化。
2.前缀索引长度选择
需要找到一个合适的区分度，可以使用如下语句判断应该定义多长的前缀索引。
select
count(distinct left(email,4)）as L4,
count(distinct left(email,5)）as L5,
count(distinct left(email,6)）as L6,
count(distinct left(email,7)）as L7,
from SUser;
注：使用前缀索引，定义好长度，就可以做到既节省空间，又不用额外增加太多的查询成本。
