MySQL索引为什么选择B+树,而不是二叉树、红黑树、B树?

news/2024/5/18 22:03:23

12.1.为什么没有选择二叉树?


二叉树是一种二分查找树,有很好的查找性能,相当于二分查找。
二叉树的非叶子节值大于左边子节点、小于右边子节点。
原因:
但是当N比较大的时候,树的深度比较高。数据查询的时间主要依赖于磁盘IO的次数,二叉树深度越大,查找的次数越多,性能越差。
最坏的情况是退化成了链表。

12.2.为什么没有选择红黑树?


红黑树相比于二叉树,它做了进一步的优化,它是一种自适应的平衡树,会根据插入的节点数量以及节点信息,自动调整树结果来维持平衡。
原因:
红黑树查找结尾的元素的时候,树的高度越高,增删改查所需要的IO次数也越多,会严重影响性能(相当于做了全表扫描)。

12.3.为什么没有选择B树?


B树和红黑树相比,其单节点可容纳多个数量,就能在很大程度上改善其性能,使B树的树高远远小于红黑树的高度。
原因:
虽然对比之前的红黑树更矮,检索数据更快,由于叶子节点没有指针,但对于大范围查询的需求,依旧需要通过多次磁盘IO来操作。

12.4.为什么选择B+树


B+树是在B树的基础上进一步优化,一方面节点分为了叶结点和叶子节点两类,另一方面叶子节点之间存在单向链表指针。

(1)叶子节点上存在单向链表指针,便于范围查找;
(2)树的节点分为了叶结点和叶子节点。

MySQL底层真正的索引结构还对叶子节点之间的指针进行了优化,B+树的叶子节点的单向指针无法友好支持倒叙查询,因此MySQL针对单向指针优化成了双向指针,
也就是双向链表结构。即可以快速按正序进行范围查询,而可以快速按倒序进行范围操作。


http://www.mrgr.cn/p/43148762

相关文章

算法学习笔记Day8——回溯算法

本文解决几个问题: 回溯算法是什么?解决回溯算法相关的问题有什么技巧?回溯算法代码是否有规律可循? 一、介绍 1.回溯算法是什么? 回溯算法就是个多叉树的遍历问题,关键在于在前序和后序时间点做一些操作…

wps屏幕录制怎么用?分享使用方法!

数字化时代,屏幕录制已成为我们学习、工作和娱乐中不可或缺的一部分。无论是制作教学视频、分享游戏过程,还是录制网络会议,屏幕录制都能帮助我们轻松实现。WPS作为一款功能强大的办公软件,其屏幕录制功能也备受用户青睐。本文将详…

CentOS-7安装Mysql并允许其他主机登录

一、通用设置(分别在4台虚拟机设置) 1、配置主机名 hostnamectl set-hostname --static 主机名2、修改hosts文件 vim /etc/hosts 输入: 192.168.15.129 master 192.168.15.133 node1 192.168.15.134 node2 192.168.15.136 node33、 保持服…

day13 ts后端持久层框架(java转ts全栈/3R教室)

简介:如果说TS全栈后端开发最重要的两个框架,除了nestjs就是持久层框架了,这里主要看下Typeorm(java中常用的就是mybatis,springdatajpa,hebernite了) 先回顾下ORM的概念:ORM就是建…

C# GetField 方法应用实例

目录 关于 C# Type 类 GetField 方法应用 应用举例 心理CT设计题 类设计 DPCT类实现代码 小结 关于 C# Type 类 Type表示类型声明:类类型、接口类型、数组类型、值类型、枚举类型、类型参数、泛型类型定义,以及开放或封闭构造的泛型类型。调用 t…

二叉树的性质

性质一:二叉树的第i层上最多有2^(i-1) 个节点 性质二:深度为k的二叉树最多有2^(k)-1个节点 等比数列求和公式: 直接套进去就得到 2^(k)-1 (结点的度(Degree) :结点子树的个数。树的度: 树中结点的最大度数。度为k的树也称为k叉树) 性质三:叶…

Uptime Kuma 使用指南:一款简单易用的站点监控工具

我平时的工作会涉及到监控,而站点是一个很重要的监控项。项目上线后,我们通常会将站点监控配置到云平台上,以检测各站点的连通性。但随着项目不断增多,云平台上的配额就有点捉急了。针对这个情况,我们可以试试这个开源…

CSS画一条虚线,并且灵活设置虚线的宽度和虚线之间的间隔和虚线的颜色

CSS画一条虚线,并且灵活设置虚线的宽度和虚线之间的间隔和虚线的颜色。 先看效果图: 在CSS中,你可以使用border属性或者background属性来画一条虚线。以下是两种常见的方法: 方法一:使用border属性 你可以设置一个元素的border…

4.24日团队开发第五天

今天进行了晨会主要讨论了昨天完成情况,以及遇到的问题 同时针对完成度进行了分析,及时调整了进度

Linux 网络操作命令Telnet

Telnet 尽管 Telnet 已经逐渐被更安全的 SSH 协议所取代,但在某些特定场景下,如对旧系统的维护或教育目的,Telnet 仍然有其使用价值。本文将介绍如何在 Linux 系统中安装 Telnet 客户端,以及如何使用它进行远程登录。 用户使用 t…

MySQL 锁机制全面解析

目录 1. MySQL的锁类型1.1 全局锁1.2 表锁1.3 行锁1.4 共享锁(读锁)1.5 排它锁(写锁)1.6 死锁 2 乐观锁和悲观锁2.1 乐观锁2.2 悲观锁 3 意向锁4 间隙锁5 临键锁6 插入意向锁7. 事务隔离级别对锁的影响6.1 读未提交(Re…

账号安全及应用

一、账号安全控制 1.1系统账号清理 将用户设置为无法登陆 锁定账户 删除账户 设定账户密码,本质锁定 锁定配置文件-chattr: -a 让文件或目录仅供附加用途。只能追加 -i 不得任意更动文件或目录。 1.2密码安全控制 chage 1.3历史命令 history&am…

OceanBase数据库日常运维快速上手

这里为大家汇总了从租户创建、连接数据库,到数据库的备份、归档、资源配置调整等,在OceanBase数据库日常运维中的操作指南。 创建租户 方法一:通过OCP 创建 确认可分配资源 想要了解具体可分配的内存量,可以通过【资源管理】功…

Hive主要介绍

Hive介绍 hive是基于 Hadoop平台操作 HDFS 文件的插件工具 可以将结构化的数据文件映射为一张数据库表 可以将 HQL 语句转换为 MapReduce 程序 1.hive 是由驱动器组成,驱动器主要由4个组件组成(解析器、编译器、优化器、执行器) 2.hive本身不…

网络协议深度解析:SSL、 TLS、HTTP和 DNS(C/C++代码实现)

在数字化时代,网络协议构成了互联网通信的基石。SSL、TLS、HTTP和DNS是其中最关键的几种,它们确保了我们的数据安全传输、网页的正确显示以及域名的正常解析。 要理解这些协议,首先需要了解网络分层模型。SSL和TLS位于传输层之上&#xff0c…

数据可视化(四):Pandas技术的高级操作案例,豆瓣电影数据也能轻松分析!

Tips:"分享是快乐的源泉💧,在我的博客里,不仅有知识的海洋🌊,还有满满的正能量加持💪,快来和我一起分享这份快乐吧😊! 喜欢我的博客的话,记得…

如何在阿里云快速配置自动定时重启ECS云服务器?

背景 无论是电子商务、在线教育、游戏,还是流媒体等业务,服务器的稳定运行都是至关重要的。然而,在实际运行中,我们可能会遇到这样一些场景: 系统更新:一些操作系统或者软件的更新可能需要重启服务器才能…

buuctf-pwn-2.rip

先用checksec看一下保护情况红色表示没有保护,绿色则表示有相应的保护 关于每种保护会在之后的做题中遇到,也有相应的应对措施,这次就不过多深入 打开ida64分析附件发现高危函数gets,这个函数不会检查输入的长度 我们可以利用它修改函数的返回地址,从而执行后门函数找到后…

【draw.io的使用心得介绍】

🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者,CSDN实力新星,CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共…

条件生成对抗网络(cGAN)在AI去衣技术中的应用探索

随着深度学习技术的飞速发展,生成对抗网络(GAN)作为其中的一个重要分支,在图像生成、图像修复等领域展现出了强大的能力。其中,条件生成对抗网络(cGAN)通过引入条件变量来控制生成模型的输出&am…