本质
索引是排好序的数据结构，可以帮助MySQL高效获取数据。
索引的作用
考虑一张表设计和数据如上图，第一列是指数据行在磁盘的存放地址，
查询sql语句为
select *from t where t.Col2 = 89;
不用索引，需要从第一行开始遍历，查询每一行的Col2值是否等于89，需要查找6次。 而MySQL的数据是存放在磁盘的，每一行的查找相当于做了一次磁盘IO操作，磁盘的寻道时间大约为10ms，假如查找100次，就需要1s，效率非常低，更不用说成千上百万行记录的表。
给Col2加上索引，例如用上图的二叉树，树的节点是key，即Col2的值，value是索引所在行的磁盘文件地址(数据行在磁盘中存放不是连续的)，那么从根节点查找Col2 = 89的值，只需要两次IO操作即可，比全表扫描快很多。
索引的优势
- 提高数据检索的效率，降低数据库的IO成本，类似于书的目录(每次翻页就是IO操作)。
- 通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗。
- 被索引的列会自动进行排序，包括【单列索引】和【组合索引】，只是组合索引的排序要复杂一些。
- 如果按照索引列的顺序进行排序，对应order by语句来说，效率就会提高很多。
索引的劣势：
- 索引会占据磁盘空间
- 索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。
索引数据结构
- 二叉树
- 红黑树(平衡二叉树)
- 有序数组
- hash表
- B树
- B+树
为什么不用二叉树
考虑上图，对Col1进行索引，二叉树是长这样子
退化成了线性结构的链表，查询效率和全表扫描一样，复杂度是O(n)。
所以二叉树对于线性增长的字段是不适合做索引存储的。
为什么不用红黑树
对Col1进行索引，红黑树是长这样子
红黑树是采用二分法思维，除了具备二叉树的特点，最主要的特征是树的左右两个子树会自动平衡，在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。
使用红黑树查找树查询的性能接近于二分查找法，查找时间复杂度是 O(log2n)，是高效的数据结构。
存在问题：一张表动辄上千万的记录，即使红黑树具有自平衡功能，树也会很高，树高 = log2(记录数)，
至少是20，假如元素落在叶子节点，就需要经历20次IO操作，还是有效率问题。
有序数组
对Col1进行索引，有序数组是长这样子
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 | 6 |
有序数组在等值查询和范围查询场景中的性能都非常优秀。
如果你要查 Col = 4，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。
同时很显然，这个索引结构支持范围查询。
如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。
hash表
考虑对表的名字列用hash做索引，如下图
Hash表，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。每次插入数据，都对key用hash算法得出散列值，放入数组中。
当发生hash冲突时，采用开链表法解决，当链表太长会rehash，或者改用红黑树存储数据。
优点：
- 在等值查询时效率很高，时间复杂度为O(1)，比B+树索引高效；
缺点：
- 仅满足等值查询，例如 "= ", "IN"，不支持范围快速查找，范围查找时还是只能通过扫描全表方式；
- hash冲突问题。
所以，哈希表这种结构适用于只有等值查询的场景，比如 Redis，Memcache 及其他一些 NoSQL 引擎。
显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。
B树
红黑树的缺点是大数据下树会变得很高，解决思路是横向扩展每层节点个数，每层存储更多的节点，就可以降低树的高度。 每个节点对应一块磁盘空间，分配更大的磁盘空间，以容纳更多的节点。
改造后的数据结构就是B树，每个大节点下可以存放多个数据。
B树特点：
- 叶节点具有相同的深度，叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。
B树缺点：
B树不支持范围查询的快速查找，想要查找15和49之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
节点存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。
B+树(多路平衡树)
MySQL实际上对B树再进行改造，得到B+树
B+树特点：
- 非叶子节点不存储数据，只存储索引(冗余)，可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高区间访问性能。
假如要查找值为30的行，数据查找过程如下：
- 先把根节点的索引全部load进内存，因为数据是已经有序的，可以使用二分查找，定位下一级索引位置。
- 定位到第二级索引后，也是load进内存，定位第三级索引。
- 定位到第三级索引，继续二分查找，找到索引位置，并取出索引对应的行数据。
过程只需要三次IO操作，约等于30ms。
假如要查找18 ~ 50的行，数据查找过程如下：
- 定位到value为18的索引，需要三次IO操作；
- 从18的索引开始，依次读取索引下一个索引，直到>50为止，再需要两次IO操作。
B树与B+树两个区别：
- B树：非叶子节点和叶子节点都会存储数据。
- B+树：只有叶子节点才会存储数据，非叶子节点只存储键值，所以B+树一个页能放入更多的索引，同样的数据量，树高更低。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表，方便进行范围搜索。
MySql默认一个页的长度为16KB，即分配给B+树每个节点大小。
mysql> show global status like 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)
假如索引字段是BigInt，占8B，索引存储的值即磁盘地址长度占6B，加起来就是14B，页大小为16KB情况下，每页可以放 16KB / 14B = 1170个索引，假如叶节点，即存放数据的节点，每行数据大小为1KB，即每页可以放16个数据行，那么树高为3的B+树，可以放满 1170 * 1170 * 16 = 2000w个索引和数据，千万级别的数据依然很高。
而且MySQL底层，实际上会把所有非叶子结点放到内存中，因为非叶子节点内存占用少，例如树高为3的B+树，放满索引后，索引大小为 1170 * 1170 * 14B = 18.2MB，所以查找数据只需要1次IO操作，效率高。
