首先需要强调，索引是基于具体的存储引擎实现的，我们谈索引必然绕不开基于哪个存储引擎。
一、索引推演
先来看个最简单的查找语句 SELECT [列名列表] FROM 表名 WHERE 列名 = xxx; 展示出的所有数据在底层的存储单位为数据页。一个数据页中默认的存储大小是16KB，也就是只能存储部分数据，因此涉及多个数据页的使用。
假设目前表中的记录比较少，所有的记录都可以被存放在一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：
以主键为搜索条件
可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件
因为在数据页中并没有对非主键建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
强调一下，表中数据在磁盘中的存储形式并非与我们在表中存储的实际顺序完全一致（即无顺序）。磁盘顺序的保证效率是很低下的，我们只需要保证逻辑顺序一致即可，单链表进行连接。
在很多页中查找情况：
大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
定位到记录所在的页。
从所在的页内查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。并且每一页上的数据又并非顺序排列的，因为要遍历所有的数据页，加上每页的数据没有顺序排列，所以这种方式显然是超级耗时的。
此时，索引应运而生。
二、设计索引
先建一个表
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表示普通记录、1表示目录项记录、2表示最小记录、3表示最大记录。
next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。
各个列的值：这里只记录在index_demo表中的三个列，分别是c1、c2和c3。
其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我想快速的定位到需要查找的记录在哪些数据页中该咋办？我们可以为快速定位记录所在的数据页建立一个目录，建这个目录必须完成下边这些事：
- 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
- 给所有的页建立一个目录项。
从以上教材图片可以看到，数据页和数据页是通过双向链表逻辑排序的。
注意，新分配的 数据页编号 可能并不是连续的。它们只是通过维护着上一个页和下一个页的编号而建立了 链表 关系。另外，页10 中用户记录最大的主键值是5，而页28 中有一条记录的主键值是4，因为5>4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次 记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中。
随着数据越来越多，数据页也会越来越多，但是无论怎么增加数据页，每个数据页中的主键都会通过双向链表保证有序，注意，数据页不需要有序。
如果我需要查找一个主键id为20的行数据，那么也是需要从头到尾进行数据页的遍历。因为底层并不知道你的数据会放在第几页，因此，给数据页对应一个目录项是非常有必要的。
以页28 为例，它对应目录项2，这个目录项中包含着该页的页号28 以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储(比如:数组)，就可以实现根据主键值快速查找某条记录的功能了。比如:查找主键值为20的记录，具体查找过程分两步:
1.先从目录项中根据 二分法 快速确定出主键值为 28的记录在目录项3中(因为12<28 <289)，它对应的页是 页9 。
再根据前边说的在页中查找记录的方式去 页9中定位具体的记录,至此，针对数据页做的简易目录就搞定了。
这个目录有一个别名，称为 索引。