面试题:MySQL为什么选择B+树作为索引结构


前言

在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明MySQL为什么选择B+树作为索引结构。


一、二叉查找树(BST):不平衡

二叉查找树(BST,Binary Search Tree),也叫二叉排序树,在二叉树的基础上需要满足:任意节点的左子树上所有节点值不大于根节点的值,任意节点的右子树上所有节点值不小于根节点的值。如下是一颗BST(图片来源)。

图片

当需要快速查找时,将数据存储在BST是一种常见的选择,因为此时查询时间取决于树高,平均时间复杂度是O(lgn)。然而BST可能长歪而变得不平衡,如下图所示(图片来源),此时BST退化为链表,时间复杂度退化为O(n)。
为了解决这个问题,引入了平衡二叉树。

图片

二、平衡二叉树(AVL):旋转耗时

AVL树是严格的平衡二叉树,所有节点的左右子树高度差不能超过1;AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。
AVL实现平衡的关键在于旋转操作:插入和删除可能破坏二叉树的平衡,此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时,最多只需要1次旋转(单旋转或双旋转);但是当删除数据时,会导致树失衡,AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡,旋转的量级为O(lgn)。
由于旋转的耗时,AVL树在删除数据时效率很低;在删除操作较多时,维护平衡所需的代价可能高于其带来的好处,因此AVL实际使用并不广泛。

三、红黑树:树太高

与AVL树相比,红黑树并不追求严格的平衡,而是大致的平衡:只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看,红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一,且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下(图片来源):
图片

与AVL树相比,红黑树的查询效率会有所下降,这是因为树的平衡性变差,高度更高。但红黑树的删除效率大大提高了,因为红黑树同时引入了颜色,当插入或删除数据时,只需要进行O(1)次数的旋转以及变色就能保证基本的平衡,不需要像AVL树进行O(lgn)次数的旋转。总的来说,红黑树的统计性能高于AVL。
因此,在实际应用中,AVL树的使用相对较少,而红黑树的使用非常广泛。例如,Java中的TreeMap使用红黑树存储排序键值对;Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时,使用链表,当冲突节点较多时,使用红黑树)。
对于数据在内存中的情况(如上述的TreeMap和HashMap),红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况(如MySQL等数据库),红黑树并不擅长,因为红黑树长得还是太高了。当数据在磁盘中时,磁盘IO会成为最大的性能瓶颈,设计的目标应该是尽量减少IO次数;而树的高度越高,增删改查所需要的IO次数也越多,会严重影响性能。

四、B树:为磁盘而生

B树也称B-树(其中-不是减号),是为磁盘等辅存设备设计的多路平衡查找树,与二叉树相比,B树的每个非叶节点可以有多个子树。 因此,当总节点数量相同时,B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”),磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order),对于一颗m阶B树,需要满足以下条件:

  • 每个节点最多包含 m 个子节点。
  • 如果根节点包含子节点,则至少包含 2 个子节点;除根节点外,每个非叶节点至少包含 m/2 个子节点。
  • 拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
  • 所有叶节点都在同一层中。

可以看出,B树的定义,主要是对非叶结点的子节点数量和记录数量的限制。
下图是一个3阶B树的例子(图片来源):

图片

B树的优势除了树高小,还有对访问局部性原理的利用。所谓局部性原理,是指当一个数据被使用时,其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点,当访问其中某个数据时,数据库会将该整个节点读到缓存中;当它临近的数据紧接着被访问时,可以直接在缓存中读取,无需进行磁盘IO;换句话说,B树的缓存命中率更高。
B树在数据库中有一些应用,如mongodb的索引使用了B树结构。但是在很多数据库应用中,使用了是B树的变种B+树。

五、B+树

B+树也是多路平衡查找树,其与B树的区别主要在于:

  • B树中每个节点(包括叶节点和非叶节点)都存储真实的数据,B+树中只有叶子节点存储真实的数据,非叶节点只存储键。在MySQL中,这里所说的真实数据,可能是行的全部数据(如Innodb的聚簇索引),也可能只是行的主键(如Innodb的辅助索引),或者是行所在的地址(如MyIsam的非聚簇索引)。
  • B树中一条记录只会出现一次,不会重复出现,而B+树的键则可能重复重现——一定会在叶节点出现,也可能在非叶节点重复出现。
  • B+树的叶节点之间通过双向链表链接。
  • B树中的非叶节点,记录数比子节点个数少1;而B+树中记录数与子节点个数相同。

由此,B+树与B树相比,有以下优势:

  • 更少的IO次数:B+树的非叶节点只包含键,而不包含真实数据,因此每个节点存储的记录个数比B数多很多(即阶m更大),因此B+树的高度更低,访问时所需要的IO次数更少。此外,由于每个节点存储的记录数更多,所以对访问局部性原理的利用更好,缓存命中率更高。
  • 更适于范围查询:在B树中进行范围查询时,首先找到要查找的下限,然后对B树进行中序遍历,直到找到查找的上限;而B+树的范围查询,只需要对链表进行遍历即可。
  • 更稳定的查询效率:B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点),而B+树的查询复杂度则稳定为树高,因为所有数据都在叶节点。

B+树也存在劣势:由于键会重复出现,因此会占用更多的空间。但是与带来的性能优势相比,空间劣势往往可以接受,因此B+树的在数据库中的使用比B树更加广泛。

六、感受B+树的威力

前面说到,B树/B+树与红黑树等二叉树相比,最大的优势在于树高更小。实际上,对于Innodb的B+索引来说,树的高度一般在2-4层。下面来进行一些具体的估算。
树的高度是由阶数决定的,阶数越大树越矮;而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page),页的大小为16KB,其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等),大多数空间都用来存储数据。

  • 对于非叶节点,记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录,则每条记录大约占用16字节;当索引是整型或较短的字符串时,这个假设是合理的。延伸一下,我们经常听到建议说索引列长度不应过大,原因就在这里:索引列太长,每个节点包含的记录数太少,会导致树太高,索引的效果会大打折扣,而且索引还会浪费更多的空间。
  • 对于叶节点,记录包含了索引的键和值(值可能是行的主键、一行完整数据等,具体见前文),数据量更大。这里假设每个叶节点页面存储100条记录(实际上,当索引为聚簇索引时,这个数字可能不足100;当索引为辅助索引时,这个数字可能远大于100;可以根据实际情况进行估算)。

对于一颗3层B+树,第一层(根节点)有1个页面,可以存储1000条记录;第二层有1000个页面,可以存储10001000条记录;第三层(叶节点)有10001000个页面,每个页面可以存储100条记录,因此可以存储10001000100条记录,即1亿条。而对于二叉树,存储1亿条记录则需要26层左右。


七、总结

最后,总结一下各种树解决的问题以及面临的新问题:

  1. 二叉查找树(BST):解决了排序的基本问题,但是由于无法保证平衡,可能退化为链表;
  2. 平衡二叉树(AVL):通过旋转解决了平衡的问题,但是旋转操作效率太低;
  3. 红黑树:通过舍弃严格的平衡和引入红黑节点,解决了AVL旋转效率过低的问题,但是在磁盘等场景下,树仍然太高,IO次数太多;
  4. B树:通过将二叉树改为多路平衡查找树,解决了树过高的问题;
  5. B+树:在B树的基础上,将非叶节点改造为不存储数据的纯索引节点,进一步降低了树的高度;此外将叶节点使用指针连接成链表,范围查询更加高效。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/212564.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一缕青丝寄相思

10年8月16日七夕节男孩向女孩表白,女孩不知道那天是七夕,也没有读懂男孩的爱,女孩在9月22日中秋,向男孩打开了心门,男孩却没有懂女孩的心思.13年后的一封问候邮件,一束女孩的长发和回不去的青春 洒满阳光的午后 转眼间看到你的笑脸 微笑着你对我说 遇上你认识我真好 你说得好莫…

数据结构与算法(Java) -单调队列单调栈题单

单调队列(灵神笔记) 239 滑动窗口最大值 239. 滑动窗口最大值 - 力扣(LeetCode) 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗…

找不到DNS地址的解决方案

找不到DNS地址的解决方案 第一种解决方案:刷新DNS缓存第二种解决方案: 配置Internet协议版本4(TCP/IPv4)配置IP地址配置DNS地址 如何查看本机IPv4地址、子网掩码与默认网关 第一种解决方案:刷新DNS缓存 WINR输入cmd回…

对比ProtoBuf和JSON的序列化和反序列化能力

1.序列化能力对比验证 在这里让我们分别使用PB与JSON的序列化与反序列化能力,对值完全相同的一份结构化数据进行不同次数的性能测试。 为了可读性,下面这一份文本使用JSON格式展示了需要被进行测试的结构化数据内容: {"age" : 20,"name…

2023年第十二届数学建模国际赛小美赛A题太阳黑子预测求解分析

2023年第十二届数学建模国际赛小美赛 A题 太阳黑子预测 原题再现: 太阳黑子是太阳光球上的一种现象,表现为比周围区域暗的暂时斑点。它们是由抑制对流的磁通量浓度引起的表面温度降低区域。太阳黑子出现在活跃区域内,通常成对出现&#xff…

Android自定义View实现八大行星绕太阳转动效果

最近尝试使用Android自定义View实现了一个8大行星绕太阳转动的自定义View效果,效果静态图如下所示: 还没来得及对该效果进行比较通用的包装,仅仅实现效果,有兴趣的可以继续扩展、美化、包装一下。 核心代码就一个类PlanetsView。 …

js中setinterval怎么用?怎么才能让setinterval停下来?

setinterval()是定时调用的函数,可按照指定的周期(以毫秒计)来调用函数或计算表达式。 setinterval()的作用是在播放动画的时,每隔一定时间就调用函数,方法或对象。 setInterval() 方法会不停地调用函数,…

Stm32F401RCT6内部FLASH数据擦除读写方法

Stm32F401RCT6内部FLASH数据的分区和F103的已经不一样了,读写格式化的方法网上内容不多,自己摸索了一下,基本可以,还存在一个问题 读取: uint16_t f[5];uint8_t tx[10];f[0] *(volatile uint16_t*)0x08020000; //ST…

tar文件覆盖漏洞 CVE-2007-4559

文章目录 前言原理例题 [NSSRound#7 Team]新的博客方法一 手搓文件名方法二 python脚本 前言 做到[NSSRound#6 Team]check(Revenge)时发现是tar文件覆盖,但是对概念和执行过程理解不够深就光光记住脚本,所以在做本题[NSSRound#7 Team]新的博客时打算重新…

一个网站,四种创建制作电子期刊的方法

想象一下,你正在走进一家神奇的商店,里面陈列着各种精美的杂志和期刊。但是,这些杂志和期刊并不是印刷品,而是可以直接在网站上制作和发布的电子期刊。 但是像这样能在网上发的电子期刊该怎么制作呢?不知道如何制作的小…

cc-product-waterfall仿天猫、淘宝购物车店铺商品列表组件

cc-product-waterfall仿天猫、淘宝购物车店铺商品列表组件 引言 在电商应用中,购物车体验的优化对于提升用户满意度和转化率至关重要。在本文中,我们将深入探讨如何使用cc-product-waterfall组件,结合uni-number-box和xg-widget,…

『Nginx安全访问控制』利用Nginx实现账号密码认证登录的最佳实践

📣读完这篇文章里你能收获到 如何创建用户账号和密码文件,并生成加密密码配置Nginx的认证模块,实现基于账号密码的登录验证 文章目录 一、创建账号密码文件1. 安装htpasswd工具1.1 CentOS1.2 Ubuntu 二、配置Nginx三、重启Nginx 在Web应用程…

Linux驱动开发学习笔记1《字符设备驱动开发》

目录 一、字符设备驱动简介 二、chrdevbase 字符设备驱动开发实验 1.创建驱动程序的目录 2.创建vscode工程 3.编写实验程序 4.编译驱动程序和测试APP代码 (1)加载驱动模块 (2)创建设备节点文件 (3&#xff…

【开源】前后端分离的在线考试系统,支持多种部署方式

在线考试系统 https://download.csdn.net/download/mo3408/88593116 在线考试系统是一种利用网络技术,实现在线出题、答题、阅卷、成绩查询等一系列考试活动的系统。它不受地理位置限制,可以实现远程考试,大大提高了考试的效率和便利性。此…

HBASE命令行查看中文字符

问题记录 中文显示的是编码字符不方便查看value\xE5\xB8\xB8\xE5\xAE\x89\xE5\xAE\x891修改前中文显示: 解决方法 1、列族 : 列名 : toString ’2、列族 : 列名 : c(org.apache.hadoop.hbase.util.Bytes).toString ’ scan karry:student,{COLUMNS > [info:…

C-语言每日刷题

目录 [蓝桥杯 2015 省 A] 饮料换购 题目描述 输入格式 输出格式 输入输出样例 # [蓝桥杯 2023 省 A] 平方差 题目描述 输入格式 输出格式 输入输出样例 说明/提示 【样例说明】 [NOIP2001 普及组] 数的计算 题目描述 输入格式 输出格式 输入输出样例 说明/提示 样例 1 解释 数据…

SQL自学通之简介

目录 一、SQL 简史 二、数据库简史 1、Dr. Codds 对关系型数据库系统的十二条规则 2、设计数据库的结构 3、数据库的前景 4、对于什么是客户机/服务器型电脑系统 BernardH.Boar的定义如下: 5、交互式语言 6、易于实现 7、SQL 总览 三、流行的 SQL 开发工具…

python初始化矩阵相关

做算法题经常需要初始化一个二维的dp数组 下面两种方法是最常用的 matrix [[0]*n]*n matrix [[0]*n for _ in range(n)]以前经常混用也没发现什么问题,直到昨天debug的时候发现第一种初始化之后对矩阵进行赋值时混乱的,比如matrix[0][1]2会导致所有行…

[Linux ] sed文本处理和免交互

一、sed 1.1 sed是什么 sed 是一种流编辑器(stream editor),用于对文本数据进行文本转换和处理。它通常被用于在命令行中执行文本编辑任务,可以对输入的文本进行搜索、替换、删除等操作,并将结果输出。sed 是一个非交…

Linux脚本awk命令

目录 一. awk命令简介 1. awk版本 2. awk与vim的区别 3. awk与sed的区别 4. awk工作原理 5. awk格式 6. awk常用选项 二. awk基础用法 1. awk基础用法 2. BEGIN和END语句块 3. 指定分隔符 4. 首尾关键字 三. awk内置变量 1. FS变量 2. OFS变量 3. RS变量 4. NF…