探究Mysql索引底层的bmore树的非叶子节点数据为什么小于4kb

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
云数据库 RDS PostgreSQL,高可用系列 2核4GB
简介: 探究Mysql索引底层的bmore树的非叶子节点数据为什么小于4kb

文章首发于我的个人博客,到个人博客体验更佳阅读哦

https://www.itqiankun.com/article/1564901799
为什么要设置B+树的非叶子节点数据小于4kb呢,我们往下一探究竟

原因如下所示

因为数据库里面的索引就是使用的bmore树,所以我们使用sql语句来讲解bmore树的产生:

比如有下面的两个常用的需求:

根据某个值查找数据,比如select * from user where id=1234;
根据区间值来查找某些数据,比如select * from user where id > 1234 and id < 2345。

为了让二叉查找树支持按照区间来查找数据,我们可以对它进行这样的改造:树中的节点并不存储数据本身,而是只是作为索引。除此之外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。就像下面这样:

2019073009030515

改造之后,如果我们要求某个区间的数据。我们只需要拿区间的起始值,在树中进行查找,当查找到某个叶子节点之后,我们再顺着链表往后遍历,直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据,就是符合区间值的所有数据。

20190730090334667

但是,我们要为几千万、上亿的数据构建索引,如果将索引存储在内存中,尽管内存访问的速度非常快,查询的效率非常高,但是,占用的内存会非常多。
比如,我们给一亿个数据构建二叉查找树索引,那索引中会包含大约1亿个节点,每个节点假设占用16个字节,那就需要大约1GB的内存空间。给一张表建立索引,我们需要1GB的内存空间。如果我们要给10张表建立索引,那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?

我们可以借助时间换空间的思路,把索引存储在硬盘中,而非内存中。我们都知道,硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的,而磁盘访问的速度是毫秒级别的。读取同样大小的数据,从磁盘中读取花费的时间,是从内存中读取所花费时间的上万倍,甚至几十万倍。所以我们通过减少访问磁盘索引的次数来减少这个访问磁盘的查询速度。怎么减少呢,就是让每个节点的读取(或者访问),都对应一次磁盘IO操作,这样树的高度就等于每次查询数据时磁盘IO操作的次数。

所以我们要把bmore树创建成m叉树,因为m值越大,树的高度也就越低,如图所示,给16个数据构建二叉树索引,树的高度是4,查找一个数据,就需要4个磁盘IO操作(如果根节点存储在内存中,其他结点存储在磁盘中),

20190730090354476

如果对16个数据构建五叉树索引,那树的高度只有2,查找一个数据,对应只需要2次磁盘操作。如下图所示

20190730090417259

如果m叉树中的m是100,那对一亿个数据构建索引,树的高度也只是3,最多只要3次磁盘IO就能获取到数据。磁盘IO变少了,查找数据的效率也就提高了。

但是m值也不是越大越好,因为不管是内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是4KB,这个值可以通过getconfig PAGE_SIZE命令查看)来读取的,一次只会读一页的数据。如果要读取的数据量超过一页的大小,就会触发多次IO操作。所以,我们在选择m大小的时候,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只需要一次磁盘IO操作。

那么什么叫做一个节点的大小呢,比如下面的数据,下面的篮筐的这个节点,它里面存储的数据,就是可以存储所有子节点里面的数据,但是不包含本节点的数据,本节点的数据在本节点的父节点里面存储着。什么意思呢,看下面的图片,下面的蓝框里面的30,65其实是在下面的蓝框的父节点红框节点里面存储着,然后下面的绿色框里面的30,65其实是在父节点蓝框节点里面存储着,同时蓝框节点还存储着下面的绿色框里面的所有字节点数据,所以只要保证红框节点,蓝框节点等节点的数据大小不超过4kb就可以了,那么如果超过了怎么办呢,超过4kb大小的节点都会被mysql处理掉,这里就要去看bmore树的添加和删除了

20190730090438908

能看到这里的同学,就帮忙点个赞吧,Thanks(・ω・)ノ

相关实践学习
每个IT人都想学的“Web应用上云经典架构”实战
本实验从Web应用上云这个最基本的、最普遍的需求出发,帮助IT从业者们通过“阿里云Web应用上云解决方案”,了解一个企业级Web应用上云的常见架构,了解如何构建一个高可用、可扩展的企业级应用架构。
MySQL数据库入门学习
本课程通过最流行的开源数据库MySQL带你了解数据库的世界。 &nbsp; 相关的阿里云产品:云数据库RDS MySQL 版 阿里云关系型数据库RDS(Relational Database Service)是一种稳定可靠、可弹性伸缩的在线数据库服务,提供容灾、备份、恢复、迁移等方面的全套解决方案,彻底解决数据库运维的烦恼。 了解产品详情:&nbsp;https://www.aliyun.com/product/rds/mysql&nbsp;
相关文章
|
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
|
2月前
|
SQL 人工智能 关系型数据库
如何实现MySQL百万级数据的查询?
本文探讨了在MySQL中对百万级数据进行排序分页查询的优化策略。面对五百万条数据,传统的浅分页和深分页查询效率较低,尤其深分页因偏移量大导致性能显著下降。通过为排序字段添加索引、使用联合索引、手动回表等方法,有效提升了查询速度。最终建议根据业务需求选择合适方案:浅分页可加单列索引,深分页推荐联合索引或子查询优化,同时结合前端传递最后一条数据ID的方式实现高效翻页。
139 0
|
1月前
|
存储 关系型数据库 MySQL
在CentOS 8.x上安装Percona Xtrabackup工具备份MySQL数据步骤。
以上就是在CentOS8.x上通过Perconaxtabbackup工具对Mysql进行高效率、高可靠性、无锁定影响地实现在线快速全量及增加式数据库资料保存与恢复流程。通过以上流程可以有效地将Mysql相关资料按需求完成定期或不定期地保存与灾难恢复需求。
144 10
|
2月前
|
存储 SQL 关系型数据库
MySQL 核心知识与索引优化全解析
本文系统梳理了 MySQL 的核心知识与索引优化策略。在基础概念部分,阐述了 char 与 varchar 在存储方式和性能上的差异,以及事务的 ACID 特性、并发事务问题及对应的隔离级别(MySQL 默认 REPEATABLE READ)。 索引基础部分,详解了 InnoDB 默认的 B+tree 索引结构(多路平衡树、叶子节点存数据、双向链表支持区间查询),区分了聚簇索引(数据与索引共存,唯一)和二级索引(数据与索引分离,多个),解释了回表查询的概念及优化方法,并分析了 B+tree 作为索引结构的优势(树高低、效率稳、支持区间查询)。 索引优化部分,列出了索引创建的六大原则
|
2月前
|
SQL 存储 缓存
MySQL 如何高效可靠处理持久化数据
本文详细解析了 MySQL 的 SQL 执行流程、crash-safe 机制及性能优化策略。内容涵盖连接器、分析器、优化器、执行器与存储引擎的工作原理,深入探讨 redolog 与 binlog 的两阶段提交机制,并分析日志策略、组提交、脏页刷盘等关键性能优化手段,帮助提升数据库稳定性与执行效率。
|
3月前
|
存储 关系型数据库 MySQL
MySQL覆盖索引解释
总之,覆盖索引就像是图书馆中那些使得搜索变得极为迅速和简单的工具,一旦正确使用,就会让你的数据库查询飞快而轻便。让数据检索就像是读者在图书目录中以最快速度找到所需信息一样简便。这样的效率和速度,让覆盖索引成为数据库优化师傅们手中的尚方宝剑,既能够提升性能,又能够保持系统的整洁高效。
117 9
|
26天前
|
安全 关系型数据库 MySQL
MySQL安全最佳实践:保护你的数据库
本文深入探讨了MySQL数据库的安全防护体系,涵盖认证安全、访问控制、网络安全、数据加密、审计监控、备份恢复、操作系统安全、应急响应等多个方面。通过具体配置示例,为企业提供了一套全面的安全实践方案,帮助强化数据库安全,防止数据泄露和未授权访问,保障企业数据资产安全。
|
11天前
|
缓存 关系型数据库 BI
使用MYSQL Report分析数据库性能(下)
使用MYSQL Report分析数据库性能
46 3
|
17天前
|
关系型数据库 MySQL 数据库
自建数据库如何迁移至RDS MySQL实例
数据库迁移是一项复杂且耗时的工程,需考虑数据安全、完整性及业务中断影响。使用阿里云数据传输服务DTS,可快速、平滑完成迁移任务,将应用停机时间降至分钟级。您还可通过全量备份自建数据库并恢复至RDS MySQL实例,实现间接迁移上云。

推荐镜像

更多