1. 为什么使用索引
假如给数据使用 二叉树 这样的数据结构进行存储，如下图所示
2、索引及其优缺点
2.1 索引概述
2.2 优点
类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的 IO 成本 这也是创建索引的主要的原因。
通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 (唯一约束)
在实现数据的参考完整性方面，可以 加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低了 CPU 的消耗。
2.3 缺点
增加索引也有许多不利的方面，主要表现在如下几个方面:
创建索引和维护索引要 耗费时间 （因为索引是排好序的），并且随着数据量的增加，所耗费的时间也会增加。
索引需要占 磁盘空间，除了数据表占数据空间之 外，每一个索引还要占一定的物理空间，存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
因此，选择使用索引时，需要综合考虑索引的优点和缺点。
3. InnoDB 中索引的推演
3.1 索引之前的查找
先来看一个精确匹配的例子：
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
3.1.1 在一个页中的查找
注意：
数据表中记录之间物理上是不连续的，但是逻辑上是连续的，之间通过单链表进行连接；数据页之间通过双向链表进行连接
以主键为搜索条件：O ( l o g 2 n ) ，以其他列为搜索条件：O ( n )
3.1.2 在很多页中查找
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能 从第一个页 沿着 双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是 超级耗时 的。此时 索引 应运而生。
我们可以联想下学校的图书馆：所有书架上有着对应的编号，每个书架中有着分区从A-Z。借书时，先根据书的类型找到对应的书架，再从书架中对应的分区找到目标书籍。
3.2 设计索引
建一个表：
mysql> 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 行格式来实际存储记录的。这里我们简化了 index_demo 表的行格式示意图：
我们只在示意图里展示记录的这几个部分：
record_type：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记 录、 3 表示最大记录、 1 表示目录项的记录，暂时还没用过，下面讲。
next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用
箭头来表明下一条记录是谁。（用来保证数据逻辑上的连续）
各个列的值：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3。
其他信息：除了上述 3 种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：
把一些记录放到页里的示意图就是：
3.2.1一个简单的索引设计方案
我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们 想快速的定位到需要查找的记录在哪些数据页 中该咋办？我们可以为快速定位记录所在的数据页而 建立一个目录 。 建这个目录必须完成下边这些事：
下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
给所有的页建立一个目录项。
**注意：**不建立目录项前，每次进行查询（插入）数据时，都要从前往后一个个数据页、一条条记录查找。需要先加载数据页，再二分查找对应的数据。甚至有时候，加载数据页的速度比查找速度还耗时，这样就非常得不偿失了。才有了 为所有的页建立目录项的操作。
所以我们为上边几个页做好的目录就像这样子：
以 页 28 为例，它对应 目录项 2 ，这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为 20 的记录，具体查找过程分两步：
先从目录项中根据 二分法 快速确定出主键值为 20 的记录在 目录项 3 中（因为 12 < 20 < 209 ），它对应的页是 页 9。
再根据前边说的在页中查找记录的方式（二分法）去 页 9 中定位具体的记录。
至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引 。
3.2.2 InnoDB 中的索引方案
思考一下，我们之前的设计方案有什么问题？
如下图：比如我们要插入三条数据且恰好在页28和页29之间的，那么需要重新创建个数据页，同时创建对应的目录项，但是目录项是保存在数组中的。目录项3、4都需要向后移动，然后才能插入新的目录项。这样的话效率是非常低的。
解决办法：为多个目录项建立目录页，目录项之间通过指针方式进行连接（链表），目录页上建立当前页的目录信息，便于后续的二分查找。同时目录项之间指针连接也方便进行插入和删除操作。
具体细节看下面的第一次迭代！
① 迭代 1 次：目录项纪录的页
我们把前边使用到的目录项放到数据页中的样子就是这样：
从图中可以看出来，我们新分配了一个编号为 30 的页来专门存储目录项记录。这里再次强调 目录项记录 和普通的 用户记录 的不同点：
目录项记录 的 record_type 值是 1，而 普通用户记录 的 record_type 值是 0。
目录项记录只有 主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列 ，另外还有 InnoDB 自己添加的隐藏列。
了解：记录头信息里还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的页中的主键值最小的目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0 。
**相同点：**两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度 (如果没有页目录，链表是无法进行 二分查找)
现在以查找主键为 20 的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：
先到存储 目录项记录的页，也就是页 30 中通过 二分法 快速定位到对应目录项，因为 12 < 20 < 209，所以定位到对应的记录所在的页就是页 9。
再到存储用户记录的页9中根据 二分法 快速定位到主键值为 20 的用户记录。
**注意：**建立目录页后，IO次数也会降低。比如上面的查找只有两次IO
② 迭代 2 次：多个目录项纪录的页
从图中可以看出，我们插入了一条主键值为 320 的用户记录之后需要两个新的数据页：
为存储该用户记录而新生成了 页 31 。
因为原先存储目录项记录的 页 30 的容量已满（我们前边假设只能存储 4 条目录项记录），所以不得不需要一个新的 页 32 来存放 页 31 对应的目录项。(目录页之间用双向链表连接)
现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要 3 个步骤，以查找主键值为 20 的记录为例：
确定 目录项记录页
我们现在的存储目录项记录的页有两个，即 页 30 和 页 32 ，又因为页 30 表示的目录项的主键值的范围是 [1, 320)，页 32 表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在 页 30 中。
通过目录项记录页 确定用户记录真实所在的页 。在一个存储 目录项记录 的页中通过主键值定位一条目录项记录的方式说过了。
在真实存储用户记录的页中定位到具体的记录。
**存在的问题：**查找数据第一步，判断数据是在哪个目录项记录页中时，由于目录项记录页之间是双链表连接的，所以只能从前往后进行遍历查找（过程中IO次数较多），之后找到了再二分查找到对应的数据页…
改进办法：为数据项记录页 建立目录页
③ 迭代 3 次：目录项记录页的目录页
如图，我们生成了一个存储更高级目录项的 页 33 ，这个页中的两条记录分别代表页 30 和页 32，如果用户记录的主键值在 [1, 320) 之间，则到页 30 中查找更详细的目录项记录，如果主键值 不小于 320 的话，就到页 32 中查找更详细的目录项记录。
我们可以用下边这个图来描述它：
这个数据结构，它的名称是 B+ 树 。
④ B+Tree
一个 B+ 树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层， 之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页 最多存放 3 条记录 ，存放目录项 记录的页 最多存放 4 条记录 。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录 的叶子节点代表的数据页可以存放 100 条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存 放 1000 条目录项记录 ，那么：
如果 B+ 树只有 1 层，也就是只有 1 个用于存放用户记录的节点，最多能存放 100 条记录。
如果 B+ 树有 2 层，最多能存放 1000×100=10,0000条记录。
如果 B+ 树有 3 层，最多能存放 1000×1000×100=1,0000,0000条记录。 1亿
如果 B+ 树有 4 层，最多能存放 1000×1000×1000×100=1000,0000,0000条记录。相当多的记录！！！ 1000亿
你的表里能存放 100000000000 条记录吗？所以一般情况下，我们 用到的 B+ 树都不会超过 4 层 ，那我们通过主键值去查找某条记录最多只需要做 4 个页面内的查找（查找 3 个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过二分法实现快速定位记录。
为啥B+ 树都不会超过 4 层呢？
树的层次达到4的时候，可以存储的数据量足够多了（1000亿）。树的层次越低，IO次数就越少，从而效率越高
