MYSQL优化——B+树讲解
B-/B+树看 MySQL索引结构
B-树
B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树.它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.

B-树有如下特点:
所有键值分布在整颗树中;
任何一个关键字出现且只出现在一个结点中;
搜索有可能在非叶子结点结束;
在关键字全集内做一次查找,性能逼近二分查找;
B+ 树
B+树是B-树的变体,也是一种多路搜索树, 它与 B- 树的不同之处在于:
所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
为所有叶子结点增加了一个链指针
简化 B+树 如下图

为什么使用B-/B+ Tree
红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。MySQL 是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree,还跟磁盘存取原理有关。
局部性原理与磁盘预读
由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取,而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理:
当一个数据被用到时,其附近的数据也通常会马上被使用
程序运行期间所需要的数据通常比较集中
由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。
MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理**,每页大小默认为16K(这个值可以修改)**.linux 默认页大小为4K
B-/+Tree索引的性能分析
实际实现B-Tree还需要使用如下技巧:
每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个结点只需一次I/O。
假设 B-Tree 的高度为 h,B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。
而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。
B-Tree和B+Tree中为什么优先选择B+Tree
B+树更适合外部存储,由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B+树单次磁盘IO的信息量大于B-树,I/O效率更高。
Mysql是一种关系型数据库,区间访问是常见的一种情况,B+树叶节点增加的指向相邻节点的链指针,加强了区间访问性,可使用在范围区间查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找(between, <,>)。
B+Tree的定义
B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征:
有m个子树的节点包含有m个元素(B-Tree中是m-1)
根节点和分支节点中不保存数据,只用于索引,所有数据都保存在叶子节点中。
所有分支节点和根节点都同时存在于子节点中,在子节点元素中是最大或者最小的元素。
叶子节点会包含所有的关键字,以及指向数据记录的指针,并且叶子节点本身是根据关键字的大小从小到大顺序链接。

红点表示是指向卫星数据的指针,指针指向的是存放实际数据的磁盘页,卫星数据就是数据库中一条数据记录。
叶子节点中还有一个指向下一个叶子节点的next指针,所以叶子节点形成了一个有序的链表,方便遍历B+树。
B+树的优势
1.更加高效的单元素查找
B+树的查找元素3的过程:
第一次磁盘IO

第二次磁盘IO

第三次磁盘IO

这个过程看下来,貌似与B树的查询过程没有什么区别。但实际上有两点不一样:
a、首先B+树的中间节点不存储卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素,如此一来,相同数量的数据下,B+树就相对来说要更加矮胖些,磁盘IO的次数更少。
b、由于只有叶子节点才保存卫星数据,B+树每次查询都要到叶子节点;而B树每次查询则不一样,最好的情况是根节点,最坏的情况是叶子节点,没有B+树稳定。
2.叶子节点形成有顺链表,范围查找性能更优
B树范围查找3-8的过程
a、先查找3

b、再查找4、5、6、7、8,中间过程省略,直接到8的查找

这里查找的范围跨度越大,则磁盘IO的次数越多,性能越差。
B+树范围查找3-11的过程

先从上到下找到下限元素3,然后通过链表指针,依次遍历得到元素5/6/8/9/11;如此一来,就不用像B树那样一个个元素进行查找。
总结
1.单节点可以存储更多的元素,使得查询磁盘IO次数更少。
2.所有查询都要查找到叶子节点,查询性能稳定。
3.所有叶子节点形成有序链表,便于范围查询。
PS:在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。
相关文章:
MYSQL优化——B+树讲解
B-/B树看 MySQL索引结构 B-树 B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树.它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图. B-树有如下特点: 所有键值分布在整颗树中; 任何一…...
Rokid Jungle--Station pro
介绍和功能开发 YodaOS-Master操作系统:以交换计算为核心,实现单目SLAM空间交互,具有高精度、实时性和稳定性。发布UXR2.0SDK,为构建空间内容提供丰富的开发套件 多模态交互 算法原子化 多种开发工具协同 多生态支持 骁龙XR2…...
如何实现微服务
一、问题拆解 1.1、客户端如何访问这些服务 原来的Monolithic方式开发,所有的服务都是本地的,UI可以直接调用;现在按功能拆分成独立的服务,跑在独立的虚拟机上的Java进程了。客户端UI如何访问他的? 后台有N个服务&a…...
MySQL如何进行增量备份与恢复?
目录 一、MySQL 介绍 二、增量备份 三、备份恢复 一、MySQL 介绍 MySQL是一款开源的关系型数据库管理系统(RDBMS),它以其可靠性、灵活性和易于使用而备受赞誉。以下是关于MySQL数据库的介绍: MySQL是由瑞典公司MySQL AB开发&…...
微服务框架
一、目标 微服务框架通过组件化的方式提供微服务的开发部署、服务注册发现、服务治理与服务运维等能力。主流的微服务框架有开源的Spring Cloud、Dubbo与Service Mesh等,各大云厂商也基于开源的微服务框架,集成相关的云服务,实现企业级的微服…...
(matplotlib)如何让各个子图ax大小(宽度和高度)相等
文章目录 不相等相等 import matplotlib.pyplot as plt import numpy as np plt.rc(font,familyTimes New Roman) import matplotlib.gridspec as gridspec不相等 我用如下subplots代码画一行四个子图, fig,(ax1,ax2,ax3,ax4)plt.subplots(1,4,figsize(20,10),dpi…...
python http 上传文件
文章目录 改进质量 import random import requests from requests_toolbelt.multipart.encoder import MultipartEncoderurl http://ip:port/email data MultipartEncoder(fields{receiverId: xxxx163.com,mailSubject: mailSubject,content: content,fileList: (file_name, …...
IPO解读:Instacart曲折上市,业务模式如何持续“绚烂”?
商业世界的模式创新就像夜空中的烟火,而上升期的烟火总是绚烂的。 近日,美国商品配送业的鼻祖Instacart重新启动了IPO,并于9月11日,更新了招股书,将发行价定为每股26-28美元,计划融资6.16亿美元。值得一提…...
使用sql profile 稳定执行计划的案例
文章目录 1.缘起2.变慢的sql3.检查瓶颈4.解决办法4.1 SQLTXPLAIN 也称为 SQLT4.11 下载coe_xfr_sql_profile.sql4.12 使用方法4.13 执行coe_xfr_sql_profile.sql4.14 执行coe_xfr_sql_profile.sql产生的sql profile文件4.15 验证 4.2 SQL Tuning Advisor方式4.21 第一次Tuning …...
海南大学金秋悦读《乡村振兴战略下传统村落文化旅游设计》2023新学年许少辉八一新书
海南大学金秋悦读《乡村振兴战略下传统村落文化旅游设计》2023新学年许少辉八一新书...
[N0wayback 2023春节红包题] happyGame python反编译
这个反编译的比较深 一,从附件的图标看是python打包的exe文件,先用pyinstxtractor.py 解包 生成的文件在main.exe_extracted目录下,在这里边找到main 二,把main改名为pyc然后加上头 这个头从包里找一个带头的pyc文件ÿ…...
Redis 初识与入门
1. 什么是Redis Redis 是一种基于内存的数据库,对数据的读写操作都是在内存中完成,因此读写速度非常快,常用于缓存,消息队列、分布式锁等场景。 Redis 提供了多种数据类型来支持不同的业务场景,比如 String(字符串)、…...
【STM32】片上ADC的初步使用
基于stm32f103系列 基于《零死角玩转 STM32F103—指南者》 ADC简介 stm32f103上的ADC 数量:3 精度:12bit(4096) 通道:ADC1,ADC2均有16个通道,ADC3有8个 功能: 转换结束、注入转换结束和发生模拟看门狗事件时产生中断。 …...
esxi下实现ikuai相同的两个网卡,单独路由配置
1.首先安装配置双网卡。 因为esxi主机只接入了一根外网的网线,那么我们这两个网卡都是一样的网卡,具体的到系统里面进行设置。 2.开机安装系统 进入配置界面,此处就不用多说了,可以看我之前的文档,或者网上其他人的安…...
Windows环境下Elasticsearch相关软件安装
Windows环境下Elasticsearch相关软件安装 本文将介绍在 windows 环境下安装 Elasticsearch 相关的软件。 1、安装Elasticsearch 1.1 安装jdk ElasticSearch是基于lucence开发的,也就是运行需要java jdk支持,所以要先安装JAVA环境。 由于ElasticSear…...
配置Jedis连接池
一、概述 Jedis本身是线程不安全的,并且频繁的创建和销毁连接会有性能损耗,因此推荐使用Jedis连接池代替Jedis的直连方式。 二、创建连接池 public class JedisConnectionFactory {private static final JedisPool jedisPool;static {//配置连接池Jedi…...
Windows 12 开源网页版
前言 Windows 12 网页版是一个开源项目,使用标准网络技术,例如 Html、CSS 和 Javascript, 希望让用户在网络上预先体验 Windows 12 Windows 12 网页版download Windows 12 网页版 gitlab项目Windows 12 网页版 downloadWindows 12 demo参考downloaddemo test 开始菜单 …...
circleMidpoint(scrPt c, GLint r) 未定义的标识符,openGL第四章例子 ,画饼状图。
以下是完整的例子。在第四版 《计算机图形学 with openGL》第四章的例子中,竟然只调用了circleMidpoint(scrPt &c, GLint r) ,没有实现,我认为是系统方法,怎么找都找不到。openGL 官方文档也没找到,这不会是自定义…...
RKNN模型评估-性能评估和内存评估
基于Python的模型评估 perf_debug:进行性能评估时是否开启debug 模式。在 debug 模式下,可以获取到每一层的运行时间,否则只能获取模型运行的总时间。默认值为 False。 eval_mem: 是否进入内存评估模式。进入内存评估模式后,可以…...
window mysql-8.0.34 zip解压包安装
window系统上安装mysql8 解压版 下载压缩包 https://cdn.mysql.com//Downloads/MySQL-8.0/mysql-8.0.34-winx64.zip安装 用解压软件解压刚下载的mysql-8.0.34-winx64.zip 的文件至d:\devs路径下。 创建配置文件my.ini到路径d:\devs\mysql-8.0.34-winx64下 [mysqld] # 设置…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
游戏开发中常见的战斗数值英文缩写对照表
游戏开发中常见的战斗数值英文缩写对照表 基础属性(Basic Attributes) 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
Python的__call__ 方法
在 Python 中,__call__ 是一个特殊的魔术方法(magic method),它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时(例如 obj()),Python 会自动调用该对象的 __call__ 方法…...
