【SQL】浅谈关系型数据库的索引原理

来源：https://zhuanlan.zhihu.com/p/23624390
作者：陈大侠

本文将解决四个问题：
为什么要给表加上主键？
为什么加索引之后会使查询变快？
为什么加索引后会使写入、修改、删除变慢？
什么情况下要同时在两个字段上建索引？

一、为什么要给表加上主键？

形象地说，如果我们建一个不加主键的表，那么它的记录是一行一行排列整齐地放置在磁盘存储器上的。它是真正的“表”结构。
另一方面，如果我们建一个加主键的表，那么表在磁盘上的存储结构就不是整齐排列的了，而是变成了树状结构，即“平衡树”结构。

换句话说，就是整个表变成了一个索引，即所谓的聚集索引。

1.平衡树
平衡树是指子树的高度差不超过1。
通俗地讲，就是每个叶子节点都均匀一些，不要太凸出。

2.聚集索引

聚集索引依据键值的逻辑顺序来决定表中数据相应的物理顺序。

为什么一个表只能有一个聚集索引？

因为一个表的物理顺序只有一种情况，因此一个表只能有一个聚集索引。

为什么一个表只能有一个主键？

因为主键的作用就是把表的数据存储方式转化成聚集索引（平衡树）的存储方式，而聚集索引只有一种，因此一个表只能有一个主键。

3.一个例子

上图就是一个带主键的表（聚集索引）的结构图。
其中树的所有节点（底部除外）的数据都是由主键字段中的数据构成。
假如我们执行一个SQL语句：
SELECT * FROM table WHERE id =1256;
如上图，首先根据索引定位到1256这个值所在的叶节点，然后再通过叶节点渠道id等于1256的数据行。

二、为什么加索引之后会使查询变快？

表的存储格式变成树状结构之后，我们查询的次数就不再是记录的个数，而是平衡树的高度；平衡树的高度和记录的个数的关系是：
图片说明
这样，利用索引就会使数据库查询有惊人的性能提升。

证明：n个节点的二叉平衡树的高度是O(log2 n)。

三、为什么加索引后会使写入、修改、删除变慢？

主要是为了维护平衡树这个结构。
增删改数据都会改变平衡树各节点中的索引数据内容，从而破坏树结构，因此，在每次数据改变时，DBMS必须去重新梳理树（索引）的结构以确保它的正确，这会带来不小的性能开销。

四、什么情况下要同时在两个字段上建索引？

让我们先看看非聚集索引，也就是我们平时经常使用的常规索引。

1.非聚集索引
非聚集索引同样采用平衡树作为索引的数据结构。索引树结构中各节点的值来自于表中的索引字段。

例如，假如给user表的name字段加上索引，那么索引就是由name字段中的值构成。在数据改变时，DBMS需要一直维护索引结构的正确性。

如果给表中多个字段加上索引，那么就会出现多个独立的索引结构，每个索引（非聚集索引）相互之间不存在关联。
图片说明

每次给字段建一个新索引，字段中的数据就会被复制一份出来，用于生成索引。因此，给表添加索引，会增加表的体积，占用磁盘存储空间。

非聚集索引和聚集索引的区别在于，通过聚集索引可以查到需要查找的数据，二通过非聚集索引可以查到记录对应的主键值，再使用主键的值通过聚集索引查找到需要的数据。
图片说明
不管以任何方式查询表，最终都会利用主键通过聚集索引来定位到数据，聚集索引（主键）是通往真实数据所在的唯一路径。

2.覆盖索引（复合索引、多字段索引）
这种非主流的索引方式，可以不使用聚集索引来查询数据。
上文指出，当字段建立索引以后，字段中的内容会被同步到索引之中；如果为一个索引指定两个字段，那么这两个字段的内容都会被同步到索引之中。

例，执行下面的SQL语句
CREATE INDEX index_birthday ON user_info(birthday); // 建立索引

SELECT user_name 
FROM user_info
WHERE birthday = '1991-11-1'; // 查询生日再1991年11月1日出生用户的用户名
这句查询SQL语句的执行过程如下：

首先，通过非聚集索引index_birthday查找birthday等于1991-11-1的所有记录的主键ID值；
然后，通过得到的主键ID值执行聚集查找，找到主键ID值对应的真实数据（数据行）存储的位置；
最后，从得到的真实数据中取得user_name字段的值返回。

如果我们把birthday字段上的索引改成双字段的覆盖i索引：
CREATE INDEX index_birthday_and_user_name ON user_info(birthday, user_name); 
这句查询SQL语句的执行过程就变为：

通过非聚集索引index_birthday_and_user_name查找birthday等于1991-11-1的叶节点内容；
然而，叶结点中除了有user_name表主键ID的值外，user_name字段的值也在里面，因此不需要通过主键ID值得查找数据行的真实所在，直接取得叶节点中user_name的值返回即可。

通过这种覆盖索引直接查找的方式，可以省略不使用覆盖索引查找的后面两个步骤，大大提高查询性能。
图片说明