首页 > 数据库 >MySQL - B+树

MySQL - B+树

时间:2023-02-10 21:25:30浏览次数:54  
标签:元素 查询 叶子 查找 MySQL 数据 节点

B+树

一个m阶的B+树具有如下几个特征:

  1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

首先来看看B+树的结构:

img

上面的这颗树中,得出结论:

  • 根节点元素8是子节点2,5,8 的最大元素,也是叶子节点6,8 的最大元素;
  • 根节点元素15是子节点11,15 的最大元素,也是叶子节点13,15 的最大元素;
  • 根节点的最大元素也就是整个B+树的最大元素,以后无论插入删除多少元素,始终要保持最大的元素在根节点当中。
  • 由于父节点的元素都出现在子节点中,因此所有的叶子节点包含了全部元素信息,并且每一个叶子节点都带有指向下一个节点的指针,形成了一个有序链表。

卫星数据:

指的的是索引元素所指向的数据记录,比如数据库中的某一行,在B-树中,无论中间节点还是叶子节点都带有卫星数据。

B-树中的卫星数据(Satellite Information):

img

B+树中的卫星数据(Satellite Information):

只有叶子节点带有卫星数据,其余中间节点仅仅是索引,没有任何的数据关联。

img

需要补充的是,在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。

B+ 树的查询

下面分别通过单行查询和范围查询来做分析:

单行查询:
比如我们要查找的元素是3:

B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点。

第一次磁盘IO:

img

第二次磁盘IO:

img

第三次磁盘IO:

img

B+树查询与B-数据对比:

  • B+树的中间节点没有卫星数据,所以同样大小的磁盘可以容纳更多的节点元素;
  • 在数据量相同的情况下,B+树的结构比B-树更加“矮胖”,因此查询的IO次数也更少;
  • B+树的查询必须最终查找到叶子节点,而B-树只要查找匹配的元素即可,无论匹配的元素处于中间节点还是叶子节点。
  • B-树的查找性能并不稳定(最好情况只查询根节点,最坏情况是查找叶子节点)。而B+树的每一次查找都是稳定的。

范围查询:

比如我们要查询3到11的范围数据:

B-树的范围查询过程:

自顶向下,查找到范围的下限(3):

img

中序遍历到元素6:

img

中序遍历到元素8:

img

中序遍历到元素9:

img

中序遍历到元素11,遍历结束:

img

B+树的范围查找过程

自顶向下,查找到范围的下限(3):

img

通过链表指针,遍历到元素6, 8:

img

img

总结:

B+树比B-树的优势三个:

  1. 单一节点存储更多的元素,使得查询的IO次数更少。
  2. 所有查询都要查找到叶子节点,查询性能稳定。
  3. 所有叶子节点形成有序链表,便于范围查询。

标签:元素,查询,叶子,查找,MySQL,数据,节点
From: https://www.cnblogs.com/amor2818/p/17110313.html

相关文章

  • MySQL--binlog2sql 安装及使用
    安装:依赖python3,请提前安装开源地址:https://github.com/danfengcao/binlog2sql$curlhttps://bootstrap.pypa.io/get-pip.py-oget-pip.py #下载安装脚本$sudop......
  • 记一次在Linux-Ubuntu上的mysql8安装
    踩坑网上的信息干货量太少了,都错的了解到centos系和ubuntu系的Linux还是有较大的区别的,命令都有不同,yum和apt,包管理器都不一样新开的Linux服务器跟裸奔一样,啥啥命令都没......
  • MySQL数据库系统部署使用
    推荐步骤: 在centos01上安装MySQL数据库服务,生成服务器配置文件,添加系统服务优化命令初始化MySQL,设置访问密码登录MySQL数据库 在centos01的MySQL服务器上创建数据库,数......
  • Mysql数据库备份恢复
    Mysql数据库备份恢复​推荐步骤:​使用mysqldump对数据库,数据库中表,一个数据库多个表,所有数据库进行备份,模拟数据丢失恢复备份的数据​配置mysql数据库开启二进制日志功能,配......
  • docker 下MySQL主从读写分离配置
    主从同步机制:同步基于耳机子机制,主服务器使用二进制来记录数据库的变动状况,从服务器通过读取和执行日志文件来保存主服务的数据一致首先要保障主从的版本一致或相近1......
  • MySQL 5.7.27 详细下载安装配置教程
    以下MySQL5.7.27详细下载安装配置教程【很早之前也记录过一篇MySQL8.0的安装配置过程,如果是8.0可参考下面的另一篇文章】MySQL的下载安装与Navicat配置(超详细)_乞力马扎......
  • Mysql 的三种 join方式
    mysql只有三种join方式参考:https://www.jianshu.com/p/76c90b03b7bdmysql只有三种join方式,但通过组合可以达到各种效果而已join就是innerjoinleftjoinrigh......
  • mysql 按照天,小时,分钟等分组排序
    按照季度统计SELECTCONCAT(DATE_FORMAT(create_time,'%Y'),'-',FLOOR((DATE_FORMAT(create_time,'%m')+2)/3),'季度')ASQUARTER,COUNT(1)AS总量FROM表WHEREcr......
  • MySQL视图、存储过程、函数、触发器、定时任务、流程控制总结
    视图的增删改查视图相当于一张只能读的表,不可以修改。当组成视图的表发生数据变化的时候,视图会相对应的进行改变。存储过程的练习创建存储过程:create[ifnotexi......
  • MySQLInstallerConsole.exe程序弹出窗口提示“MySQL Installer is running in Communi
    电脑运行中时不时弹出一个窗口,没反应过来就一下自动关闭了,下次再弹出,怎么回事?原来是MySQL的定时更新任务。 解决办法:这个是新版本MySQL服务自带的一个定时任务,每天......