为什么mysql索引要使用B+树,而不是B树,红黑树

我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数(树的高度)尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

特别地:只有B-树和B+树,这里的B-树是叫B树,不是B减树。没有B减树的。

以下摘自【程序员小灰】

什么是B树

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

1、根结点至少有两个子女。 2、每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m 3、每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m 4、所有的叶子结点都位于同一层。5、每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

下面以3阶B树开始学习

这棵树中,重点看(2,6)节点。该节点有两个元素2和6,又有三个孩子1,(3,5),8。其中1小于元素2,(3,5)在(2,6)之间,8大于(3,5),正好符合上面所列的特征。

B树查询的流程:

比如上面的3阶B树查询数值5。

第1次IO:

第2次IO:

第3次IO:

第3次内存比较:

总结:每次深度加1就会进行一次磁盘IO的查询,将当前高度的数据加到内存中,再进行数值比较。从中可以看出相比大部分的查询时间是花费在磁盘IO的速度上,所以要想提高性能就是将树的高度足够低,IO次数足够少,这就是B树的优势。

B树添加的流程:

比如树里添加数值4 自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间

节点3,5已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点9是单元素节点,可以升级为两元素节点。于是拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个孩子。

从图中可以看到,为了插入一个元素,几乎全部的位置都变化了,这就是B树的自平衡(始终维持多路平衡)

B树删除的流程:

自顶向下查找元素11的节点位置。

删除11后,节点12只有一个孩子,不符合B树规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。(这个过程称为左旋)

B树应用

主要用于文件系统以及部分数据库索引(MongoDB) 而Mysql是用B+树的。

什么是B+树

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

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

从上图可以发现每一个父节点的元素都出现在子节点中,并且是子节点的最大(或最小)

从图中可以看到根节点元素8是字节点2,5,8的最大元素,也是叶子节点6,8的最大元素。根节点15是子节点11,15的最大元素,也是叶子节点13,15的最大元素。

B+树的最大元素始终位于根节点当中。所有叶子节点包含了全量元素信息,并且每一个叶子节点都带有指向 下一个节点指针,形成了一个有序链表。

B+树查询流程

单个查询:查询某个元素3

第一次磁盘IO:

第二次磁盘IO:

第三次磁盘IO:

这样看起来跟B树没有什么区别。但其实有两点是需要注意的:

1、B+树的中间节点没有卫星数据的。所以同样大小的磁盘页可以容纳更多的节点元素。(这就意味着B+会更加矮胖,查询的IO次数会更少)

B树的卫星数据

B+树的卫星数据

2、B树查找性能是不稳定的(如果要查找的数据分别在根节点和叶子节点,他们的性能就会不同)。但B+树的每一次都是稳定的,为啥呢,看下面的范围查询。

范围查询:查找到范围的下限(3)

B树的范围查询:

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

中序遍历到元素6:

中序遍历到元素8:

中序遍历到元素9:

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

B+树的范围查询:

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

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

通过链表指针,遍历到元素9, 11,遍历结束:

从上面的流程比较,可以得出以下B+树的优势:

1.单一节点存储更多的元素,使得查询的IO次数更少。

2.所有查询都要查找到叶子节点,查询性能稳定。

3.所有叶子节点形成有序链表,便于范围查询。

面试题

问题1:MySQL中存储索引用到的数据结构是B+树,B+树的查询时间跟树的高度有关,是log(n),如果用hash存储,那么查询时间是O(1)。既然hash比B+树更快,为什么mysql用B+树来存储索引呢?

答:一、从内存角度上说,数据库中的索引一般时在磁盘上,数据量大的情况可能无法一次性装入内存,B+树的设计可以允许数据分批加载。

二、从业务场景上说,如果只选择一个数据那确实是hash更快,但是数据库中经常会选中多条这时候由于B+树索引有序,并且又有链表相连,它的查询效率比hash就快很多了。

问题2:为什么不用红黑树或者二叉排序树?

答:树的查询时间跟树的高度有关,B+树是一棵多路搜索树可以降低树的高度,提高查找效率

问题3:既然增加树的路数可以降低树的高度,那么无限增加树的路数是不是可以有最优的查找效率?

答:这样会形成一个有序数组,文件系统和数据库的索引都是存在硬盘上的,并且如果数据量大的话,不一定能一次性加载到内存中。有序数组没法一次性加载进内存,这时候B+树的多路存储威力就出来了,可以每次加载B+树的一个结点,然后一步步往下找,

问题4:在内存中,红黑树比B树更优,但是涉及到磁盘操作B树就更优了,那么你能讲讲B+树吗?

B+树是在B树的基础上进行改造,它的数据都在叶子结点,同时叶子结点之间还加了指针形成链表。

下面是一个4路B+树,它的数据都在叶子结点,并且有链表相连。

问题5:为什么B+树要这样设计?

答:这个跟它的使用场景有关,B+树在数据库的索引中用得比较多,数据库中select数据,不一定只选一条,很多时候会选中多条,比如按照id进行排序后选100条。如果是多条的话,B+树需要做局部的中序遍历,可能要跨层访问。而B+树由于所有数据都在叶子结点不用跨层,同时由于有链表结构,只需要找到首尾,通过链表就能把所有数据取出来了。

比如选出7到19只需要在叶子结点中就能找到。

Image placeholder
Logan
未设置
  62人点赞

没有讨论,发表一下自己的看法吧

推荐文章
【Golang+MySQL】记一次 MySQL 数据库迁移(一)

【Golang+mysql】记一次mysql数据库迁移(一)文章地址:https://github.com/stayfoo/stayfoo-hub一、准备目标: 腾讯云CVM自建mysql数据迁移到腾

为什么你应当选择 PostgreSQL 而不是 Oracle?

本文转自| PostgreSQL中文社区 作者简介 Jan Karremans,EnterpriseDB的高级销售工程师。 译者简介 KevinZhan,深圳联友科技SA,目前负责公司部分核心系统应用

MySQL优化之覆盖索引的使用

查看测试表结构:mysql>showcreatetableim_message\G ***************************1.row**************************

使用BCC工具分析系统性能

系统管理员可以通过利用BCC(BPFCompilerCollection)库的工具来分析操作系统性能和获取操作系统信息。BCC介绍BCC工具全称BPFCompilerCollection(BCC),是

【MySQL实战45讲】索引部分整理

本文摘抄自极客时间【MySQL实战45讲】为什么要有索引?索引的作用是什么?索引的出现其实就是为了提高数据查询的效率,就像书的目录一样。一本书我们可以通过目录中快速的定位其中的某一个知识点;对于数据库

Oracle 之利用BBED修改数据块SCN—-没有备份数据文件的数据恢复

测试环境 OS:redhat6.6 oracle:12.1.0.2  BBED(OracleBlockBrowerandEDitorTool),用来直接查看和修改数据文件数据的一个工具,是Orac

MySQL 性能优化:8 种常见 SQL 错误用法!

1、LIMIT语句分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般DBA想到的办法是在type,name,create_time字段上加组合索引。这样条件排序都

Oracle/云MySQL/MsSQL“大迁移”真相及最优方案

最近一段时间碰到一些数据迁移的项目,如:Oracle迁移到MySQL,MsSQL迁移到MySQL,云MySQL迁移到本地MySQL。对于这方面做了系统的整理。包括:迁移方案的选择、如何跳出迁移遇到的坑

一条SQL语句在MySQL中如何执行的

前两天发了一条SQL慢的原因有哪些,在那篇文章我没有说到优化器之类的,我觉得如果配合一条SQL是如何执行的,会更好,所以特地找了一篇。来源:JavaGuide  |作者:木木匠本篇文章会分析一个sql

mysql 进行update时,要更新的字段中有单引号或者双引号导致不能批量生成sql的问题

前言将数据从一张表迁移到另外一张表的过程中,通过mysql的concat方法批量生成sql时遇到了一个问题,即进行UPDATE更新操作时如果原表中的字段中包含单引号'或者双引号",那么就会生成不正确的

为什么不建议在 MySQL 中使用 UTF-8?

最近我遇到了一个bug,我试着通过Rails在以“utf8”编码的MariaDB中保存一个UTF-8字符串,然后出现了一个离奇的错误:Incorrect string value: ‘😃 

为什么SQL正在击败NoSQL,这对未来的数据意味着什么

导读:经过多年的沉寂之后,今天的SQL正在复出。缘由如何?这对数据社区有什么影响?看看本文的分析。以下为译文。自从可以利用计算机做事以来,我们一直在收集的数据以指数级的速度在增长,因此对于数据存储、处

日均5亿查询量的京东订单中心,为什么舍MySQL用ES?

京东到家订单中心系统业务中,无论是外部商家的订单生产,或是内部上下游系统的依赖,订单查询的调用量都非常大,造成了订单数据读多写少的情况。我们把订单数据存储在MySQL中,但显然只通过DB来支撑大量的查

长城汽车张小斌:企业数字化不是选择,而是唯一的出路

长城汽车集团云计算总监张小斌20年IT行业经验。西安交通大学计算机专业毕业,中科院计算所硕士,曾在朗讯贝尔实验室、美国硅谷、HP、赛门铁克、Websense担任架构师、主任工程师、研发经理等职务,负责

基础信息:什么是 MySQL?

MySQL是一个开源的深受欢迎的关系型数据库管理系统(简称RDBMS)。目前排名第二,仅次于Oracle数据库。 MySQL可以免费下载,但是,还提供了几个付费版本,这些版本提供了附加功能。 顾名思义

MySQL 中 JSON 字段的使用技巧

mysql5.7.8之后开始原生支持json.在类似mongodb这种nosql数据库中,json存储数据是非常自然的,在mysql中合理的使用json,能够带来极大的便利 Json字段的使用场景 在

MySQL Batched Key Access (BKA)原理和设置使用方法举例

MySQL5.6版本开始增加了提高表join性能的算法:BatchedKeyAccess(BKA)的新特性。BKA算法原理:将外层循环的行/结果集存入joinbuffer,内存循环的每一行数据与整个b

mysql5.7 General tablespace使用说明

GeneraltablespaceGeneraltablespace 是一种共享的 innodb 表空间,有点类似 ibdata1 。可以在一个表空间数据文件下存储多张表,即使这些表来自不同的 sch

哪些行业需要使用高防服务器?

如今,随着互联网的普及,企业的业务开展离不开服务器,特别是针对热门互联网行业,如游戏、金融、电商、直播等领域,推荐使用高防服务器。因为这几个行业竞争非常激烈,容易遭到同行恶意攻击报复、敲诈勒索,是DD

为什么我使用了索引,查询还是慢?

经常有同学问我,我的一个SQL语句使用了索引,为什么还是会进入到慢查询之中呢?今天我们就从这个问题开始来聊一聊索引和慢查询。另外插入一个题外话,个人认为团队要合理的使用ORM,可以参考 ORM的权衡和

Ubuntu18.04 安装 MySQL 以及设置远程访问

安装MySQL sudoapt-getinstallmysql-server sudoaptisntallmysql-client sudoaptinstalllibmysqlclient-dev

基础信息:MySQL 特性

MySQL数据库的优缺点: 关系型数据库管理系统(RDBMS):MySQL是一个典型的关系型数据库管理系统。 易用:MySQL很容易上手。只要你掌握一些简单的SQL知识,就可以构建SQL语句与My

MySQL 数据库操作:创建和查看数据库

数据库是数据的集合。MySQL允许我们高效地存储和检索数据库中的数据。在MySQL中,我们可以使用CREATEDATABASE语句创建数据库。但是,如果数据库已经存在,则会引发错误。为了避免该错误,我

MySQL 表结构生成 Markdown 文档 | 工具篇

背景 在实施软件工程的时候,当要将某一版本归档时,需要汇总的文档要求还是比较高的、各类文档齐全,包括项目架构、项目安装、接口等文档,而数据库表结构说明文档亦属于其一。记得很早之前想找一个可以导出MyS

MySQL 数据库操作:删除数据库

使用MySQL的DROPDATABASE命令可以很容易的删除一个数据库。数据库删除的同时,所属的数据表将一起被删除。如果删除的数据库不存在,则会引发错误。为了避免错误的发生,可以在DROPDATABA