1. 最简单的索引

假设查询id=4这条数据，在没有索引的前提下，只能全表扫描。

现在就需要针对主键设计一个索引，这个索引实际上就是主键目录。

主键目录就是把数据页的页号，还有数据页里面最小的主键值放在一起，组成一个索引的目录。

图 1-1

有了主键目录，再通过主键去查询数据不就方便了。假设现在需要查询id=3的数据，首先会跟主键目录里面的最小主键对比，也即是跟每个数据页的最小主键对比，发现id=3大于数据页2的最小主键值1，小于数据页8的最大主键值4。

说明id=3的数据一定是在数据页2里面。

这就是最简单最基础的索引概念。

2. 基于B+树实现的索引页的物理存储结构

我们已经知道了主键目录实现的索引，现在有一个问题，如果单表的数据过于庞大，达到几百万几千万甚至上亿。这时候再在主键目录存放大量的数据页和最小主键值怎么行呢？

这个时候，就是采取把索引数据存储在数据页里的方式来解决。

即是说，表里的实际数据是存放在数据页里，索引的数据也存储在页里。

图 2-1

此时的索引页存储的是最小主键和数据页号。

当数据页越来越多，索引页也会越来越多，想再通过索引页去查询对应数据页效率就变得非常低下。

此时在索引页多加一个层级，在更高级的层级里，保存了每个索引页的页号和页里的最小主键值。

图 2-2

假设现在要找id=46的数据，首先到索引页35里找，通过二分法快速定位到应该到索引页20里去找。再从索引页20里面通过二分法查找定位，就会发现id=46的数据是在数据页8里面，通过目录页二分查找，查询到id=46这行数据。

如果最顶层的索引页里面存放的下层索引页过多，则需要再次分层

图 2-3

这时候的索引页结构就是一种树结构。非叶节点的索引页存放的是索引页的页号和最小主键值，叶节点的索引页存放的是数据页和最小主键值。

3. 聚簇索引

通过索引页的物理存储结构我们知道了是如何通过主键索引查询数据。

也就是说，通过主键的二分查找，找到对应的叶节点的索引页，然后二分查找对应的数据页，通过页目录，二分查找对应的槽位，然后遍历槽位中的数据得到相应的数据行。

也可以说 叶节点的索引页就是数据页自己本身。

这也是索引页+数据页组成的B+树的聚簇索引。

所以，在innodb引擎里面，对数据的增删改时，就是直接把数据页放到聚簇索引里，数据就在聚簇索引里，聚簇索引就包含了数据。

发生页分裂时，各个数据页内部就会调整数据行，保证数据页内的主键值都是有顺序的，下一个数据页的所有主键值都大于上一个数据页的所有主键值。

在页分裂的同时也会维护上层的索引数据结构。在上层的索引页里维护你的索引条目。如果数据页越来越多，对应的索引页放不下了，此时就会出现新的索引页同时再搞一个上层的索引页。

4. 二级索引

假设要针对其他字段建立索引，例如name、age之类的字段，都是类似的。

现在要对name字段建立一个索引，那么此时插入是数据的时候，一方面会把完整的数据插入到聚簇索引的叶节点的数据页里去，另一方面会为name字段重新生成一棵B+树，这棵B+树的叶节点也是数据页，但是这个数据页里面仅仅存放主键字段和name字段

图 4-1

这是一棵独立于聚簇索引的B+树，是根据name字段构建的索引B+树。至于叶节点的数据页的排序规则，和之前的一样，根据name值的大小排序。同时下一个数据页里的name字段值都大于上一个数据页里的name字段值。

这棵B+树中，非叶节点存储的是索引页号和最小name字段值；叶节点存储的是主键字段和name字段值

图 4-2

这是基于name字段值来搜索数据时，搜索过程是一致的，从根节点层层往下找，通过二分查找快速定位所在数据页。

假设是“select * from user where name = 'zangsan'”这样一条查询，首先会根据name字段值在name字段的索引b+树里面找，找到叶节点也仅仅找到对应的主键值，但并没有找到该行数据。

接下来还需要进行回表。还需要根据主键值，再到聚簇索引里从根节点开始，一路找到叶节点的数据页，定位到主键对应的完整数据行。此时才能将 select * 要的全部字段返回。

所以，这种根据普通字段建立的索引称为二级索引。

注明：

学习笔记总结于公棕号：儒猿技术窝。感兴趣的同学可以前往关注。