MySQL:索引工作原理

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介:

为什么需要索引(Why is it needed)?

当数据保存在磁盘类存储介质上时,它是作为数据块存放。这些数据块是被当作一个整体来访问的,这样可以保证操作的原子性。硬盘数据块存储结构类似于链表,都包含数据部分,以及一个指向下一个节点(或数据块)的指针,不需要连续存储。

记录集只能在某个关键字段上进行排序,所以如果需要在一个无序字段上进行搜索,就要执行一个线性搜索(Linear Search)的过程,平均需要访问N/2的数据块,N是表所占据的数据块数目。如果这个字段是一个非主键字段(也就是说,不包含唯一的访问入口),那么需要在N个数据块上搜索整个表格空间。

但是对于一个有序字段,可以运用二分查找(Binary Search),这样只要访问log2 (N)的数据块。这就是为什么性能能得到本质上的提高。


什么是索引(What is indexing)?

索引是对记录集的多个字段进行排序的方法。在一张表中为一个字段创建一个索引,将创建另外一个数据结构,包含字段数值以及指向相关记录的指针,然后对这个索引结构进行排序,允许在该数据上进行二分法排序。

副作用是索引需要额外的磁盘空间,对于MyISAM引擎而言,这些索引是被统一保存在一张表中的,这个文件将很快到达底层文件系统所能够支持的大小限制,如果很多字段都建立了索引的话。


索引如何工作(How does it work?)

首先,我们建立一个示范数据库表:

字段名       数据类型      大小
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes
注意:使用char是为了指定准确的磁盘占用大小。这个示范数据库包含500万行,而且没有索引。我们将分析一些查询语句的性能,一个是使用主键id(有序)查询,一个是使用firstName(非关键无序字段)。

例1

我们的示范数据库有r=5,000,000条记录,每条记录长度R=204字节而且使用MyISAM引擎存储(默认数据块大小为B=1024字节),这张表的块因子(blocking factor)会是bfr = (B/R) = 1024/204 = 5 条记录每磁盘数据块。保存这张表所需要的磁盘块为N = (r/bfr) = 5000000/5 = 1,000,000 blocks。

在id字段上的线性搜索平均需要N/2 = 500,000块访问来找到一条记录假设id字段是查询关键值,不过既然id字段是有序的,可以执行一个二分查询,这样平均只需要访问log2 (1000000) = 19.93 = 20 个数据块。我们马上就看到了极大的提高。

现在firstName字段既不是有序的,无法执行二分搜索,数值也不具有唯一性,所以对这张表的查找必须到最后一个记录即全表扫描N = 1,000,000个数据块访问。这就是索引用来改进的地方。

假如索引记录只包含一个索引列以及一个指向原记录数据的指针,那么它显而易见会比原记录(多列)要小。所以索引本身所需要的磁盘块要更少,扫描数目也少。firstName索引表结构如下:

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes
注意: MySQL里的指针按表大小的不同分别可能是 2, 3, 4 或 5 个字节。

例2

假设我们的数据库有r = 5,000,000 条记录,建立了一个长R = 54字节的索引,并且使用默认磁盘块大小为1,024字节。那么该索引的块因子为bfr = (B/R) = 1024/54 = 18 条记录每磁盘块。容纳这个索引表总共需要的磁盘块为N = (r/bfr) = 5000000/18 = 277,778 块。

现在使用FirstName字段来进行搜索就可以利用索引来提高性能。这允许使用一个二分查找,平均log2 (277778) = 18.08 -> 19次数据块访问。找到实际记录的地址,这需要进一步的块读取,这样总数达到19 + 1 = 20次数据块访问,这和非索引表的数据块访问次数有天壤之别。


什么时候使用索引(When should it be used?)

鉴于创建索引需要额外的磁盘空间(上面的例子需要额外的277778个磁盘块),以及太多的索引会导致文件系统大小限制所产生的问题,所以对哪些字段建立索引,什么情况下使用索引,需要审慎考虑。

由于索引只是用来加速数据查询,那么显然对只是用来输出的字段建立索引会浪费磁盘空间以及发生插入、删除操作时的处理时间,所以这种情况下应该尽量避免。此外鉴于二分搜索的特性,数据的基数或独立性是很重要的。在基数为2的字段上建立索引,将把数据分割一半,而基数为1000则将返回大约1000条记录。低基数的二分查找效率将降低为一个线性排序,而且查询优化器可能会在基数小于记录数某个比例时(如30%)的情况下将避免使用索引而直接查询原表,所以这种情况下的索引浪费了空间。












本文转自yunlielai51CTO博客,原文链接:http://blog.51cto.com/4925054/2083725,如需转载请自行联系原作者


相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
MySQL实现文档全文搜索,分词匹配多段落重排展示,知识库搜索原理分享
本文介绍了在文档管理系统中实现高效全文搜索的方案。为解决原有ES搜索引擎私有化部署复杂、运维成本高的问题,我们转而使用MySQL实现搜索功能。通过对用户输入预处理、数据库模糊匹配、结果分段与关键字标红等步骤,实现了精准且高效的搜索效果。目前方案适用于中小企业,未来将根据需求优化并可能重新引入专业搜索引擎以提升性能。
MySQL原理简介—6.简单的生产优化案例
本文介绍了数据库和存储系统的几个主题: 1. **MySQL日志的顺序写和数据文件的随机读指标**:解释了磁盘随机读和顺序写的原理及对数据库性能的影响。 2. **Linux存储系统软件层原理及IO调度优化原理**:解析了Linux存储系统的分层架构,包括VFS、Page Cache、IO调度等,并推荐使用deadline算法优化IO调度。 3. **数据库服务器使用的RAID存储架构**:介绍了RAID技术的基本概念及其如何通过多磁盘阵列提高存储容量和数据冗余性。 4. **数据库Too many connections故障定位**:分析了MySQL连接数限制问题的原因及解决方法。
MySQL原理简介—3.生产环境的部署压测
本文介绍了Java系统和数据库在高并发场景下的压测要点: 1. 普通系统在4核8G机器上每秒能处理几百个请求 2. 高并发下数据库建议使用8核16G或更高配置的机器 3. 数据库部署后需进行基准压测,以评估其最大承载能力 4. QPS和TPS的区别及重要性 5. 压测时需关注IOPS、吞吐量、延迟 6. 除了QPS和TPS,还需监控CPU、内存、磁盘IO、网络带宽 7. 影响每秒可处理并发请求数的因素包括线程数、CPU、内存、磁盘IO和网络带宽 8. Sysbench是数据库压测工具,可构造测试数据并模拟高并发场景 9. 在增加线程数量的同时,必须观察机器的性能,确保各硬件负载在合理范围
138 72
MySQL底层概述—8.JOIN排序索引优化
本文主要介绍了MySQL中几种关键的优化技术和概念,包括Join算法原理、IN和EXISTS函数的使用场景、索引排序与额外排序(Using filesort)的区别及优化方法、以及单表和多表查询的索引优化策略。
MySQL底层概述—8.JOIN排序索引优化
RDS用多了,你还知道MySQL主从复制底层原理和实现方案吗?
随着数据量增长和业务扩展,单个数据库难以满足需求,需调整为集群模式以实现负载均衡和读写分离。MySQL主从复制是常见的高可用架构,通过binlog日志同步数据,确保主从数据一致性。本文详细介绍MySQL主从复制原理及配置步骤,包括一主二从集群的搭建过程,帮助读者实现稳定可靠的数据库高可用架构。
84 9
RDS用多了,你还知道MySQL主从复制底层原理和实现方案吗?
MySQL原理简介—9.MySQL索引原理
本文详细介绍了MySQL索引的设计与使用原则,涵盖磁盘数据页的存储结构、页分裂机制、主键索引设计及查询过程、聚簇索引和二级索引的原理、B+树索引的维护、联合索引的使用规则、SQL排序和分组时如何利用索引、回表查询对性能的影响以及索引覆盖的概念。此外还讨论了索引设计的案例,包括如何处理where筛选和order by排序之间的冲突、低基数字段的处理方式、范围查询字段的位置安排,以及通过辅助索引来优化特定查询场景。总结了设计索引的原则,如尽量包含where、order by、group by中的字段,选择离散度高的字段作为索引,限制索引数量,并针对频繁查询的低基数字段进行特殊处理等。
MySQL原理简介—9.MySQL索引原理
MySQL底层概述—6.索引原理
本文详细回顾了:索引原理、二叉查找树、平衡二叉树(AVL树)、红黑树、B-Tree、B+Tree、Hash索引、聚簇索引与非聚簇索引。
MySQL底层概述—6.索引原理
MySQL原理简介—12.MySQL主从同步
本文介绍了四种为MySQL搭建主从复制架构的方法:异步复制、半同步复制、GTID复制和并行复制。异步复制通过配置主库和从库实现简单的主从架构,但存在数据丢失风险;半同步复制确保日志复制到从库后再提交事务,提高了数据安全性;GTID复制简化了配置过程,增强了复制的可靠性和管理性;并行复制通过多线程技术降低主从同步延迟,保证数据一致性。此外,还讨论了如何使用工具监控主从延迟及应对策略,如强制读主库以确保即时读取最新数据。
MySQL原理简介—12.MySQL主从同步
MySQL原理简介—7.redo日志的底层原理
本文介绍了MySQL中redo日志和undo日志的主要内容: 1. redo日志的意义:确保事务提交后数据不丢失,通过记录修改操作并在系统宕机后重做日志恢复数据。 2. redo日志文件构成:记录表空间号、数据页号、偏移量及修改内容。 3. redo日志写入机制:redo日志先写入Redo Log Buffer,再批量刷入磁盘文件,减少随机写以提高性能。 4. Redo Log Buffer解析:描述Redo Log Buffer的内存结构及刷盘时机,如事务提交、Buffer过半或后台线程定时刷新。 5. undo日志原理:用于事务回滚,记录插入、删除和更新前的数据状态,确保事务可完整回滚。
124 22
MySQL原理简介—8.MySQL并发事务处理
这段内容深入探讨了SQL语句执行原理、事务并发问题、MySQL事务隔离级别及其实现机制、锁机制以及数据库性能优化等多个方面。