索引是提高关系型数据库查询性能的利器，但其并非银弹，必须精通其原理，才能发挥奇效。
InnoDB底层是如何存储数据的？
MySQL把数据存储和查询操作抽象成了存储引擎。MySQL支持多种存储引擎，并且可以以表为粒度设置存储引擎。因为需要事务，所以InnoDB最常用。
为减少磁盘随机读取次数，InnoDB采用页而非行的粒度保存数据，即数据被分成若干页，以页为单位保存在磁盘。InnoDB的页大小默认16K。
- 各数据页形成双向链表
- 每个数据页中的记录按主键顺序形成单链表
- 每一个数据页中有一个页目录，方便按主键查询记录
- 数据页结构
页目录通过一个个槽把记录分成不同组。记录中最前面的小矩形数字，代表当前组的记录条数。
最小和最大的槽指向2个特殊的伪记录。
0 =》 最小记录 1 =》 4 2 =》 8 3 =》 12 4 =》 16 5 =》 20 6 =》 最大记录
有了槽，按主键搜索页内记录时，就能用二分查找，而无需从最小记录遍历整个页的记录链表。
比如要搜索主键（PK）=15的记录：
先二分计算得槽中间位(0+6)/2=3，指向记录12＜15，所以从槽3后继续搜索
再二分：(3+6)/2=4.5取整4，槽4对应记录16＞15，所以记录在槽3
再从槽3指向的12号记录开始向下搜索3次，定位到15号记录
聚簇索引和二级索引
页目录就是最简单的索引，通过对记录进行一级分组来降低搜索的时间复杂度。
这样能够降低的时间复杂度数量级有限。当有无数个数据页来存储表数据时，我们就需要考虑如何建立合适索引，才能方便定位记录所在的页。
为了解决这个问题，InnoDB引入B+树
- 最低层的叶子节点，存放数据
- 其他上层节点-非叶子节点，存放目录项，作为索引
- 非叶子节点分为不同层次，通过分层降低每层的搜索量
- 每层节点按索引键大小排序，构成双向链表，加速范围查找
因此，InnoDB使用B+树，既可以保存实际数据，也可加速数据搜索，这就是聚簇索引。
如果把上图叶子节点下面方块中的省略号看作实际数据，那么它就是聚簇索引的示意图。由于数据在物理上只会保存一份，所以包含实际数据的聚簇索引只能有一个。
InnoDB会自动使用主键（唯一定义一条记录的单或多个字段）作为聚簇索引的索引键（若无主键，则选择第一个不包含NULL值的唯一列）。方框数字代表索引键的值，对聚簇索引，一般就是主键。
B+树如何快速查找主键
比如搜索PK=4数据，通过根节点中的索引可知数据在第一个记录指向的2号页，通过2号页的索引又可知道数据在5号页，5号页就是实际数据页，再通过二分查找页目录马上可以找到记录的指针。
为了实现非主键字段的快速搜索，就引出了二级索引，也叫作非聚簇索引、辅助索引。非聚簇索引也是B+树，如下：
非聚簇索引的叶子节点保存的不是实际数据，而是主键。
获得主键值后去聚簇索引获得数据行，就是回表。
假设该索引是针对用户名字段创建的，索引记录上面方块中的字母是用户名，按顺序形成链表。若要搜索用户名为b的数据，经过两次定位可以得出在数据页5中，查出所有主键为7和6，再拿这俩主键继续使用聚簇索引进行两次回表得到完整数据。
额外创建二级索引的代价
维护代价
创建N个二级索引，就需要再创建N棵B+树，新增数据时不仅要修改聚簇索引，还需要修改这N个二级索引。
假设有如下表：
通过如下存储过程创建10万条测试数据，约140s。
再创建两个索引：
则创建10万条记录的耗时提高到154s。
页中的记录都是按照索引值从小到大的顺序存放的：
- 新增记录就需要往页中插入数据，现有的页满了就需要新创建一个页，把现有页的部分数据移过去，这就是页分裂
- 若删除了许多数据使得页很空闲，就需要页合并
页分裂和合并，都会有I/O代价，且过程中可能产生死锁。
空间代价
虽然二级索引不保存原始数据，但要保存索引列的数据，所以会占用更多的空间。
比如，person表创建了两个索引后，使用下面的SQL查看数据和索引占用的磁盘：
SELECT DATA_LENGTH, INDEX_LENGTH FROM information_schema.TABLES WHERE TABLE_NAME='person'
结果显示，数据本身只占用了4.7M，而索引占用了8.4M。
