MySQL - 深入解析MySQL索引数据结构

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS PostgreSQL,高可用系列 2核4GB
云数据库 RDS MySQL,高可用系列 2核4GB
简介: MySQL - 深入解析MySQL索引数据结构

MySQL官方对索引定义:是存储引擎用于快速查找记录的一种数据结构。需要额外开辟空间和数据维护工作。

  • 索引是针对表来说的,不是针对数据库来说的(建表的sql语句中的index就是索引);
  • 索引是物理数据页存储,在数据文件中(InnoDB,ibd文件),利用数据页(page)存储;
  • 索引可以加快检索速度,但是同时也会降低增删改操作速度,索引维护需要代价。

先介绍一款可以帮助理解数据结构的网站:Data Structure Visualizations

1. 索引的数据结构演进

1.1 链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

有一张用户表,有id、username、password三个字段。现在对这个表进行查询。

假设上表中的数据存储在链表上,执行以下SQL我们可以发现影响查询速度的是这条数据在第几行

-- 查找1次
select * from user where password = 123;
-- 查找2次
select * from user where password = 234;
-- 查找3次
select * from user where password = 78;
-- 查找4次
select * from user where password = 567;
-- 查找5次
select * from user where password = 70;
-- 查找6次
select * from user where password = 379;

假设表中有1000万条数据,现在要查询第1000万条数据,这样就需要查找1000万次。顺序查找的问题是存储数据的结构是线性的,也就是说想要查询第2条数据,我需要知道第1条数据是什么。 大家可能会考虑到为什么不要数组,直接通过下标就可以查到数据,问题是数组是固定长度的,那么数组长度定义为多少合适呢?

1.2 二叉树

要解决链表的问题,我们可以用来解决,先来看一下二叉树:二叉树是一种特殊的树,每个节点最多有两个子节点,值从左到右依次递增。

二叉搜索树通过增加了一条搜索路径,提高了查询效率,查找的效率取决于树的深度(高度)

  • 问:为什么索引的数据结构不用二叉树?

因为当值依次递增插入时,二叉树会退化成链表,对加快查询没有任何作用。

时间复杂度(代码执行的次数):O(N)

1.3 红黑树(自平衡二叉查找树)

特点:

  1. 每个节点只能是红色或黑色;
  2. 跟节点必须是黑色;
  3. 红色的节点,它的叶节点只能是黑色;
  4. 从任一节点到其叶子节点的所有路径都包含相同数目的黑色节点。

为了解决二叉树变成链表的问题,出现了红黑树。当数据插入时,红黑树通过旋转和变色来达到平衡。这样就弥补了二叉树退化成链表的尴尬。 平衡后树的高度就变成了4层,相比于二叉树,效率更高。

  • 问:为什么索引的数据结构不用红黑树?

因为当值依次递增插入时树的高度会变得特别高。就例如上图查询0009只用4次,那查询1000万呢?树的高度大概是24,最坏的情况需要查找24次!查找24次是概念呢?,MySQL存储数据是存文件的,每次查找都需要读一次文件到内存,即最坏的查询情况需要读24次文件到内存,也就是24次IO操作,这是非常耗时的。

时间复杂度为:O(log2N)

1.4 B树(多路平衡搜索树)

特点:

  1. 索引值和data数据分布在整棵树结构中
  2. 每个节点可以存放多个索引值及对应的data数据
  3. 树节点中的多个索引值从左到右升序排列

B树的搜索:从根节点开始,对节点内的索引值序列采用二分法查找,如果命中就结束查找。没有命中会进入子节点重复查找过程,直到所对应的的节点指针为空,或已经是叶子节点了才结束。

因为树的高度问题,出现了B树(多路平衡搜索树),B树的思路是多叉树。只要分叉越多,那么每一层可以存放的元素就越多,树的层级自然而然就会降低。那么分叉肯定是越多越好,最多可以多到什么程度呢?这取决于MySQL一页可存储的数据量是多少,我们可以通过SQL命令来查询:

show global status like 'Innodb_page_size';

可以看到MySQL默认一页是16384字节,大约是16kb。假设一条数据1KB为例,一颗高度为3的B树,可以存储的数据个数是 16 * 16 * 16 = 4096

问:为什么索引的数据结构不用B树?

虽然B树相对于红黑树,树的高度降低了,但是随着数据量的增多,树的高度还是会变得很高,效率会变得特别低。而且对范围查找也不方便。

1.5 B+树

特点:

  1. 非叶子节点不存储data数据,只存储索引值,这样便于存储更多的索引值
  2. 叶子节点包含了所有的索引值和data数据
  3. 叶子节点用指针连接,提高区间的访问性能

相比B树,B+树进行范围查找时,只需要查找定位两个节点的索引值,然后利用叶子节点的指针进行遍历即可。而B树需要遍历范围内所有的节点和数据,显然B+Tree效率高。

1.6 哈希

Hash 底层实现是由 Hash 表来实现的,是根据键值 <key, value> 存储数据的结构。非常适合根据key查找 value 值,也就是单个 key 查询,或者说等值查询。其结构如下所示:

从上面结构可以看出,Hash索引可以方便的提供等值查询,但是对于范围查询就需要全表扫描了。Hash索引在MySQL 中Hash结构主要应用在Memory原生的Hash索引 、InnoDB 自适应哈希索引。

InnoDB提供的自适应哈希索引功能强大,接下来重点描述下InnoDB 自适应哈希索引。

InnoDB自适应哈希索引是为了提升查询效率,InnoDB存储引擎会监控表上各个索引页的查询,当InnoDB注意到某些索引值访问非常频繁时,会在内存中基于B+Tree索引再创建一个哈希索引,使得内存中的 B+Tree 索引具备哈希索引的功能,即能够快速定值访问频繁访问的索引页。

InnoDB自适应哈希索引:在使用Hash索引访问时,一次性查找就能定位数据,等值查询效率要优于B+Tree。

自适应哈希索引的建立使得InnoDB存储引擎能自动根据索引页访问的频率和模式自动地为某些热点页建立哈希索引来加速访问。另外InnoDB自适应哈希索引的功能,用户只能选择开启或关闭功能,无法进行人工干涉。

show engine innodb status \G; 
show variables like '%innodb_adaptive%';

2. 总结

  • 为什么mysql使用的是B+树

准确的表述:为什么mysql的InnoDB和MyISAM存储引擎的索引使用的是B+树

  1. hash表,等值查询是很快的,但是不满足常用的范围查找且相邻的两个值之间没有关系,而且hash比较消耗内存。
  2. 二叉树/平衡二叉树/红黑树等都是有且仅有2个分支,共性就是数据量大的时候树的深度变深,增加IO的次数。
  3. B树会在节点上存储数据,这样一页存放的key的数量就会减少,增加树的深度。
  4. B+树中非叶子节点去除了数据,这样就会页中key的数量,而且叶子节点之间是通过链表相连,有利于范围查找和分页。
相关实践学习
每个IT人都想学的“Web应用上云经典架构”实战
本实验从Web应用上云这个最基本的、最普遍的需求出发,帮助IT从业者们通过“阿里云Web应用上云解决方案”,了解一个企业级Web应用上云的常见架构,了解如何构建一个高可用、可扩展的企业级应用架构。
MySQL数据库入门学习
本课程通过最流行的开源数据库MySQL带你了解数据库的世界。 &nbsp; 相关的阿里云产品:云数据库RDS MySQL 版 阿里云关系型数据库RDS(Relational Database Service)是一种稳定可靠、可弹性伸缩的在线数据库服务,提供容灾、备份、恢复、迁移等方面的全套解决方案,彻底解决数据库运维的烦恼。 了解产品详情:&nbsp;https://www.aliyun.com/product/rds/mysql&nbsp;
相关文章
|
3月前
|
存储 关系型数据库 MySQL
MySQL数据库索引的数据结构?
MySQL中默认使用B+tree索引,它是一种多路平衡搜索树,具有树高较低、检索速度快的特点。所有数据存储在叶子节点,非叶子节点仅作索引,且叶子节点形成双向链表,便于区间查询。
100 4
|
2月前
|
存储 SQL 关系型数据库
MySQL中binlog、redolog与undolog的不同之处解析
每个都扮演回答回溯与错误修正机构角色: BinLog像历史记载员详细记载每件大大小小事件; RedoLog则像紧急救援队伍遇见突發情況追踪最后活动轨迹尽力补救; UndoLog就类似时间机器可倒带历史让一切归位原始样貌同时兼具平行宇宙观察能让多人同时看见各自期望看见历程而互不干扰.
152 9
|
3月前
|
存储 SQL 关系型数据库
MySQL 核心知识与索引优化全解析
本文系统梳理了 MySQL 的核心知识与索引优化策略。在基础概念部分,阐述了 char 与 varchar 在存储方式和性能上的差异,以及事务的 ACID 特性、并发事务问题及对应的隔离级别(MySQL 默认 REPEATABLE READ)。 索引基础部分,详解了 InnoDB 默认的 B+tree 索引结构(多路平衡树、叶子节点存数据、双向链表支持区间查询),区分了聚簇索引(数据与索引共存,唯一)和二级索引(数据与索引分离,多个),解释了回表查询的概念及优化方法,并分析了 B+tree 作为索引结构的优势(树高低、效率稳、支持区间查询)。 索引优化部分,列出了索引创建的六大原则
|
3月前
|
存储 SQL 关系型数据库
MySQL 核心知识与性能优化全解析
我整理的这份内容涵盖了 MySQL 诸多核心知识。包括查询语句的书写与执行顺序,多表查询的连接方式及内、外连接的区别。还讲了 CHAR 和 VARCHAR 的差异,索引的类型、底层结构、聚簇与非聚簇之分,以及回表查询、覆盖索引、左前缀原则和索引失效情形,还有建索引的取舍。对比了 MyISAM 和 InnoDB 存储引擎的不同,提及性能优化的多方面方法,以及超大分页处理、慢查询定位与分析等,最后提到了锁和分库分表可参考相关资料。
|
10月前
|
SQL 关系型数据库 MySQL
深入解析MySQL的EXPLAIN:指标详解与索引优化
MySQL 中的 `EXPLAIN` 语句用于分析和优化 SQL 查询,帮助你了解查询优化器的执行计划。本文详细介绍了 `EXPLAIN` 输出的各项指标,如 `id`、`select_type`、`table`、`type`、`key` 等,并提供了如何利用这些指标优化索引结构和 SQL 语句的具体方法。通过实战案例,展示了如何通过创建合适索引和调整查询语句来提升查询性能。
1881 10
|
4月前
|
关系型数据库 MySQL
MySQL字符串拼接方法全解析
本文介绍了四种常用的字符串处理函数及其用法。方法一:CONCAT,用于基础拼接,参数含NULL时返回NULL;方法二:CONCAT_WS,带分隔符拼接,自动忽略NULL值;方法三:GROUP_CONCAT,适用于分组拼接,支持去重、排序和自定义分隔符;方法四:算术运算符拼接,仅适用于数值类型,字符串会尝试转为数值处理。通过示例展示了各函数的特点与应用场景。
|
6月前
|
SQL 运维 关系型数据库
MySQL Binlog 日志查看方法及查看内容解析
本文介绍了 MySQL 的 Binlog(二进制日志)功能及其使用方法。Binlog 记录了数据库的所有数据变更操作,如 INSERT、UPDATE 和 DELETE,对数据恢复、主从复制和审计至关重要。文章详细说明了如何开启 Binlog 功能、查看当前日志文件及内容,并解析了常见的事件类型,包括 Format_desc、Query、Table_map、Write_rows、Update_rows 和 Delete_rows 等,帮助用户掌握数据库变化历史,提升维护和排障能力。
|
7月前
|
索引
【Flutter 开发必备】AzListView 组件全解析,打造丝滑索引列表!
在 Flutter 开发中,AzListView 是实现字母索引分类列表的理想选择。它支持 A-Z 快速跳转、悬浮分组标题、自定义 UI 和高效性能,适用于通讯录、城市选择等场景。本文将详细解析 AzListView 的核心参数和实战示例,助你轻松实现流畅的索引列表。
246 7
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
291 29
|
8月前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
507 27

热门文章

最新文章

推荐镜像

更多