通俗易懂介绍mysql索引为什么使用B+树?

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
云数据库 RDS PostgreSQL,高可用系列 2核4GB
简介: 通俗易懂告诉你mysql索引为什么使用B+树?回答这个问题之前先考虑两个问题: 1.mysql为什么使用索引? 2.支持索引的数据结构都有哪些?

通俗易懂告诉你mysql索引为什么使用B+树?回答这个问题之前先考虑两个问题:

   1.mysql为什么使用索引?

   2.支持索引的数据结构都有哪些?


1.mysql为什么使用索引?


   持久化存储的数据都是存储于磁盘,而从磁盘中进行读写数据都是IO操作,相对于内存数据读取,IO操作很容易出现性能瓶颈问题,为了提升数据io数据读取的性能问题,就有了索引的概念。官方介绍中索引是提升数据库读取性能的数据结构。对索引最通俗易懂、最直观的解释就是好比是新华字典中每个首字母,如果想从厚厚的一本字典中找到一个汉字,从第一页开始一直找到最后一页显然是很耗时的。但是先确定好要能找的字的第一个首字母,范围就一下子缩小了,所消耗的时间也减少了很多,这就是索引的好处。当然实际上mysql并不是按照这种实现的,不过有异曲同工之处。至于mysql中具体的索引是怎么起作用的继续往下看!


2.支持索引的数据结构都有哪些?


   常见的并且有助于提升查询速度的数据结构有一下几种:

哈希表

二叉树

红黑树

B树

B+树

依次说一下每种数据结构的优缺点。

哈希表

   哈希存储都不陌生,就是按照K-V键值对的方式进行读取,可以根据key直接获取value值。对于等值查询,哈希查询速度很快,但是对于范围查询的场景,哈希索引并不适合,也需要每条数据都进行查询然后判断是否符合范围,相当于全表扫描,所以不是合适的索引数据类型。

ca62e1818ae20f6acdf70473a087a50e_f697484cdbf849689f31e9b49c4d7255.png

二叉树

   结构特点:每个节点下面最多有两个子节点,左侧子节点大于父节点,右侧子节点小于父节点。简单来讲优点就是缩小查找的范围,减少读取的次数。下面模拟插入指定数据:15 10 17 12 9 21 16,存储之后的数据结构为:

8c2869a616eaf8c0358fd6e3fe4290ba_99773625992b4cb880e72bbd76b1be42.png

二叉树动态插入展示

比如说查找12,只需要对比两次就可以找到12.查找速率确实能提升。但mysql为什么没有使用二叉树,原因是可能会出现“链表”数据结构,此种结构相当于“全表扫描”。比如说需要存储连续的数据:

de2f3f3e3118e2e360b802971215eda1_4403009fe2ef405e85c8d3003c0fb6a4.png

红黑树

   红黑树实际上也算是二叉树的一种,也有人称之为平衡二叉树,主要的优点是解决普通二叉树可能存在的单链表结构。存储相同数据的存储图如下:

8abc4086928f062bda0f55c02ef2811d_a71b520e2c234e7c9783acc6aaf8c61a.png

可以看出数据存储的位置基本上一致。主要看下对于连续数据存储的情况:

fbbac17e8095f58275397ce544b345ed_2c96cd96d62e4ca78e826feee913ed0e.png

红黑树动态插入展示

可以发现红黑树解决了二叉树存储可能出现的链表结构。但是mysql为什么索引不用红黑树?原因在于红黑树的问题在树的高度问题,数据量增多,树的高度就会增加,每层树的读取时就相当于一次IO操作,显然也不是最好的数据结构。继续往下看。

B树

   可以说B树的出现主要是解决红黑树中树高度过高导致磁盘IO读取次数过高的问题。首先说一下mysql中磁盘最小的存储单位为页,存储大小为16Kb,相当于人民币的分。页中存储多个节点,

每个节点由三部分组成:索引字段值、字段值所对应的行详细数据、行数据所在的磁盘地址。数据结构图如下:

bf3e18ebb2a7e2c4a70bd870de2be3e7_3043a72be3894bd1b65a10470fc1124f.png

B+树

   mysql中使用存储引擎是B+数,原因是B+树相对于B树,非叶子节点不存储行详细数据,仅储存索引字段值以及所在磁盘的地址值,会存在冗余重复的索引字段值,优点在于每页存储单位中能存储更多的索引信息,形成的B数会更加矮小更胖。参考图如下:

7603efe67a9a5ea9c9f3945ce619d845_b24d81f50b504b3a977e50fe6a492680.png

逻辑图如下:

fe1f3d452ecd5d497a95b1860735cf59_2236e6d761b2442fb8bbcf242fd90f3f.png


假设主键为bigint类型,主键bigint占用8个字节,指针地址占用6个字节,8+6=14,所以我们可以得出,一页能存放的指针个数为16k/(8+6)约等于1170。单条行记录大小约为1k,那么一个page能存储的行记录数为16k/1k=16,所以树高3层为1170117016约等于2190w数据,完美解决树高导致IO读取次数过高问题。

说明:文章中动态页面为国外某学校网站地址,支持多种数据结构演示,地址:https://www.cs.usfca.edu/~galles/visualization/,关于索引添加之后的数据摆放顺序可以参考网站演示.


相关实践学习
每个IT人都想学的“Web应用上云经典架构”实战
本实验从Web应用上云这个最基本的、最普遍的需求出发,帮助IT从业者们通过“阿里云Web应用上云解决方案”,了解一个企业级Web应用上云的常见架构,了解如何构建一个高可用、可扩展的企业级应用架构。
MySQL数据库入门学习
本课程通过最流行的开源数据库MySQL带你了解数据库的世界。   相关的阿里云产品:云数据库RDS MySQL 版 阿里云关系型数据库RDS(Relational Database Service)是一种稳定可靠、可弹性伸缩的在线数据库服务,提供容灾、备份、恢复、迁移等方面的全套解决方案,彻底解决数据库运维的烦恼。 了解产品详情: https://www.aliyun.com/product/rds/mysql 
相关文章
|
2月前
|
存储 SQL 关系型数据库
mysql底层原理:索引、慢查询、 sql优化、事务、隔离级别、MVCC、redolog、undolog(图解+秒懂+史上最全)
mysql底层原理:索引、慢查询、 sql优化、事务、隔离级别、MVCC、redolog、undolog(图解+秒懂+史上最全)
mysql底层原理:索引、慢查询、 sql优化、事务、隔离级别、MVCC、redolog、undolog(图解+秒懂+史上最全)
|
2月前
|
存储 关系型数据库 MySQL
MySQL数据库索引的数据结构?
MySQL中默认使用B+tree索引,它是一种多路平衡搜索树,具有树高较低、检索速度快的特点。所有数据存储在叶子节点,非叶子节点仅作索引,且叶子节点形成双向链表,便于区间查询。
98 4
|
4月前
|
存储 关系型数据库 MySQL
阿里面试:MySQL 一个表最多 加几个索引? 6个?64个?还是多少?
阿里面试:MySQL 一个表最多 加几个索引? 6个?64个?还是多少?
阿里面试:MySQL 一个表最多 加几个索引? 6个?64个?还是多少?
|
6月前
|
关系型数据库 MySQL 数据库
Mysql的索引
MYSQL索引主要有 : 单列索引 , 组合索引和空间索引 , 用的比较多的就是单列索引和组合索引 , 空间索引我这边没有用到过 单列索引 : 在MYSQL数据库表的某一列上面创建的索引叫单列索引 , 单列索引又分为 ● 普通索引:MySQL中基本索引类型,没有什么限制,允许在定义索引的列中插入重复值和空值,纯粹为了查询数据更快一点。 ● 唯一索引:索引列中的值必须是唯一的,但是允许为空值 ● 主键索引:是一种特殊的唯一索引,不允许有空值 ● 全文索引: 只有在MyISAM引擎、InnoDB(5.6以后)上才能使⽤用,而且只能在CHAR,VARCHAR,TEXT类型字段上使⽤用全⽂文索引。
|
2月前
|
存储 SQL 关系型数据库
MySQL 核心知识与索引优化全解析
本文系统梳理了 MySQL 的核心知识与索引优化策略。在基础概念部分,阐述了 char 与 varchar 在存储方式和性能上的差异,以及事务的 ACID 特性、并发事务问题及对应的隔离级别(MySQL 默认 REPEATABLE READ)。 索引基础部分,详解了 InnoDB 默认的 B+tree 索引结构(多路平衡树、叶子节点存数据、双向链表支持区间查询),区分了聚簇索引(数据与索引共存,唯一)和二级索引(数据与索引分离,多个),解释了回表查询的概念及优化方法,并分析了 B+tree 作为索引结构的优势(树高低、效率稳、支持区间查询)。 索引优化部分,列出了索引创建的六大原则
|
3月前
|
存储 关系型数据库 MySQL
MySQL覆盖索引解释
总之,覆盖索引就像是图书馆中那些使得搜索变得极为迅速和简单的工具,一旦正确使用,就会让你的数据库查询飞快而轻便。让数据检索就像是读者在图书目录中以最快速度找到所需信息一样简便。这样的效率和速度,让覆盖索引成为数据库优化师傅们手中的尚方宝剑,既能够提升性能,又能够保持系统的整洁高效。
120 9
|
4月前
|
机器学习/深度学习 关系型数据库 MySQL
对比MySQL全文索引与常规索引的互异性
现在,你或许明白了这两种索引的差异,但任何技术决策都不应仅仅基于理论之上。你可以创建你的数据库实验环境,尝试不同类型的索引,看看它们如何影响性能,感受它们真实的力量。只有这样,你才能熟悉它们,掌握什么时候使用全文索引,什么时候使用常规索引,以适应复杂多变的业务需求。
107 12
|
8月前
|
存储 关系型数据库 MySQL
MySQL索引学习笔记
本文深入探讨了MySQL数据库中慢查询分析的关键概念和技术手段。
605 81
|
5月前
|
SQL 存储 关系型数据库
MySQL选错索引了怎么办?
本文探讨了MySQL中因索引选择不当导致查询性能下降的问题。通过创建包含10万行数据的表并插入数据,分析了一条简单SQL语句在不同场景下的执行情况。实验表明,当数据频繁更新时,MySQL可能因统计信息不准确而选错索引,导致全表扫描。文章深入解析了优化器判断扫描行数的机制,指出基数统计误差是主要原因,并提供了通过`analyze table`重新统计索引信息的解决方法。
137 3
|
6月前
|
自然语言处理 关系型数据库 MySQL
MySQL索引有哪些类型?
● 普通索引:最基本的索引,没有任何限制。 ● 唯一索引:索引列的值必须唯一,但可以有空值。可以创建组合索引,则列值的组合必须唯一。 ● 主键索引:是特殊的唯一索引,不可以有空值,且表中只存在一个该值。 ● 组合索引:多列值组成一个索引,用于组合搜索,效率高于索引合并。 ● 全文索引:对文本的内容进行分词,进行搜索。

推荐镜像

更多