1. 索引分类
我们可以按照四个角度来分类索引。
- 按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。
- 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。
- 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。
- 按「字段个数」分类：单列索引、联合索引。
2. B树和B+树
2.1 B 树（ B- 树）
- 关键字分布在整棵树的所有节点。
- 任何一个关键字 出现且只出现在一个节点中。
- 搜索有可能在 非叶子节点 结束。
- 其搜索性能等价于在关键字全集内做一次二分查找。如下图所示：
2.2 B+ 树
- 非叶子节点的子树指针与关键字个数相同。
- 非叶子节点的子树指针 P[i]，指向关键字属于 [k[i],K[i+1]) 的子树（注意：区间是前闭后开)。
- 为所有叶子节点增加一个链指针。
- 所有关键字都在叶子节点出现。
2.3 B+树 查询
- InnoDB 的数据是按「数据页」为单位来读写的，也就是说，当需要读一条记录的时候，并不是将这个记录本身从磁盘读出来，而是以页为单位，将其整体读入内存。
- 如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作「回表」，也就是说要查两个 B+ 树才能查到数据。
- 不过，当查询的数据是主键值时，因为只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据。
2.4 为什么选用B+树
1、B+Tree vs B Tree
B+树的高度比较稳定，因为它的非叶子节点不会保存数据，只保存键值和指针的情况下，一个页能承载大量的数据。
- B+ 树的磁盘读写代价更低。B+ 树的内部没有指向关键字具体信息的指针，所以其内部节点相对 B 树更小，如果把所有关键字存放在同一块盘中，那么盘中所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相应的，IO 读写次数就降低了。
- 树的查询效率更加稳定。B+ 树所有数据都存在于叶子节点，所有关键字查询的路径长度相同，每次数据的查询效率相当。而 B 树可能在非叶子节点就停止查找了，所以查询效率不够稳定。
- B+ 树只需要去遍历叶子节点就可以实现整棵树的遍历。
2. B+Tree vs 二叉树
对于有 N 个叶子节点的 B+Tree，其搜索复杂度为O(logdN)，其中 d 表示节点允许的最大子节点个数为 d 个。
在实际的应用当中， d 值是大于100的，这样就保证了，即使数据达到千万级别时，B+Tree 的高度依然维持在 3到4 层左右，也就是说一次数据查询操作只需要做 3到4 次的磁盘 I/O 操作就能查询到目标数据。
而二叉树的每个父节点的儿子节点个数只能是 2 个，意味着其搜索复杂度为 O(logN)，这已经比 B+Tree 高出不少，因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。
2.3 B+Tree vs Hash
Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。
但是 Hash 表不适合做范围查询，它更适合做等值的查询，这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。
2.5 B+ 树存储多少数据
InnoDB存储引擎它也是有最小存储单位的，叫做页（Page），默认大小是16kb。页可以放一行一行的数据（叶子节点），也可以放主键+指针（非叶子节点）。
假如我们的主键id为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节。这样算下来就是 16*1024 / 14 = 1170，就是说一个页上可以存放1170个指针。
一个指针指向一个存放记录的页，一个页里可以放16条数据，那么一颗高度为2的B+树就可以存放 1170 * 16=18720 条数据。同理，高度为3的B+树，就可以存放 1170 * 1170 * 16 = 21902400 条1k数据的记录。
B+树的高度一般为2-4层，就可以满足千万级数据的存储。
查找数据的时候，一次页的查找代表一次IO，那我们通过主键索引查询的时候，其实最多只需要2-4次IO就可以了。
3. 聚集索引和非聚集索引
3.1 InnoDB 和 MyISAM 区别
InnoDB 是由一个聚集索引和非聚集索引构成。MyISAM 全是非聚集索引。
但是无论是什么，底层的数据结构都是用 B+树实现的。
1. MyISAM 非聚集索引
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
非聚簇索引的主键索引和辅助索引两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已。
主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。
由于索引树是独立的，通过辅助键检索无需访问主键的索引树。
索引文件（.MYI）和数据文件（.MYD）文件是分离的, 索引文件仅保存数据记录的地址(指针去查找)。
2. InnoDB 聚集索引
- 聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。
- 聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树数据结构一样，每个数据页都通过一个双向链表来进行链接。
- 由于实际的数据页只能按照一棵 B+ 树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在 B+ 树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。
- 聚集索引的存储并不是物理上连续的，而是逻辑上连续的。
- 如果一个主键被定义了，那么这个主键就是作为聚集索引。如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引。如果没有主键也没有合适的唯一索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增。
- 聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。
3.2 InnoDB的聚集索引和非聚集索引
在数据库中，B+ 树的高度一般都在 2～4 层，这也就是说查找某一键值的行记录时最多只需要 2 到 4 次 IO，这倒不错。因为当前一般的机械磁盘每秒至少可以做 100 次 IO，2～4 次的 IO 意味着查询时间只需 0.02～0.04 秒。
1. InnoDB 是由一个聚集索引和非聚集索引构成
数据库中的B+树索引可以分为聚集索引（clustered inex）和辅助索引（secondary index）。辅助索引有时也称非聚集索引（non-clustered index）。
但是不管是聚集还是辅助的索引，其内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据。聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。
2. InnoDB 非聚集索引
叶子节点并不包含行记录的全部数据（只有索引字段本身的数据，废话）。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。
如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问以得到最终的一个数据页。
3.3 总结
例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段int作为主键则是一个很好的选择。
4. 索引机制
4.1 查看索引
1 | SHOW INDEX FROM table_name; |
Cardinality：非常关键的值，表示索引中唯一值的数目的估计值。Cardinality表的行数应尽可能接近1，如果非常小，那么用户需要考虑是否可以删除此索引。
Null：是否索引的列含有NULL值。可以看到idx_b这里为Yes，因为定义的列b允许NULL值。
4.2 Cardinality
Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。
但是这个值并不是实时更新的，如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。
对两条基本一样的语句执行EXPLAIN，但是最终出来的结果不一样：一个使用索引，另外一个使用全表扫描。这时最好的解决办法就是做一次ANALYZE TABLE的操作。因此我建议在一个非高峰时间，对应用程序下的几张核心表做ANALYZE TABLE操作，这能使优化器和索引更好地为你工作。
在InnoDB存储引擎中，Cardinality统计信息的更新发生在两个操作中：INSERT和UPDATE。但是表中1/16的数据已发生过变化，或者stat_modified_counter＞2 000 000 000
4.3 覆盖索引
InnoDB存储引擎支持覆盖索引（covering index，或称索引覆盖），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。
对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为（primary key1，primary key2，…，key1，key2，…）。例如，下列语句都可仅使用一次辅助联合索引来完成查询：
1 | SELECT key2 FROM table WHERE key1=xxx； |
覆盖索引的另一个好处是对某些统计问题而言的。
1 | SELECT COUNT(*)FROM buy_log; |
InnoDB存储引擎并不会选择通过查询聚集索引来进行统计。由于buy_log表上还有辅助索引，而辅助索引远小于聚集索引，选择辅助索引可以减少IO操作。
1 | SELECT COUNT(*)FROM buy_log |
表buy_log有（userid，buy_date）的联合索引，这里只根据列b进行条件查询，一般情况下是不能进行该联合索引的，但是这句SQL查询是统计操作，并且可以利用到覆盖索引的信息，因此优化器会选择该联合索引。
4.4 强制使用某个索引
如果用户确定指定某个索引来完成查询，那么最可靠的是使用FORCE INDEX，而不是USE INDEX。
6. 索引方案
6.1 建立索引机制
最左前缀匹配原则（重要，重要，重要）
复合索引(col1, col2, col3)，能使用的是(col1), (col1, col2), (col1, col2, col3)。 (col1, col3)会启用(col1)的索引查询
ESR原则
精确(equal)匹配的字段放在最前面，排序(sort)条件放中间，范围(range)匹配的字段放在最后面
尽量选择区分度高的列作为索引
区分度的公式是 count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1。
使用短索引
例如，有一个CHAR(200)列，如果在前10个或20个字符内，多数值是唯一的，那么就不要对整个列进行索引。对前10个或者20个字符进行索引能够节省大量索引空间，也可能会使查询更快。
尽量的扩展索引，不要新建索引
比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。索引的列不要为 null
也能建立索引, 但是会造成不符合预期的行为。
6.2 索引失效的场景
联合索引非最左匹配
数据类型隐式转换
1
2
3phone varchar(20)
select phone where phone = '1000000' # 用到索引
select phone where phone = 1000000 # 用不到索引索引列参与计算 ， WHERE
age+10=30索引列使用了函数， from_unixtime(create_time) = ’2014-05-29’，应该写成create_time = unix_timestamp(’2014-05-29’)。
模糊查询 like 以%开头
查询结果集是原表中的大部分数据，mysql估计使用全表扫描要比使用索引快，则不使用索引。
or前后没有同时使用索引，虽然name字段上加了索引，但是age字段没有索引，使用or的时候会全表扫描。
7. 头脑风暴
- B+树走索引是从上往下，全表扫描是从左往右。
- InnoDB只能有一个聚集索引，索引和数据在一起。
- InnoDB其他的索引就做辅助索引，走索引后，找到的数据时在用聚集索引，再次回表查询。
- 建立索引：最左匹配，区分度高，不要为 null，扩展索引，数量控制。
- 查询索引：复合索引，不参与函数，不强转类型。
