【面试】为什么Mysql用B+树做索引而不用B-树或红黑树

news/2024/11/20 13:43:11/

文章目录

  • 前言
  • 一、B+树只有叶节点存放数据,其余节点用来索引,而B-树是每个索引节点都会有Data域。
  • 二、那么Mysql如何衡量查询效率呢?
  • 三、B树相对于红黑树的区别

前言

原因如下:

  • B+树能显著减少IO次数,提高效率
  • B+树的查询效率更加稳定,因为数据放在叶子节点
  • B+树能提高范围查询的效率,因为叶子节点指向下一个叶子节点

一、B+树只有叶节点存放数据,其余节点用来索引,而B-树是每个索引节点都会有Data域。

所以从Mysql(Inoodb)的角度来看,B+树是用来充当索引的,一般来说索引非常大,尤其是关系性数据库这种数据量大的索引能达到亿级别,所以为了减少内存的占用,索引也会被存储在磁盘上。

二、那么Mysql如何衡量查询效率呢?

磁盘IO次数。 B-树/B+树 的特点就是每层节点数目非常多,层数很少,目的就是为了就少磁盘IO次数,但是B-树的每个节点都有data域(指针),这无疑增大了节点大小,说白了增加了磁盘IO次数(磁盘IO一次读出的数据量大小是固定的,单个数据变大,每次读出的就少,IO次数增多,一次IO多耗时),而B+树除了叶子节点其它节点并不存储数据,节点小,磁盘IO次数就少。这是优点之一。
另一个优点是: B+树所有的Data域在叶子节点,一般来说都会进行一个优化,就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据,这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的,而B树不支持这样的遍历操作。

三、B树相对于红黑树的区别

AVL 数和红黑树基本都是存储在内存中才会使用的数据结构。在大规模数据存储的时候,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。为什么会出现这样的情况,我们知道要获取磁盘上数据,必须先通过磁盘移动臂移动到数据所在的柱面,然后找到指定盘面,接着旋转盘面找到数据所在的磁道,最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上,树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,B树可以有多个子女,从几十到上千,可以降低树的高度。

数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。


http://www.ppmy.cn/news/103522.html

相关文章

Docker安装SQL Studio

前言 当前镜像是基于SQL Studio官网linux版本的安装包构建而成,镜像的tag和官方安装包的版本是对应的,例如:v1.6.0对应官方linux安装包的v1.6.0版本,目前只有v1.6.0版本的镜像。附上官网安装包下载地址 镜像说明 暴露端口 # 容…

1.Linux初识

在 Linux 系统中,sudo 是一个重要的命令,可以允许普通用户以管理员权限来运行特定的命令。通过 sudo 命令,普通用户可以暂时获取管理员权限,执行需要管理员身份才能执行的操作。 下面是一些关于 sudo 命令的用法: 以管…

Consul

1 下载 官网:https://releases.hashicorp.com/consul 根据自己情况选择自己所需的安装包下载即可。 2 安装 2.1 linux安装consul服务 ## 从官网下载最新版本的Consul服务 wget https://releases.hashicorp.com/consul/1.15.2/consul_1.15.2_linux_amd64.zip ##…

【SQL】PostgreSQL语句

最近使用PostgreSQL做了不少数据处理的工作,现将学习到的SQL语句整理一下。 创建数据库 CREATE DATABASE table_name; 创建表格 CREATE table_name IF NOT EXISTS {} (time timestamp, data int) 插入数据 insert into table_name values(%s, %s); 选择数据 …

AbandonedConnectionCleanupThread$ConnectionFinalizerPhantomReference内存溢出

网上查了查资料,根据自己情况在这里整理了一下,供大家学习和参考。 目录 1、现象 2、mysql-connector-java 源码分析 3、解决方法 3.1、配置disableAbandonedConnectionCleanup 3.2、暴力解决方式-----定时GC 4、什么是虚引用 5、关联对象真的被回…

dolphinscheduler3.1.7windows部署启动说明

简介 Apache DolphinScheduler是一个新一代分布式大数据工作流任务调度平台,致力于“解决大数据任务之间错综复杂的依赖关系,整个数据处理开箱即用”。它以 DAG(有向无环图) 的方式将任务连接起来,可实时监控任务的运行状态,同时…

二进制安装docker

二进制安装docker文档 建模部署 docker安装 下载docker 因rpm包安装依赖较多,选择二进制安装,下载地址如下 https://download.docker.com/linux/static/stable/x86_64/ 创建docker组 groupadd docker如果没有docker组,启动docker将会报…

java学习——java学习进度一String类1(学习记录——供回溯)

String 分割字符串 split( ) String s "1,2,3,4"; //未使用split分割前 System.out.println(s.length());//使用split分割后 String[] ssplit s.split(","); System.out.println(ssplit.length);split( , ) //两个参数都有的时候,第一个为用…