MySQL学习之索引

图片

阅读本文大约需要 8 分钟。

提到索引,我相信在座各位应该都会有所了解,在实际开发中也会经常用到。比如我们通过慢日志查询的时候,看到有SQL查询比较慢的时候,会想到给哪个字段加个索引吧。但是什么是索引?索引又是怎么工作的呢?

什么是索引? 所以的出现就是为了提高数据查询的效率,它就像书的目录一样,能让你进行快速的找到某一章节,更快速的进行定位。

索引常见的模型

索引的实现方式有很多种,我们之前也进行了数据结构学习,正好在这里可以用到。有兴趣的可以进去看下

数据结构

thinkabel,公众号:白砂
数据结构之PHP二分搜索树

常见的实现是哈希表、有序数组、搜索树,先看下每个数据结构的一些特点:

  • 哈希表

  • 哈希是一种以键值(key-value)对形式存储的数据结构,把值放到数组里,用一个哈希函数把key转换成一个固定的值,然后把value放在这个数组这个位置。

  • 有序数组

  • 有序数据作为索引

  • 搜索树

  • 就是一个二叉搜索树,二叉搜索树的特点就是:左子树的节点值小于父节点的值,右子树的节点值大于父节点的值。

引发的思考

我们知道,在经过多个key值经过哈希函数后,会出现同一个值的情况,这种情况是哈希冲突。那怎么进行处理的呢?

在MySQL索引中,处理这个哈希冲突的方法就是拉出一个链表。如下图所示:

图片

(哈希表 示意图)

流程是这样的,User2 和 User4根据身份证号计算出的哈希值是N,然后遍历链表,找到要查找的name。通过上面我们能看到,每个数据块并不是递增的,这样做的好处是增加新的User时,速度是比较快的,直接往后追加。缺点也就显而易见,不易于做区间查询,速度是很慢的,成本太高。所以**哈希表只适合做等值查询的场景。**

这时你是不是会想,既然哈希做查区间查询很慢,那有序索引就可以解决这个问题,效率很高啊。

没错,仅仅看有查询效率中,有序索引就是最好的数据结构,但是有序索引在进行插入操作时,是不是就必须要挪动后面所有的记录,成本也随之高了。所以有序索引只适合用于静态存储引擎,比如某一年的某某信息,比较固定。

这时你会想,这两种方式都不好,那二分搜索树可以吧?查询和更新的时间复杂度都是O(log(N))。

当然,二叉树的搜索效率是最高的,索引不止要存在内存中,还要写到磁盘上。可以想象一下,如果树的深度比较高。树的不同结点可能不在磁盘的同一页中,所以每次磁盘的寻址加载次数,IO就越多,自然查找就会慢。

因此这里就不能使用二叉树,而是使用“N”叉树。这个“N”取决于数据块(也称页)的大小。

这些普及知识到这里先结束了,虽然很枯燥无味,坚持就是胜利。

主键索引和普通索引的区别

在InnoDB中,表都是根据主键顺序以索引形式存放的,这种存储方式称之为索引组织表。InnoDB 使用的是B+树索引模型,所以数据都是存放在B+树上的。每一个索引在InnoDB中对应一棵B+树。

mysql> create table T(
    id int primary key, 
    k int not null, 
    name varchar(16),
    index (k)
)engine=InnoDB;

图片

(InnoDB索引 组织结构图)

从图中可以看到,主键索引的叶子节点存的是整行数据,而非主键索引存放的是主键的值。(叶子节点之间是通过双向链表进行关联的,所以在进行区间查找的时候是很方便的)。

我们通过主键id查询一条语句的话,只需要找到id这颗B+树,就能找到需要的数据;

但是我们通过普通索引进行查找的话,需要先找到k的索引B+树,因为非主键索引下放的是主键的值,我们需要在拿到这个主键的值去主键索引树中继续查找。这个过程就有了一个**回表**操作。

非主键索引会比主键索引多一次扫描索引树的操作,效率会比主键索引低。

索引维护引发的一些问题

既然索引是通过B+树进行实现的,不然是树还是数组,都需要有维护这个树或者数组的操作。

还是使用上面的图来说明吧,比如现在插入新的行ID 是 700, 只需要在R5的记录后面插入一个新的记录,整体结构不会有什么改动。如果新插入的ID值是400,那就需要逻辑上挪动300后面的数据,为400空出位置。

这个时候,如果说这个R5这个数据页满了,根据B+数的算法,就需要申请一个新的数据页,然后把数据挪动过去。这个过程称为页分裂。

这里借用一下手机的例子,就是比如你整理手机桌面,把一些游戏的软件归纳到一个盒子里,这时盒子第一页已经满了,你想往这个里面放入一个,在你放入位置后面的软件都需要移动到新的一页中

我们想一下,在这个分裂的过程中,自然性能会受到影响;也要想到一个点,就是在新的数据页中,会产生一定的空间浪费。

有分裂自然也就有合并,当相邻的两个页删除了数据,利用率很低后,会将数据页进行合并,合并的过程中也就是分裂的逆操作

思考

  • 在我们日常开发中,我们应该是使用什么作为主键呢?是以自增id作为主键 还是 以业务逻辑的字段作为主键呢?

** 想象一下,使用id为主键的时候,建表语句中是不是有 primary key auto_increment。每次插入新数据的时候,是不指定id的,系统会在 AUTO_INCREMENT 记录下一个的id值。**

也就是说**自增主键是每次插入一条记录,都是追加操作,不会挪动其他记录,所以不会产生叶子节点的分裂。
**

而业务逻辑做主键,是不能保证有序插入的,这样写成本的效率相对很高。

还有一点就是,每个非主键上的叶子节点存储的都是主键的值, 主键长度越小,普通索引节点就越小,占用空间就越小。从性能和空间占用方面考虑,自增主键往往是比较合理的选择。

  • 在我们正常查询中,避免不了肯定不能全部都是以主键为条件进行查询的,这个时候,就会有回表操作,怎么避免回表的操作呢?

解决这个问题呢,我们可以通过覆盖索引的方式。前提是我们查询的数据字段,要是在索引上,这样索引就已经覆盖了我们需要的查询需求,所以在索引上就已经获取到我们想要的数据,自然也就不需要进行回表了。

覆盖索引

图片

(InnoDB 索引组织结构)

select * from T where k between 3 and 5

我们执行看看这个流程:

1. 在 k 索引树上找到 k = 3 的记录,取得主键索引值为 300;

2. 在主键id索引树上找到 id = 300 的 行数据 R3;

3. 在 k 索引树取下一个值 k=5,取得 ID=500;

4. 再回到 ID 索引树查到 ID=500 对应的 R4;

5. 在 k 索引树取下一个值 k=6,不满足条件,循环结束。

我们可以看到,回到主键索引树上进行搜索了两次,也就是回表了两次。这个就是回表的过程。

如果我们把SQL语句改成:

select ID from T where k between 3 and 5

只需要查询id的值,id的值已经存在k这个索引树上,直接就可以讲结果返回,不需要在进行回表查询,所以** 索引树 k 覆盖了查询需求, 这就是覆盖索引。**

覆盖索引可以减少树的搜索次数,显著提升了查询性能,是一种常用的性能优化手段。

最左前缀原则

这里我们会想到,没给一个字段都设计一个索引。是不是索引也太多了, 索引多往往也会影响查询性能,可能还会造成空间浪费,那该怎么办?

我们可以使用联合索引进行优化,B+树这种索引结构,可以利用索引的最左前缀来进行定位记录。

  • 举例:

  • 用(name,age)这个联合索引来分析

  • 索引项是按照索引定义里面出现的字段顺序排序的

  • 当你的逻辑需求是查到所有名字是 张三 的人时,可以快速定位到 ID4,然后向后遍历得到所有需要的结果

  • 如果要查的是名字第一个字是 张 的人,SQL 语句条件是 where name like ‘张 %’,查找到第一个符合的记录是 ID3,然后向后遍历,直到不满足条件为止

  • 只要满足最左前缀,就可以利用索引来加速检索,可以是联合索引的最左 N 个字段,也可以是字符串索引的最左 M 个字符

索引下推

这是我们可能会有疑问,就是那些没有被最左前缀命中的记录,会怎么样呢?

图片

如果要查的是名字第一个字是 张 的人,SQL 语句条件是 where name like ‘张 %’,查找到第一个符合的记录是 ID3,然后向后遍历,直到不满足条件为止。这个时候会查到所有姓张的。

但是我们把条件改成:

select * from tuser where name like ‘张%’ and age=10 and ismale=1

这个时候,InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10,对于不等于 10 的记录,直接判断并跳过。在我们的这个例子中,只需要对 ID4、ID5 这两条记录回表取数据判断,就只需要回表 2 次。

图片

最后,求关注。如果你还想看更多优质原创文章,欢迎关注我的公众号「白砂」

如果我的文章对你有所帮助,还请帮忙点赞、在看、转发一下,你的支持会激励我输出更高质量的文章,非常感谢!

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 3

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!