深入解析MySQL索引结构:从数组到B+树的演变与优化
前言: 在数据库查询中,索引是一种关键的性能优化工具。然而,索引的失效可能导致查询效率大幅下降。为了更好地理解索引的工作原理及规避其失效,深入了解索引结构的演变过程尤为重要。
- MySQL 的索引数据结构从简单到复杂,主要经历了以下几个阶段:
1. 数组和链表:简单但低效的起步

- 特点:
- 数组:支持快速等值查找,但插入和删除效率低,时间复杂度为 O(n)。
- 链表:动态插入删除效率高,但查找需要线性扫描,效率低。
- 局限性:
- 不适合范围查询和频繁插入、删除的场景。
- 对于大规模数据,查找性能难以满足需求。
2. 二叉搜索树:提升效率但不稳定

-
特点:
- 左子树的节点值 < 根节点,右子树的节点值 > 根节点。
- 查找、插入和删除的时间复杂度为 O(log n)。
-
问题:
- 数据分布不均衡时,可能退化为链表,复杂度降为 O(n)。
- 不适合大规模数据的磁盘 I/O 场景。
3. 红黑树:平衡性与效率的折中

-
特点:
- 通过颜色属性(红/黑)及旋转操作保持平衡。
- 时间复杂度稳定为 O(log n),插入、删除效率较高。
-
局限性:
- 树的高度仍较大,对于磁盘 I/O 敏感的场景性能不足。
- 更适合内存索引,不适用于大规模数据存储。
4. B-树:为磁盘优化的多叉平衡树

-
特点:
- 节点可容纳多个关键字,减少树的高度。
- 支持等值查询和范围查询,插入和删除通过节点分裂保持平衡。
-
优点:
- 更少的树高意味着更少的磁盘 I/O,适合海量数据查询。
-
局限性:
- 叶子节点和非叶子节点都存储数据,占用更多空间。
- 查询路径不稳定,非叶子节点也可能存储数据,影响效率。
5. B+树:数据库索引的主流选择

-
改进点:
- 所有数据存储在叶子节点:非叶子节点只存储索引,减少节点大小,进一步降低树高。
- 叶子节点链表连接:支持高效范围查询,链表可直接顺序扫描。
-
优点:
- 查询性能稳定:所有查找操作都到达叶子节点,路径固定,效率更高。
- 适配范围查询:链表结构使范围查询更加高效。
- 磁盘 I/O 优化:单节点存储更多索引值,减少访问磁盘的次数。
-
缺点:
- 非叶子节点为冗余索引,占用空间稍多。
6. B+树 vs B-树:直观对比
| 特点 | B-树 | B+树 |
|---|---|---|
| 数据存储 | 数据存储在叶子节点和非叶子节点 | 数据存储仅在叶子节点 |
| 非叶子节点的功能 | 既存储索引也存储数据 | 仅存储索引信息 |
| 叶子节点的连接 | 无链表连接 | 叶子节点通过链表连接 |
| 查找效率 | 每次查找到达某个节点即可 | 必须查找到叶子节点(范围查询效率更高) |
| 空间占用 | 较少 | 较多 |
| 范围查询 | 需要在树中逐层遍历 | 叶子节点链表可以直接实现范围查询 |
7. 哈希:精准查询的快刀

-
优点:
- 时间复杂度 O(1),适合精确匹配查询。
- 实现简单,广泛用于 NoSQL 数据库和缓存系统(如 Redis、Memcached)。
-
局限性:
- 不支持范围查询,随机化存储导致无法顺序访问。
- 数据冲突处理(如链表法、开放地址法)会影响性能。
8. 为什么 MySQL 选用 B+树?
-
优化磁盘 I/O:
- 非叶子节点仅存储索引,减少节点大小,提高磁盘页的利用率。
- 树高降低,减少查询时的磁盘访问次数(通常仅需 3-4 次 I/O)。
-
查询性能稳定:
- 所有查找都需到叶子节点,路径长度固定,性能更均匀。
-
支持范围查询:
- 叶子节点链表连接,可顺序扫描,天然适配范围查询和分页。
-
维护成本低:
- 插入和删除操作只需局部调整,不影响整体结构。
-
数据库特性匹配:
- B+树索引性能适配高并发查询、大规模数据存储等场景。
结束语:MySQL 索引结构的演变从简单的数组、链表到红黑树、B-树,再到 B+树的最终选择,背后折射的是对性能、存储效率和功能适配的不断优化。这不仅仅是一种技术选择,更是一种工程智慧。
——如果觉得有帮助,😊点个赞支持一下吧!——
相关文章:
深入解析MySQL索引结构:从数组到B+树的演变与优化
前言: 在数据库查询中,索引是一种关键的性能优化工具。然而,索引的失效可能导致查询效率大幅下降。为了更好地理解索引的工作原理及规避其失效,深入了解索引结构的演变过程尤为重要。 MySQL 的索引数据结构从简单到复杂࿰…...
【疑难杂症】 HarmonyOS NEXT中Axios库的响应拦截器无法拦截424状态码怎么办?
今天在开发一个HarmonyOS NEXT的应用的时候,发现http接口如果返回的状态码是424时,我在axios中定义的拦截器失效了。直接走到了业务调用的catch中。 问题表现: 我的拦截器代码如下: 解决办法: 先说解决办法ÿ…...
jmeter并发用户逐步递增压测找性能拐点
jmeter并发用户逐步递增压测找性能拐点 目的: 使用逐层递增的并发压力进行测试,找到单功能的性能拐点(一般需要包含四组测试结果,拐点前一组,拐点一组,拐点后两组),统计响应时间、…...
【PostgreSQL使用】最新功能逻辑复制槽的failover,大数据下高可用再添利器
逻辑复制的failover 专栏内容: postgresql入门到进阶手写数据库toadb并发编程 个人主页:我的主页 管理社区:开源数据库 座右铭:天行健,君子以自强不息;地势坤,君子以厚德载物. ✅ ὒ…...
【开源免费】基于SpringBoot+Vue.JS租房管理系统(JAVA毕业设计)
本文项目编号 T 102 ,文末自助获取源码 \color{red}{T102,文末自助获取源码} T102,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...
Linux下Nvidia显卡GPU开启驱动持久化
GPU开启驱动持久化的原因 GPU 驱动一直处于加载状态, 减少运行程序时驱动加载的延迟。不开启该模式时,在程序每次调用完 GPU 后, GPU 驱动都会被卸载,下次调用时再重新加载, 驱动频繁卸载加载, GPU 频繁被…...
MS SQL Server 实战 排查多列之间的值是否重复
目录 需求 范例运行环境 数据样本设计 功能实现 上传EXCEL文件到数据库 SQL语句 小结 需求 在日常的应用中,排查列重复记录是经常遇到的一个问题,但某些需求下,需要我们排查一组列之间是否有重复值的情况。比如我们有一组题库数据&am…...
【玩转MacBook】Git安装
Git 官网也提到了MacBook 可以使用 Homebrew 安装 Git,所以在此使用 Homebrew 安装。 1、安装 Homebrew 执行安装脚本 在 Terminal 中执行如下命令: /bin/bash -c "$(curl -fsSL https://gitee.com/ineo6/homebrew-install/raw/master/install.…...
【优先算法】双指针 --(结合例题讲解解题思路)(C++)
今日鸡汤: “无人负我青云志,我自踏雪至山巅。” -徐霞客《青云志》 释义:没有人能够帮助我实现我的理想,即使面对再大的困难,我也要踏着积雪,一步步,到达山巅。 目录 1.快乐数 2.盛最多的…...
简述css中z-index的作用?如何用定位使用?
z-index是一个css属性,用于控制元素的堆叠顺序, 如何使用定位用index 1、position:relative; z-index; 相对于自己来定位的,可以根据top,bottom,right,leftÿ…...
Redis——数据淘汰策略
文章目录 1. 引入2. 讲解2.1 Redis 中的 8 种数据淘汰策略2.2 LRU 和 LFU 算法2.3 建议 3. 总结 1. 引入 在 Redis——数据过期策略 的“引入”部分讲解过,Redis 的数据存在内存中,而内存容量相对较小,不能将大量数据 无限期 地缓存。然而&a…...
机器学习之KNN算法预测数据和数据可视化
机器学习及KNN算法 目录 机器学习及KNN算法机器学习基本概念概念理解步骤为什么要学习机器学习需要准备的库 KNN算法概念算法导入常用距离公式算法优缺点优点:缺点︰ 数据可视化二维界面三维界面 KNeighborsClassifier 和KNeighborsRegressor理解查看KNeighborsRegr…...
前端node.js
一.什么是node.js 官网解释:Node.js 是一个开源的、跨平台的 JavaScript 运行时环境。 二.初步使用node.js 需要区分开的是node.js和javascript互通的只有console和定时器两个API. 三.Buffer Buffer 是一个类似于数组的对象,用于表示固定长度的字节序列。 Buffer…...
Excel基础知识
一:数组 一行或者一列数据称为一维数组,多行多列称为二维数组,数组支持算术运算(如加减乘除等)。 行:{1,2,3,4} 数组中的每个值用逗号分隔列:{1;2;3;4} 数组中的每个值用分号分隔行列…...
Spring Boot对访问密钥加密解密——RSA
场景 用户无需登录,仅仅根据给定的访问keyId和keySecret就可以访问接口。 keyId 等可以明文发送(不涉及机密),后端直接从请求头读取。keySecret 不可明文,需要加密后放在另一个请求头(或请求体࿰…...
Vue介绍
一、Vue框架简介 Vue.js是一个用于构建用户界面的渐进式JavaScript框架。它的核心库只关注视图层,易于上手,并且可以与其他库或现有项目进行整合。其特点包括响应式数据绑定、组件化开发和虚拟DOM等。 响应式数据绑定 Vue通过Object.defineProperty()方法来进行数据劫持。当…...
表单元素(标签)有哪些?
HTML 中的表单元素(标签)用于收集用户输入的数据,常见的有以下几种: 文本输入框 <input type"text">:用于单行文本输入,如用户名、密码等。可以通过设置maxlength属性限制输入字符数&…...
人工智能与云计算的结合:如何释放数据的无限潜力?
引言:数据时代的契机 在当今数字化社会,数据已成为推动经济与技术发展的核心资源,被誉为“21世纪的石油”。从个人消费行为到企业运营决策,再到城市管理与国家治理,每个环节都在生成和积累海量数据。然而,数…...
TCP Analysis Flags 之 TCP Out-Of-Order
前言 默认情况下,Wireshark 的 TCP 解析器会跟踪每个 TCP 会话的状态,并在检测到问题或潜在问题时提供额外的信息。在第一次打开捕获文件时,会对每个 TCP 数据包进行一次分析,数据包按照它们在数据包列表中出现的顺序进行处理。可…...
【MyBatis 核心工作机制】注解式开发与动态代理原理
有很多朋友可能已经在开发中熟练使用 MyBatis 或者刚开始学习 MyBatis,对于它的一些工作机制不太了解。“咦,怎么写几个注解,写几个配置文件,就能实现这些效果呢,好神奇呀!”当你看完这篇博客之后…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
