探究Mysql索引底层的bmore树的非叶子节点数据为什么小于4kb-阿里云开发者社区

开发者社区> 云栖社区直播> 正文

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

简介: 探究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(・ω・)ノ

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
PostgreSQL 双节点流复制如何同时保证可用性、可靠性(rpo,rto) - (半同步,自动降级方法实践)
PostgreSQL 双节点流复制如何同时保证可用性、可靠性(rpo,rto) - (半同步,自动降级方法实践)
517 0
C#使用OleDB操作ACCESS插入数据时提示:参数 @p_Contract 没有默认值
C#使用OleDB操作ACCESS插入数据时提示:参数 @p_Contract 没有默认值 OleDbParameter param = new OleDbParameter("" + dc.ColumnName, dc.DataType); 出现该问题的原因是创建了Parameter,却没有为Parameter.value指定一个值。
832 0
为什么不走索引, PostgreSQL
我明明创建了索引字段,为什么不选择索引扫描呢?我该注意什么,怎么解决
4195 0
redis分布式锁,无须设置有效期,自动检测hold锁的节点是否存活
基于redis实现分布式锁,无需设置有效期,自动检测hold锁的节点是否存活。
1939 0
线上MySQL数据库高负载的解决思路--再次论程序应用索引的重要性
前言:过去的笔记整理而得,未免丢失,发布个人博客。[2012年的资料笔记] 场景:数据库的负载飙升,CPU高达99%。查看进程。通过猜测推理,定位了一些select语句 363478427 | apps_read     | 192.
806 0
InnoDB索引概述,二分查找法,平衡二叉树
索引是应用程序设计和开发的一个重要方面。如果索引太多,应用的性能可能会受到影响;如果索引太少,对查询性能又会产生影响。要找到一个合适的平衡点,这对应用的性能至关重要。 如果知道数据的使用,从一开始就应该在需要处添加索引。
1060 0
Redis的安装及创建节点、部署群集
Redis简介 Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。
1044 0
13
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载