4 - 索引（上）- 常见索引模型以及 InnoDB 的索引
关键字
索引，查询效率，B+树
0.什么是索引
索引就像是一本书的目录，可以提高数据的查询效率，如果没有索引，你很可能只能使用遍历的方式查询数据。
1.索引的常见模型
在《数据结构与算法之美》的专栏中，介绍了很多可以用于搜索的数据结构，包括：哈希表、有序数组、搜索树、跳表等。关于索引，我也写了一篇总结：具体算法8 - 索引的方方面面。
在这里，我们简要的提一下哈希表、有序数组、搜索树这三种数据结构，具体如果有疑问，可以访问隔壁的《数据结构与算法之美》。
1.1散列表
散列表的底层是一个数组，它通过哈希函数计算数据所在的数组下标。散列表的查询速度很快，但是会面临哈希冲突的问题。下面给出一个例子，记录了四个人的身份证信息和姓名，并使用拉链法处理冲突：
4-哈希冲突.png
散列表的特点：
- 使用散列表做等值查询非常快。
- 使用哈希表所区间查询的速度很慢。（我们可以使用 散列表 + 有序链表 的方式解决）
1.2有序数组
我们可以使用二分查找在有序数组中快速找到一个数据，同时它的范围查询性能也很优秀。依然是身份证查名字的例子：
4-有序数组.png
特点：
- 查找很快，支持快速的范围查找。
- 插入和删除成本很高，所以它只适用于静态存储。
1.3搜索树
首先看一下二叉搜索树：
4-二叉搜索树.png
特点：
- 这里，非叶子节点为索引，叶子节点才存储数据。
- 查找也很快速。
由于数据库的数据量很大，所以我们会将数据和索引都存到硬盘中。如果使用二叉搜索树，会多次访问磁盘，这会显著降低查找性能。
所以，为了加快查找，我们将二叉树扩展为 N 叉树，以加快查找。这也是 B+树 作为数据库索引的主要原因。具体可以看这里。
2.InnoDB 的索引模型
在 InnoDB 中，所有索引都是使用 B+ 索引模型。
假设我们有如下的数据表：
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
4-InnoDB索引结构.png
注意：
- 索引类型分为 主键索引 和 非主键索引。
- 主键索引：叶子节点为数据，指向磁盘文件，一般来说是一个文件页（page）。
- 非主键索引：又称二级索引，叶子节点为主键的值。
两种索引的区别：
- 使用主键查询，只需要搜索 ID 这一棵 B+树。
- 使用二级索引，需要先搜索 k 索引树，获得相应的 ID 后，再到 ID 索引树中搜索。也就是说，使用二级索引会索引两棵索引树，这个过程称为回表。
- 因此，建议尽量多使用主键索引。
3.索引维护
随着数据的增加和删除，一个数据页内的索引可能过多（或过少），这时就需要进行索引的维护（具体过程依然建议看我之前的笔记）：
- 数据页满，插入数据，需要进行页分裂。
- 数据页过小，仍然删除数据，可以进行页合并。
有了上面的说明，我们看一个说法：
一些数据库建表规范有这样的描述：建表语句中一定要有自增主键
我们来分析这句话：
- 自增主键定义：NOT NULL PRIMARY KEY AUTO_INCREMENT .
- 自增主键在插入数据时都是追加操作，不会触发叶子节点的分裂。
- 如果使用业务逻辑字段做主键，如果不能保证有序插入，写数据的成本会变高。
- 自增主键一般是字节类型，使用它作为二级索引的叶子节点值，可以节省空间。
可以考虑使用业务字段直接做主键的情况：
- 只有一个索引
- 该索引是唯一索引
- 也就是典型的 KV 场景
小结
- 几种常见的索引模型。
- InnoDB 使用 B+树 作为索引的原因。
- 通常我们建议使用一个自增主键作为索引。
专栏作者的思考题：
最后，我给你留下一个问题吧。对于上面例子中的 InnoDB 表 T，如果你要重建索引 k，你的两个 SQL 语句可以这么写：
alter table T drop index k;
alter table T add index(k);
如果你要重建主键索引，也可以这么写：
alter table T drop primary key;
alter table T add primary key(id);
我的问题是，对于上面这两个重建索引的作法，说出你的理解。如果有不合适的，为什么，更好的方法是什么？
解答：
通过两个 alter 语句重建索引 k，以及通过两个 alter 语句重建主键索引是否合理。
在评论区，有同学问到为什么要重建索引。我们文章里面有提到，索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
这道题目，我给你的“参考答案”是：重建索引 k 的做法是合理的，可以达到省空间的目的。但是，重建主键的过程不合理。不论是删除主键还是创建主键，都会将整个表重建。所以连着执行这两个语句的话，第一个语句就白做了。这两个语句，你可以用这个语句代替 ： alter table T engine=InnoDB。在专栏的第 12 篇文章《为什么表数据删掉一半，表文件大小不变？》中，我会和你分析这条语句的执行流程。
以上就是本节的全部内容
注：本文章的主要内容来自我对极客时间app的《MySQL实战45讲》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
