MySQL 数据结构优化与索引细节解析:打造高效数据库的优化秘笈(一)

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: MySQL 数据结构优化与索引细节解析:打造高效数据库的优化秘笈

前言

在上篇博文:构建优化之城:MySQL 数据建模、数据类型优化与索引常识全面解析 提到了数据建模方案及数据类型的优化方案,简要说明了一些索引的基本知识及分类、技术名词,该篇博文会从以下几点来对 MySQL 调优部分进行分析:

  1. 索引数据结构、优化细节
  2. 大数据量查询优化
  3. 海量数据解耦优化处理

数据结构

InnoDB、MyISAM 存储引擎底层索引使用的 B+ Tree,Memory 存储引擎使用的 hash

推荐一个数据结构可视化网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

HASH

hash 表存在于就是一个数组,然后在每一个数组下可以添加一个数据桶,以链表的方式进行实现。hash 表有对应的下标值,从 0 开始进行排列,若想要往 hash 表里放数据的话,必须要经过散列算法,然后计算出对应的位置,将数据放入到指定的位置中,而散列算法最简单的实现就是取模运算

hash 表方式看起来虽然很好,能够通过对应的下标位置定位到某一条记录,但是需要注意 hash 表同样也有明显的缺点

  1. 会占用大量的内存空间,在每次使用 hash 表时需要将大量的数据加载到内存中,此时是非常浪费内存空间的,所以在 MySQL Memory 存储引擎中使用 hash 索引,像 InnoDB 这种存储引擎支持自适应 hash,但它是由 MySQL 自主控制的
  2. 在进行数据查询时都是等值查询,首先通过 Key 计算出 hash 值,然后定位到某一个位置,进行 Key 比较,但是大部分公司用的都是基于范围查询,而 hash 表在进行范围查询时必须挨个匹配,这样查询会比较浪费时间,所以不太合适。最终可以得出结论:若每次查询都是等值查询,那么 hash 表方式查询是是比较快的,若是基于范围查询,hash 方式查询是比较慢的
  3. 使用 hash 表存储数据时,需要设计比较优秀的 hash 算法,若算法设计不合理的话,会导致数据散列不均匀,浪费比较多的存储空间,同时在数据查询时会导致查询效率较低

基于以上缺点,在 MySQL InnoDB、MyISAM 存储引擎并没有使用 hash 表来存储数据,而 Memory 存储引擎使用了 hash 表这样的方式,注意索引的数据结构选择与存储引擎是息息相关的

Binary Search Trees、AVL Trees

基于二叉树会产生一条腿长一条腿短,这样的话很明显会编程挨个对比的过程,而当插入的数据越来越多时,会导致链表越长,这样的效率一定是比较低的,大于根节点值往右边塞 < 小于根节点值往左边塞 >

造成上述问题,最关键的原因:树的左右分支不够平衡,因此后续才有了二叉平衡树,即 AVL 树,如下图:

AVL 树要求左子树、右子树之间的高度之差不能超过 1,因此在进行数据插入时会造成 N 个旋转操作来保持树的平衡,所以在进行数据插入时效率比较低,查询的效率会比较快,这样的话可以理解为损失部分性能来满足查询性能的提升,但会引起插入、删除需求比较多时,如何解决呢?插入数据的越来越多,会造成树越来越深,从而会造成查询效率降低

Red/Black Trees

红黑树也基于二叉平衡树,只不过不是严格意义上的平衡树;在 AVL 树中,要求左右子树的高度之差不能超过 1,但红黑树的要求是最长子树只要不超过最短子树的两倍路径长度就好,如下图:

通过以上的分析,可以得出一个结论:无论是那种类型的二叉树,最终都会存在一个问题,随着数据量的增加,树的层数就会增加,那么就会造成 IO 次数越多,从而影响数据读取的效率

B Trees

B 树的数据结构特点如下:

  1. 所有键值分布在整棵树中
  2. 搜索有可能在非叶子节点结束(有可能在度为 0 或度为 1 的节点结束)在关键字全局内作一次查找,性能逼近于 二分查找
  3. 每个节点最多拥有 M 个子树,根节点至少有 2 个子树
  4. 分支节点至少拥有 M/2 颗子树(除根节点、叶子节点都是分支节点)
  5. 所有叶子节点都在同一层,每个叶子节点最多有 M-1 Key,并且以升序排列

在 MySQL 使用 B 树结构进行数据存储时,如下图:

每一个树节点都占用一个磁盘块,一个节点上有两个升序排序的关键词(如:16、34)以及三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址。两个关键词(16、34)划分成三个范围域对应三个指针所指向的子树数据范围域,以根节点 16、34 为例子,P1 指针指向的子树数据范围小于 16,P2 指针指向的子树数据范围为 16~34,P3 指针指向的子树数据范围大于 34

比如,要找出关键词等于 28,查找关键词过程如下:

  1. 通过根节点找到磁盘块 1,读入内存【磁盘 I/O 操纵第一次】
  2. 比较关键字 28 在区间(16~34)找到磁盘块 1 中的 P2 指针
  3. 通过 P2 指针找到磁盘块 3,读入内存【磁盘 I/O 操纵第二次】
  4. 比较关键字 28 在区间(25~31)找到磁盘块 3 中的 P2 指针
  5. 通过 P2 指针找到磁盘块 8,读入内存【磁盘 I/O 操纵第三次】
  6. 在磁盘块 8 中的关键词列表,找到关键字 28

B 树作为存储索引的数据结构,缺点如下:

  1. 每个节点都有 Key,同时也包含了 data,但每个页的存储空间是有限的,若 data 比较大的话会导致每个节点存储的 Key 数量变小
  2. 当存储数据量很大时会导致深度越大,同时就会增大查询时的磁盘 IO 次数,进而影响了查询性能
  3. InnoDB 存储引擎,默认情况下读取的是 16 KB,一共会读取三个磁盘块,意味着一共读取了 48 KB 数据,假设说上面这些 P 指针、节点 Key 都不需要占用额外的存储空间,一条数据占用 1 KB,那意味着当前节点里面最多存储 16 条数据,下一个磁盘块也是 16 条,第三个磁盘块也是 16 条,最终的总数也就是 4096 条,故而这个支撑的数据量太少了!

B+ Trees

B+ 树是在 B 树基础之上作的一种优化,如下:

  1. B+ 树每个节点可以包含更多的节点,这样做的原因是:为了降低树的高度、将数据范围变为多个区间,区间越多,数据检索越快
  2. 非叶子节点存储 Key,叶子节点存储 Key、数据
  3. 叶子节点之间通过指针相互连接在一起(符合磁盘的预读特性)顺序查询性能更高

在 B+ 树有两个头指针:一个指向根节点,另一个指向关键词最小的叶子节点,但所有叶子节点(数据节点)之间是一种链式环结构;因此可以对 B+ Tree 进行两种查找运算:

  1. 对于主键的范围查询、分页查询
  2. 从根节点开始,进行随机查找

叶子节点负责存储数据,非叶子节点不存储数据,能保证尽可能多的存储数据,查找数据的方式不变,可以进行计算一下三层的 B+ 树能存储多少数据

读取数据仍然是 16 KB,假设:P 指针、节点 Key 占用 10 字节,那么 16 KB = 16*1000/10,结果为 1600,第二层也是 1600,第三层还是 1600,最终的结果:40960000,可达到千万级别,而刚刚 B 树为 4096,完全不是量级的数据

数据存储

在上述中,是对 MySQL 索引结构的统一描述,但对于不同的存储引擎来说,虽然使用的都是基于 B+ Tree 数据结构,但在实际存储数据时是完全不一样的

InnoDB

在 InnoDB 存储引擎中,数据、索引是放在一起的,因此你看到的只有 idb 文件,其中既能存储实际的数据,又可以存储索引数据,因此当查询索引时,能够直接从叶子节点中获取需要的数据行,如下图:

[root@trench study]# cat /etc/my.cnf
# 找到 datadir 配置所在的文件目录
[root@trench study]# pwd
/var/lib/mysql/study
[root@trench study]# ll
total 1152
# 表结构文件
-rw-r----- 1 mysql mysql   8586 May 16 22:22 course.frm
-rw-r----- 1 mysql mysql  98304 May 16 22:24 course.ibd

InnoDB 通过 B+ Trees 结构对主键创建索引,然后在叶子节点中存储记录,若没有主键,那么就选择唯一键,后台就会生成一个 6 字节的 row_id 作为主键

若创建索引的键是其他字段,那么叶子节点存储的是该记录的主键,然后再通过主键索引找到对应的记录,这叫做回表

MyISAM

在 MyISAM 存储引擎中,数据文件、索引文件是分开存储的,所以能看到两个文件,后缀分别是:MYI、MYD,因此在进行数据检索时,需要读取两个文件,在索引的数据结构中存储的是实际的数据行地址,如下图:

[root@trench study]# pwd
/var/lib/mysql/study
[root@trench study]# ll
total 1064
# 表结构文件
-rw-r----- 1 mysql mysql   8586 May 16 22:36 course.frm
-rw-r----- 1 mysql mysql    120 May 16 22:36 course.MYD
-rw-r----- 1 mysql mysql   2048 May 16 22:36 course.MYI

索引优化

上一篇讲到了索引的基本概念、索引的分类以及索引相关的技术名词

在 MySQL 官网中,给了数据库、表案例 > sakila 数据库,如下:https://dev.mysql.com/doc/index-other.html,后续会基于该数据库表进行索引优化演示

相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
2天前
|
缓存 算法 关系型数据库
MySQL底层概述—8.JOIN排序索引优化
本文主要介绍了MySQL中几种关键的优化技术和概念,包括Join算法原理、IN和EXISTS函数的使用场景、索引排序与额外排序(Using filesort)的区别及优化方法、以及单表和多表查询的索引优化策略。
MySQL底层概述—8.JOIN排序索引优化
|
2天前
|
SQL 关系型数据库 MySQL
MySQL底层概述—7.优化原则及慢查询
本文主要介绍了:Explain概述、Explain详解、索引优化数据准备、索引优化原则详解、慢查询设置与测试、慢查询SQL优化思路
MySQL底层概述—7.优化原则及慢查询
|
3天前
|
存储 缓存 关系型数据库
MySQL底层概述—5.InnoDB参数优化
本文介绍了MySQL数据库中与内存、日志和IO线程相关的参数优化,旨在提升数据库性能。主要内容包括: 1. 内存相关参数优化:缓冲池内存大小配置、配置多个Buffer Pool实例、Chunk大小配置、InnoDB缓存性能评估、Page管理相关参数、Change Buffer相关参数优化。 2. 日志相关参数优化:日志缓冲区配置、日志文件参数优化。 3. IO线程相关参数优化: 查询缓存参数、脏页刷盘参数、LRU链表参数、脏页刷盘相关参数。
MySQL底层概述—5.InnoDB参数优化
|
3天前
|
存储 关系型数据库 MySQL
MySQL底层概述—6.索引原理
本文详细回顾了:索引原理、二叉查找树、平衡二叉树(AVL树)、红黑树、B-Tree、B+Tree、Hash索引、聚簇索引与非聚簇索引。
MySQL底层概述—6.索引原理
|
5天前
|
SQL 关系型数据库 MySQL
MySQL原理简介—11.优化案例介绍
本文介绍了四个SQL性能优化案例,涵盖不同场景下的问题分析与解决方案: 1. 禁止或改写SQL避免自动半连接优化。 2. 指定索引避免按聚簇索引全表扫描大表。 3. 按聚簇索引扫描小表减少回表次数。 4. 避免产生长事务长时间执行。
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
328 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
53 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
43 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9

推荐镜像

更多