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] # 设置…...
Mysql判断某个数据库中是否包含某个表,与pymysql工具函数
查看某个数据库中的全部表: SELECT table_name FROM information_schema.tables WHERE table_schema 数据库名因此查看某个库中的某个表可以使用: SELECT table_name FROM information_schema.tables WHERE table_schema 数据库名 AND table_name 表…...
快速掌握正则表达式
文章目录 限定符 Qualifier第一个常用限定符 ?第二个常用限定符 *第三个常用限定符 或运算符字符类元字符 Meta-characters\d 数字字符\w 单词字符空白符 \s.任意字符^ $ 行首行尾 贪婪与懒惰匹配 Greedy vs Lazy Match实例 1 :RGB颜色匹配实例 2 &…...
git: ‘lfs‘ is not a git command unclear
首先可以尝试 git lfs install 是否可以,不可以后就看这个连接:https://stackoverflow.com/questions/48734119/git-lfs-is-not-a-git-command-unclear。 我的是ubuntu,所以: 保证这个前提: git-lfs requires git ve…...
代码随想录--哈希--两个数组的交集
题意:给定两个数组,编写一个函数来计算它们的交集。 说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。 import java.util.ArrayList; import java.util.HashMap; import java.util.List;public class SSS {public …...
基于腾讯文档进行应届生个人求职记录
1. 新建一个腾讯文档 电脑登录QQ,点击“腾讯文档”功能键。 2. 可以选择下载客户端,也可以直接进入网页版。(本人使用网页版) 3. 点击新建,选择在线表格。 4. 编辑表名,表内容。 5. 设置文档权限…...
计算机视觉实战项目(图像分类+目标检测+目标跟踪+姿态识别+车道线识别+车牌识别)
图像分类 教程博客_传送门链接:链接 在本教程中,您将学习如何使用迁移学习训练卷积神经网络以进行图像分类。您可以在 cs231n 上阅读有关迁移学习的更多信息。 本文主要目的是教会你如何自己搭建分类模型,耐心看完,相信会有很大收获。废话不…...
(18)线程的实例认识:线程的控制,暂停,继续,停止,线程相互控制,协作
话不多,但比较中肯,本文参照c# 线程暂停继续的实现方式_哔哩哔哩_bilibili 一、老方式 1、这是一个老的实现方式,基本不推荐,背后控制的原理需要了解。 界面:三个button一个textbox …...
c#动态保留小数位数的数值格式化方法实例----从小数点后非零数字保留两位进行四舍五入
c#动态保留小数位数的数值格式化方法实例----从小数点后非零数字保留两位进行四舍五入 功能介绍代码案例输出结果封装扩展方法控制台调用 其他方法地址 功能介绍 1. 输入的数字是整数,则直接返回整数部分的字符串表示。 2. 如果输入的数字是小数,则执行…...
大数据精准营销大数据平台应用场景有哪些,平台优势有哪些?
精准营销大数据平台应用场景有很多种,比如在银行领域,我通过相应的客户数据,也可以给客户推广一些银行业务。还可以运用于证券行业,除此之外还可以运用于保险或者信托行业,借助精准营销大数据平台可以进行主动营销。那…...
Pyspark案例综合(数据计算)
数据计算 map方法 map算子 map算子(成员方法)接受一个处理函数,可用lambda快速编写,对RDD内的元素一一处理,返回RDD对象 链式调用 对于返回值是新的RDD的算子,可以通过链式调用的方式多次调用算子 &q…...
wordpress 怎么添加即时联系窗口/网店运营流程步骤
原标题:听说,近视的人智商更高?近视的你还好吗如果你在学校里走路的时候碰到了熟人跟他打招呼却没有得到回应千万不要生气因为他可能是因为……………………没戴眼镜!!!近日,德国美因茨大学科学…...
日照建站外包/龙岗百度快速排名
用了FineUI有一段时间了,还是分享下我咋改的吧,没想的那么难,我也是从小白来的。 基础是要懂JQ和EXTJS,主要是要懂JQ和EXTJS能干啥,这里有两个网站http://www.w3school.com.cn/jquery/traversing_find.asphttp://extjs…...
php程序员网站开发建设/b2b网站平台有哪些
我写过一些开源项目,在开源方面有一些经验,最近开到了阮老师的微博,深有感触,现在一个开源项目涉及的东西确实挺多的,特别是对于新手来说非常不友好 最近我写了一个jslib-base,旨在从多方面快速帮大家搭建一…...
罗琳做的网站/口碑营销的优势有哪些
参考:https://blog.csdn.net/lifei08108006/article/details/50417485这个结论正确吗?看二条命令:数据是:select * FROM test.orders where ceate_record_time > 2019结果:为什么会出现 2018 的字符串?s…...
深圳疫情最新消息今天新增病例/电商中seo是什么意思
一、什么是EPEL?EPEL,即Extra Packages for Enterprise Linux(http://Fedoraproject.org/wiki/EPEL) 是由 Fedora 社区打造,为 RHEL 及衍生发行版如 CentOS、Scientific Linux 等提供高质量软件包的项目。在这里可以获得 RHEL 的高质量、高性…...
县政府门户网站建设情况/深圳seo培训
转载于:https://www.cnblogs.com/xenron/archive/2012/07/12/2587468.html...