深入解析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,对于它的一些工作机制不太了解。“咦,怎么写几个注解,写几个配置文件,就能实现这些效果呢,好神奇呀!”当你看完这篇博客之后…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
