面试官:来说说mysql索引的基本原理


一般来说,系统中读写的比例大概为10:1,数据库的查询效率直接影响了系统的性能.

在生产系统中,查询过慢的情况也是频繁出现。几乎我曾经历过的每个项目上线都会出现慢查询的情况,尤其是当系统运行一段时间后,数据量变大,当初未设计索引的这些表的查询都会变慢。从我带过的团队成员来看,大部分同事在处理这个问题时都是无从下手。出现这种问题的原因在于并没有对索引的使用掌握扎实。

所以,我打算基于mysql索引的知识点整理几篇文章,这几篇文章的目的就是对各种的类型索引来进行实战,以及从案例项目中分析索引是如何作用的,一方面是给自己复盘复盘,另一方面是引导大家如何高效的使用索引。

首先,需要我们了解索引的本质是什么?
索引的目的在于提高查询效率,与我们读书的目录是一个道理,先找到目录章节,再找到页数。
其本质都是:通过不断缩小想要获取数据的范围来筛选出最终想要的结果,在搜索的过程中会将随机事件变成顺序事件。而在我们数据库的索引也是一样,区别在于数据库的数据不仅包括等值查询,还包括范围、and、or 、like 等查找事件,而数据又是存在磁盘上的。为了提高查询效率这就需要好好设计数据库索引的存储结构。
在mysql数据库中主要使用两种索引存储的数据结构:

1、hash索引

2、B+ tree 索引



Hash索引

hash索引是以hash的形式组织数据,hash索引是一种基于哈希表的索引结构,它是一种需要精确匹配才生效的索引结构。实现原理是:对索引列计算哈希值,把记录映射到哈希槽中,然后指向对应记录行的地址。提到哈希就会存在hash函数,比如 h(x) =  x%3 ,假如某个表有如下记录数:

面试官:来说说mysql索引的基本原理

我们对id列建立了一个hash索引,假设哈希函数是h (x) = x % 3,那么哈希表的结构如下:

面试官:来说说mysql索引的基本原理

可以看到,每个哈希槽对应一个哈希值,每个哈希值对应一个或多个记录行。如果我们要查询id=2的记录,我们只需要计算h (2) = 2,然后在哈希槽2中找到对应的记录行,就是(2, Bob)。这样就很快地找到了我们想要的结果。

hash索引的优点是查找速度非常快,大多数情况下都是O (1)的时间复杂度。但是它也有一些缺点,例如:
  • hash索引不支持排序,因为哈希表的结构是无序的。
  • hash索引不支持部分列索引查找,因为哈希函数是对整个索引列计算的,不能只匹配一部分。
  • hash索引只支持等值查询,无法提供范围查询功能,因为哈希函数的输出是随机的,不能按照大小顺序排列。
  • hash索引的查找效率受哈希冲突的影响,如果不同的索引列计算出相同的哈希值,就会导致哈希槽中有多个记录行,这样就需要遍历所有的记录行进行比较,降低了查询效率。


mysql的Memory存储引擎使用的就是hash索引。

B+tree 索引

B+tree 索引是一种基于 B+tree 数据结构的索引,它可以提高范围查询和排序的效率,同时节省磁盘空间和 IO 次数,在 MySQL innoDB存储引擎中,B+tree 索引是默认的索引类型,平常我们使用create index 语句就创建了一个B+tree 索引。

索引一般是比较大的,所以也是存储到了磁盘的数据文件中,当我们安装完mysql可以去看数据文件,如果是MyISAM存储引擎,则索引文件和数据文件是分开存放的,如果是innodb存储引擎,则索引文件和数据文件是同一个文件。

这就又引出了一个概念,聚簇索引和非聚簇索引

聚簇索引:将索引和数据存储到一起,索引结构的叶子节点存放着数据,其他非叶子节点存指针和索引。在innodb存储引擎中。

非聚簇索引:数据和索引分开存储,索引结构的叶子节点指向了数据对应的位置。

innodb的主键索引和非主键索引

在innodb中,又分为主键索引和非主键索引,主键索引就是聚簇索引,而非主键索引为非聚簇索引,又称为二级索引。假如我们在某张表中创建索引,如下:

CREATE TABLE user (

 id INT PRIMARY KEY, — 主键默认为聚簇索引

 name VARCHAR(50) NOT NULL

) ENGINE=InnoDB; — 指定存储引擎为 InnoDB

上面的sql,主键就是索引,这个主键索引就是聚簇索引,它是按照主键的顺序进行数据存储,并构造b+tree的数据结构,B+tree的叶子节点就是行记录,行记录与主键值紧凑的存储到一起,这也意味着innodb的主键索引就是数据表本身,它按主键的顺序存放了整张表的数据,占用的空间就是整个表数据量的大小。

其存储结构大致如下:

面试官:来说说mysql索引的基本原理

面试官:来说说mysql索引的基本原理

以上部分图片来源于网络,如有侵权请私信告知。

而非主键索引,比如,在name列上创建索引

CREATE TABLE user (

 id INT PRIMARY KEY,

 name VARCHAR(50) NOT NULL,

INDEX idx_name (name) — 创建非聚簇索引

) ENGINE=InnoDB;

上面的sql中使用name列作为索引,它属于非聚簇索引,又称二级索引或辅助索引,这种情况是根据索引列构建B+tree结构,在叶子节点中只存储了索引列和主键的信息。二级索引占用的空间会比聚簇索引小很多,通常创建辅助索引就是为了提升查询效率。在innodb存储引擎中,一个表只能创建一个聚簇索引,但可以创建多个辅助索引。

非聚簇索引的叶子节点存储的是主键的值,而不是完整的数据,所以需要通过主键再到聚簇索引中查找数据,这个过程叫做回表。如下图所示:

面试官:来说说mysql索引的基本原理

面试官:来说说mysql索引的基本原理

假如要查询name = C 的数据,其搜索过程如下:
  1. 先在辅助索引中通过C查询最后找到主键id = 9.
  2. 在主键索引中搜索id为9的数据,最终在主键索引的叶子节点中获取到真正的数据。
所以通过辅助索引进行检索,需要检索两次索引。

本篇内容总结
  1. innodb存储引擎中,数据文件和索引文件分开存储。

  2. mysql数据库包含两种方式的索引,hash索引和b+tree索引,innodb存储引擎默认使用b+tree索引。

  3. B+tree索引从大类上分为聚簇索引和非聚簇索引,在innodb存储引擎中,使用的是聚簇索引。

  4. 聚簇索引是将数据按照索引顺序存储在磁盘上,因此聚簇索引的数据存储和索引存储是混合在一起的;而非聚簇索引则是将索引和数据分开存储的,通过指针来定位数据行。

  5. 在 InnoDB 存储引擎中,聚簇索引是按照主键顺序存储数据的一种索引类型,它可以提高数据的访问速度,但也有一些限制,例如每个表只能有一个聚簇索引,而且主键的长度不能太长。

  6. 在其他字段创建的索引,通常是非聚簇索引,也就是二级索引或普通索引。非聚簇索引的叶子节点存储的是主键的值,而不是完整的数据,所以需要通过主键再到聚簇索引中查找数据,这个过程叫做回表。

  7. 并不是所有的非主键索引都是非聚簇索引,有一种特殊的情况,就是当表没有显式定义主键,也没有唯一非空索引时,InnoDB 会自动创建一个隐藏的 row-id 作为聚簇索引。这时,如果在其他字段创建唯一索引,那么这个唯一索引就会变成聚簇索引,而原来的 row-id 就会变成非聚簇索引。

  8. 一般来说,在 InnoDB 存储引擎中,在主键上的索引就是聚簇索引,在其他字段创建的索引都是非聚簇索引,但也有例外的情况,需要具体分析。

  9. B+tree 的叶子节点存储了所有的数据,而且通过指针相连,形成一个有序链表,这样可以方便地进行范围查询和排序,而哈希索引等无法支持范围查询。B+tree 的非叶子节点只存储关键字和指针,不存储数据,这样可以增加每个节点的容量,减少树的高度,也可以减少索引的维护成本。


原文始发于微信公众号(小核桃编程):面试官:来说说mysql索引的基本原理

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/216077.html

(0)
李, 若俞的头像李, 若俞

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!