一、基础
1.1 索引
MySQL官方文档对索引的定义：
Indexes are used to find rows with specific column values quickly.
在数据之外，数据库系统维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
1.2 查找算法和数据结构
二分查找：O（logN）
二叉查找树、平衡二叉树
二、B树、B+树
（平衡）二叉树有一个缺陷，树的高度会随着数据量的增加而增高，由于数据存储在磁盘，从而导致IO开销很大。
2.1 b-tree
B树是由二叉树和索引顺序访问方法演化而来的一种数据结构。它是一种自平衡的树数据结构，维护排序的数据，并允许在对数时间内进行搜索、顺序访问、插入和删除操作。
相对于二叉树，b树的每个节点可以用的子节点的数目更多，这就意味着，在相同的数据量下，树的高度显著降低，查找更快，从而减少了磁盘的io。
2.2 b+tree
现实使用中，基本是使用的b+树，b+树是B树的变种，它是一种专门为磁盘或其他读取设备设计的一种平衡查找树。不同于b树，b+树的非叶子节点只存储索引，不存储数据，所有数据都按照顺序存储在同一层的叶子节点。
2.3 带有顺序访问指针的b+tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
特性：
- 1.单一节点存储更多的元素，使得查询的IO次数更少；
- 2.所有查询都要查找到叶子节点，查询性能稳定；
- 3.所有叶子节点形成有序链表，便于范围查询。
三、MySQL B+树索引
MySQL数据库InnoDB存储引擎的数据表，有两种索引：聚集索引(cluster index)和辅助索引(secondary index)。每个表可以有多个辅助索引，但是有且只有一个聚集索引，一般说来，聚集索引和主键是同义词：
- 如果表定义了主键，那么InnoDB会使用主键作为聚集索引
- 如果表没有定义主键，那么InnoDB会使用第一个唯一索引作为主键，这个唯一索引里的所有列必须都不能为null
- 如果以上两点都不满足，InnoDB会在一个包含行号（row id）的合成列上建立一个名为GEN_CLUST_INDEX 的聚集索引
3.1 聚集索引
InnoDB存储引擎表是索引组织表，按照主键顺序存放表中的数据。聚集索引按照表的主键顺序组织一个B+树，同时在叶子节点中存放完整的行数据，所以将聚集索引叶子节点称为数据页，非叶子节点称为索引页。索引组织表的这一特性决定了，数据页也是聚集索引的一部分。并且所有的数据页都通过链表来链接。
叶子索引指向的是数据页，进行查找时，会将对应行所在的数据页加载到内存中，在对相应的行进行二分查找，由于这一操作是在内存中进行，所以速度很快。
3.2 辅助索引
同聚集索引一样，辅助索引的底层实现也是b+树，不同的是，辅助索引的叶子节点存放的是辅助索引的索引列和主键。因此通过辅助索引进行查找分两步，首先查到辅助索引对应的主键，然后再去聚集索引中获取主键对应的数据。
3.3 B+树索引分裂
如果数据的插入顺序是随机的，比如聚合索引是UUID的情况，那么取页的中间记录作为分裂点；如果数据的插入是有顺序的，那么分裂点定在中间就不是很合理。假设一个页的记录如下
p1 : 1 2 3 4 5 6 7 8 9
现要插入数字10，如果选择中间的记录作为插入点，那么当前页会分裂成下面两列：
p1 : 1 2 3 4
p2 : 5 6 7 8 9 10
由于插入是按顺序的，p1这个页里面不会有记录插入，从而导致了空间的浪费，并且p2很快又会迎来一次分裂，导致页分裂过于频繁。
InnoDB存储引擎会根据插入是否有序，来决定分裂点，当插入有序时，会根据插入的方向决定在尾端进行页分裂。
四、分区相关
MySQL支持的分区是局部索引分区，即一个分区中及存放了索引又存放了数据。全局分区是指，分区中只存放数据，而所有数据的索引放在一个对象中。
如果对表进行了分区，那么所有的唯一索引都要带上分区使用的所有列。
五、使用索引分区的一些意见
- 使用自增的主键（页分裂和热点数据）
http://seanlook.com/2017/02/16/mysql-autoincrement/
https://www.cnblogs.com/JiangLe/p/6362770.html - 索引不宜太多
- 联合索引的使用：最左前缀原则
ICP http://blog.codinglabs.org/articles/index-condition-pushdown.html
im多个键值的B+树 - 分区表在查找时必须带上分区字段
- 慢sql日志 和 explain命令（执行计划）
