MySQL - 剖析MySQL索引底层数据结构

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
云数据库 RDS MySQL,高可用系列 2核4GB
简介: MySQL - 剖析MySQL索引底层数据结构

20200718163724889.png

更多干货

带你搞定MySQL实战,轻松对应海量业务处理及高并发需求,从容应对大场面试


Pre

什么是索引?

通俗的说就是为了提高效率专门设计的一种 排好序数据结构


怎么理解呢?

举个例子哈



20200718164913418.png


如上数据 ,假设有个SQL

select *  from t where  col2 = 22 ;


如果没有索引的话,是不是得逐行进行全表扫描,走磁盘IO…

如果加上一个合适的索引呢?

比如用一个二叉树


20200718170054677.png


二叉树我们知道,右边的比左边大

那执行刚才的SQL的话,第一条记录是34 ,那我们查找的是22, 是不是就只要到它的左边查找即可,因为右边的数据都比34大,肯定没有22 ,找到22 以后, 搞定 ,I/O次数是不是比刚才的全表扫描的次数少很多,那效率自然就高了。


索引的数据结构选型


二叉树 ?


可以用二叉树吗? 我们知道MySQL一般都有自增主键 ,id之类的字段

我们来演示下使用二叉树来存储这种自增的数据的话,会怎样?


https://www.cs.usfca.edu/~galles/visualization/BST.html

20200718175347147.gif



那查询

select * from t where id = 7


20200718171255172.gif


自增主键的时候 这个二叉树已经退化成链表了。。。。。


想想,一个几百万数据量的表 ,查找某个大一点的id , 逐个查找比对 (这些数据也是存储在磁盘上的,还得从磁盘上捞啊) 这I/O 这效率可想而知吧…


二叉树 pass ,不考虑了


既然退化成链表了,那试试带有平衡功能的树 二叉平衡树 (红黑树)?


自增主键, 退化为为链表


红黑树 ?


二叉树既然在某些情况下会退化成链表, 那如果这棵树能自动平衡呢?


202007181802599.gif

这样子是不可能变成链表了,

同样 查询

select * from t where id = 7


20200718204705280.gif



三次磁盘I/O即可找到, 比刚才二叉树的七次是少了些哈 ,自然查找效率也比二叉树高了

可如果数据量几百万 上千万呢?

这棵树 得多高哇。。。

数据量大, 树高问题

那既然树高不好, 是不是如果可以控制树的高度(比如 3 到4层的高度,这样查询起来还能接受),让每一层能存储更多的数据,然后再分裂,这样的话数据量相乘起来,也是不少了对吧,这样就能存储更多的数据,这样会不会好一点? ----> B-Tree


B-Tree ?


  • 叶节点具有相同的深度, 叶节点之间指针为空
  • 所有索引元素不重复
  • 节点中的数据索引从左到右递增排列


20200718221418845.png


叶子节点之间的没有指针,区别于B+树。

data存储的是数据对应的磁盘地址, k-v结构。

我们来看下B-Tree的插入 (Max.Degree 设置为3 即 元素到了3个就分裂 )


20200719093236648.gif

查找一下

20200719093349753.gif



3次

MySQL也没有使用B-Tree , 因为



20200719133625517.png除了存储索引以外,还存储了data(数据对应的磁盘地址) , 为了更多的存储数据,MySQL对B-Tree进行了很多改造

由此演进出了 B+Tree ,将data部分仅保留在叶子节点上,这样的话同等的页可以存储更多而索引数据。


B+Tree


  • 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点用指针连接,提高区间访问的性能



2020071913400456.png


数据仅存储在叶子节点, data可能是磁盘地址也可能是其他的列数据,这个和存储引擎有关系。

叶子节点之间有指针相连。

我们来算下 3层高的B+Tree能存储多少数据结构

假设是BigInt类型的数据

2020071913425424.png


BigInt 占 8个字节 ,同时还是用6个字节存储了它指向的数据的物理地址

MySQL在使用innodb引擎的时候页大小默认是16K ,查询如下

mysql> SHOW GLOBAL STATUS like 'Innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)
mysql>


假设 树高为3 , 这样的话,第一层即可以存储 16KB * 1024 / (8B + 6B) = 1170


同样的第二层也是1170 (第二层不是叶子结点,不存储数据)


第三层,存储数据,一般情况下一行数据的大小肯定不会超过1KB,那我们就按照1KB算吧


3层高的B+Tree , 存储BitInt可以存储 1170 * 1170 * 16 = 2千1 百万。。。。这效率还是可以的哈


想一想 如果是4层高的数 1170 * 1170 * 1170 * 16 = 250多亿数据。.。。。


当然了 都是估算, 如果换成其他类型的数据,每个表的行数据的大小都是相关的,这也就是我们通常说的 MySQL的表到千万级别就要分库分表的理论依据了。


我们看下B+Tree的插入和查找


20200719155209709.gif


20200719155924670.gif


Hash表


  • 对索引的key进行一次hash计算就可以定位出数据存储的位置
  • 很多时候Hash索引要比B+ 树索引更高效
  • 仅能满足 “=”,“IN”,不支持范围查询
  • hash冲突问题



20200719134046966.png


对索引字段进行hash以后, 还存储了数据对引得磁盘地址。


一般请款下,hash 比 b+tree的效率要高 ,但工作中绝大部分还是使用的B+Tree , 因为hash对范围查找不是很友好,还要全表扫描。


为啥B+Tree 支持范围查找?


我们知道B+Tree的叶子节点 有指针相连,从根节点找到对应的叶子节点后, 加上节点本身就是排好序的,所以范围查找就恨轻松了。


B-Tree 没有指针相连,所以要想范围查找,还得从根节点重新找,效率肯定比B+树低 。



搞定MySQL


https://artisan.blog.csdn.net/article/details/107431237?spm=1001.2014.3001.5502

相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
4月前
|
缓存 关系型数据库 MySQL
MySQL索引策略与查询性能调优实战
在实际应用中,需要根据具体的业务需求和查询模式,综合运用索引策略和查询性能调优方法,不断地测试和优化,以提高MySQL数据库的查询性能。
383 66
|
3月前
|
SQL 关系型数据库 MySQL
深入解析MySQL的EXPLAIN:指标详解与索引优化
MySQL 中的 `EXPLAIN` 语句用于分析和优化 SQL 查询,帮助你了解查询优化器的执行计划。本文详细介绍了 `EXPLAIN` 输出的各项指标,如 `id`、`select_type`、`table`、`type`、`key` 等,并提供了如何利用这些指标优化索引结构和 SQL 语句的具体方法。通过实战案例,展示了如何通过创建合适索引和调整查询语句来提升查询性能。
540 9
|
2月前
|
存储 关系型数据库 MySQL
MySQL索引学习笔记
本文深入探讨了MySQL数据库中慢查询分析的关键概念和技术手段。
300 80
|
26天前
|
缓存 算法 关系型数据库
MySQL底层概述—8.JOIN排序索引优化
本文主要介绍了MySQL中几种关键的优化技术和概念,包括Join算法原理、IN和EXISTS函数的使用场景、索引排序与额外排序(Using filesort)的区别及优化方法、以及单表和多表查询的索引优化策略。
MySQL底层概述—8.JOIN排序索引优化
|
1月前
|
SQL 存储 关系型数据库
MySQL原理简介—9.MySQL索引原理
本文详细介绍了MySQL索引的设计与使用原则,涵盖磁盘数据页的存储结构、页分裂机制、主键索引设计及查询过程、聚簇索引和二级索引的原理、B+树索引的维护、联合索引的使用规则、SQL排序和分组时如何利用索引、回表查询对性能的影响以及索引覆盖的概念。此外还讨论了索引设计的案例,包括如何处理where筛选和order by排序之间的冲突、低基数字段的处理方式、范围查询字段的位置安排,以及通过辅助索引来优化特定查询场景。总结了设计索引的原则,如尽量包含where、order by、group by中的字段,选择离散度高的字段作为索引,限制索引数量,并针对频繁查询的低基数字段进行特殊处理等。
MySQL原理简介—9.MySQL索引原理
|
27天前
|
存储 关系型数据库 MySQL
MySQL底层概述—6.索引原理
本文详细回顾了:索引原理、二叉查找树、平衡二叉树(AVL树)、红黑树、B-Tree、B+Tree、Hash索引、聚簇索引与非聚簇索引。
MySQL底层概述—6.索引原理
|
5月前
|
存储 关系型数据库 MySQL
阿里面试:为什么要索引?什么是MySQL索引?底层结构是什么?
尼恩是一位资深架构师,他在自己的读者交流群中分享了关于MySQL索引的重要知识点。索引是帮助MySQL高效获取数据的数据结构,主要作用包括显著提升查询速度、降低磁盘I/O次数、优化排序与分组操作以及提升复杂查询的性能。MySQL支持多种索引类型,如主键索引、唯一索引、普通索引、全文索引和空间数据索引。索引的底层数据结构主要是B+树,它能够有效支持范围查询和顺序遍历,同时保持高效的插入、删除和查找性能。尼恩还强调了索引的优缺点,并提供了多个面试题及其解答,帮助读者在面试中脱颖而出。相关资料可在公众号【技术自由圈】获取。
|
2月前
|
SQL 存储 关系型数据库
MySQL秘籍之索引与查询优化实战指南
最左前缀原则。不冗余原则。最大选择性原则。所谓前缀索引,说白了就是对文本的前几个字符建立索引(具体是几个字符在建立索引时去指定),比如以产品名称的前 10 位来建索引,这样建立起来的索引更小,查询效率更快!
127 22
 MySQL秘籍之索引与查询优化实战指南
|
2月前
|
存储 关系型数据库 MySQL
浅入浅出——MySQL索引
本文介绍了数据库索引的概念和各种索引结构,如哈希表、B+树、InnoDB引擎的索引运作原理等。还分享了覆盖索引、联合索引、最左前缀原则等优化技巧,以及如何避免索引误用,提高数据库性能。
|
2月前
|
存储 关系型数据库 MySQL
MySQL中为什么要使用索引合并(Index Merge)?
通过这些内容的详细介绍和实际案例分析,希望能帮助您深入理解索引合并及其在MySQL中的
184 10