一、为什么使用索引

索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本教科书的目录部分，通过目录找到对应文章的页码，便可以快速定位到需要的文章。
MySQL中也同理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要 全盘扫描。

如上图所示，数据库在没有索引的情况下，数据 分布在硬盘不同的位置上面，读取数据时，摆臂需要前后摆动查找数据，这样的操作非常耗时。
如果 数据顺序摆放，那么也需要从1到6按顺序读取，这样就相当于进行了6次IO操作，依旧非常耗时。 如果我们不借助仍和索引结构帮助我
们快速定位数据的话，我们查找Col2=89这条记录，就要逐行查找，去比较。从Col2=34开始，进行比较，发现不是，继续下一行。我们当前的表
不到10行数据，如果表很大，意味着要做很多次磁盘IO才能找到。

对字段Col2添加了索引，相当于在硬盘上为Col2维护了一个索引的数据结构，就是这个 搜索二叉树。每个节点存储的是 (k,v)结构，key是Col2，value是
该key所在行的文件指针（地址）。比如：该搜索二叉树的根节点就是：(34,0x07)。这时再去查找89这条记录就会先去查找二叉树。读34到内存,89>34；继续向右
读89到内存。89==89；找到数据返回。找到之后更具当前节点的value快速定位到要查找记录的地址。只查了两次

索引的目的就是 减少磁盘I/O次数，加快查询速率。

二、索引及其优缺点

MySQL官方对索引的定义为：索引（Index）是帮助MySQL搞笑获取数据的数据结构。

索引本质 : 索引是数据结构。你可以简单的理解为"排好序的快速查找数据结构"，满足特定的查找算法。这些数据结构以某种方式指向数据，
这样就可以在数据结构的基础上实现 高级查找算法。

索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同事，存储引擎可以定义每个表的 最大索引数
和 最大索引长度。索引存储引擎支持至少16个索引，索引长度至少为256字节。

2.1 优点

1. 降低数据库的IO成本
2. 通过创建唯一索引，可以保证数据库中每行 数据的唯一性
3. 在实现数据的参考完整性方面，可以 加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
4. 在使用分组和排序字句进行查询时，可以显著 减少查询中分组和排序的时间，降低CPU的消耗。

2.2 缺点

1. 创建索引和维护索引要 消耗时间,并且随着数据量的增加，所消耗的时间也会增加。
2. 索引需要占 磁盘空间，除了数据表占用数据空间外，每一个索引还要占用一定物理空间，存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
3. 索引虽然提高了查询速度，但会降低降低更新表的速度。当对表中的数据进行增加，删除和修改时，索引也需要维护，这样就降低了数据的维护速度。

三、InnoDB中索引的推演

3.1 索引之前的查找

select 字段名 from 表名 where 字段名 = xxx;

1. 在一个页中的查找
   • 已主键为搜索条件
     • 可以在页目录中使用 二分法快速定位对应的槽，然后便利该槽对应的分组中的记录即可快速找到。
   • 以其他列为搜索条件
     • 因为在数据页中并没有对主键列建立所谓的页目录，所以我们无法通过二分法快速定位响应的槽。这种情况只能从 最小记录开始 一次遍历
       单链表中的每条记录，然后对比每条记录是不是符合条件。
2. 在很多也中查找
   • 定位到记录所在的页
   • 从所在的页内查找记录
     在没有索引的情况下，无论是根据主键列或者其他列的值进行查找，由于我们无法快速定位到记录所在的页，所以只能 从第一个页沿着 双向链表 一直往下找，
     在每一个页中更具我们上面的查找方式去查找指定的记录。

3.2 设计索引

建一个表

create table index_demo(
    c1 INT,
    c2 INT,
    c3 char(1),
    primary key(c1)
) row_format = Compact;

这个新建的 index_demo表中有2个INT类型的列，1个Char(1)的列，而且我们规定了c1为主键,这个表使用Compact行格式来实际存储记录的。

• record_type: 记录头信息的一个属性，表示记录的类型，0 普通记录 1 目录项记录 2 最小记录 3 最大记录
• next_record: 记录头信息的一个属性，表示下一条地址相对本条记录的地址偏移量

把一些记录放到页里的示意图就是：

一个简单的索引设计方案

我们需要创建一个目录，目录需要完成下面这些事：

下一个数据页中用户记录的主键必须大于上一个页中用户记录的主键值。

那么这些记录已经按照主键值的大小串联成一个单项链表了。

假设一页只能存放三条记录，当我们再次插一条 c1=4 的记录又该如何呢。只能再添加一页

页10 和 页28 只是代号，这应该是内存地址，物理上是不连续的。

因为新插入的值可能是不连续的，所以我们需要将 28页的 4 和 10页的 5 交换位置。

这个过程表明了在页中的记录进行增删改查操作的过程中， 我们必须通过一些注入 记录移动的操作来始终保证这个状态一直成立
下一页的数据主键值必须大于上一页的数据主键值。这个过程我们称作 页分裂。

给所有的页建立一个目录项

由于数据页的 编号不可能是连续的，所以在向 index_demo表中插入许多条记录后，可能是这样的效果。

因为这些 16KB的页在物理存储上是 不连续 的，所以如果想从这么多页中更具主键值 快速定位某些记录所在的页，我们需要给他们做个 目录。

• 页的用户记录中嘴角的主键值，我们用 key 来表示
• 页号，我们用 page_no 表示
  所以我们的目录就这样
  

以 20 为例：

1. 更具二分法快速定位20在目录3中(12<20<209)所以对应的应该是页9
2. 再更具 二分法对页中的数据进行查找

至此，正对数据页做的简易目录就搞定了。这个目录有一个别名，称为 索引

InnoDB中的索引方案

第一次迭代

第二次迭代

第三次迭代

B+Tree

这个数据结构就叫做 B+Tree

无论是存放 用户记录 的数据页，还是存放 目录项记录 的数据页，我们都把它放到B+树这个数据结构中了，所以我们也称这些数据页为 节点。
从图中可以看出，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也称为 叶子结点，其余用来存放 目录项的节点被称为 非叶子节点
或者 内节点 ，其中B+树最上边的那个节点也称为 根节点。

一个 B+树可以被分为好几层，规定最下边那层，也就是存放记录的那层为 0层，之后依次往上加。
叶子结点，其余用来存放 目录项的节点被称为 非叶子节点或者内节点，其中B+树最上边的那个节点也称为根节点`。

一个 B+树可以被分为好几层，规定最下边那层，也就是存放记录的那层为 0层，之后依次往上加。
正常B+树不会超过4层