当前位置: 首页 > news >正文

深入解析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+树的演变与优化

前言&#xff1a; 在数据库查询中&#xff0c;索引是一种关键的性能优化工具。然而&#xff0c;索引的失效可能导致查询效率大幅下降。为了更好地理解索引的工作原理及规避其失效&#xff0c;深入了解索引结构的演变过程尤为重要。 MySQL 的索引数据结构从简单到复杂&#xff0…...

【玩转MacBook】JDK安装

下载 JDK 8 官网&#xff1a;https://www.oracle.com/cn/java/technologies/downloads/archive/ 找到 JDK 8 选择&#xff1a; 安装 JDK 双击 .dmg 文件&#xff1a; 继续双击&#xff1a; “继续” “继续” 走到这里&#xff0c;我发现只能选择这个“为这台电脑上的所有…...

word无法创建工作文件,检查临时环境变量。

word无法创建工作文件&#xff0c;检查临时环境变量。 word preview版本&#xff0c;关联打开文件出现报错。word无法创建工作文件&#xff0c;检查临时环境变量。 打开注册表&#xff0c;删除键 Word Preview: HKCR\CLSID{84F66100-FF7C-4fb4-B0C0-02CD7FB668FE} PowerPoint …...

威联通NAS部署openwrt软路由保姆级教程附镜像文件

创作立场&#xff1a;原创不易&#xff0c;拒绝搬运~ hello 大家好&#xff0c;我是你们的老伙伴&#xff0c;稳重的大王~ 本期教程为大家分享&#xff0c;怎么在NAS里面部署软路由&#xff0c;下面是软路由的镜像文件&#xff0c;有两个版本&#xff0c;400M的是定制版~ Sh…...

MySQL共享锁,排他锁

在 MySQL 中&#xff0c;共享锁&#xff08;S 锁&#xff09; 和 排他锁&#xff08;X 锁&#xff09; 是两种主要的锁机制&#xff0c;用于处理事务的并发控制。它们的作用和行为如下&#xff1a; 1. 共享锁 (S 锁) 定义&#xff1a; 共享锁允许事务对某一行数据进行读取&am…...

2. FPGA基础了解--全局网络

前言 引入扇出的概念介绍FPGA中的全局网络为后续时序优化埋下伏笔 扇出 在FPGA设计中扇出是一个重要的概念&#xff0c;所谓的扇出就是一个控制信号所能控制的数据信号的总个数&#xff0c;比如ctrl信号的扇出就是16 reg ctrl 0; reg [15:0] out 0; always (posedge c…...

[c++进阶(三)]单例模式及特殊类的设计

1.前言 在实际场景中,总会遇见一些特殊情况,比如设计一个类,只能在堆上开辟空间, 或者是设计一个类只能实例化一个对象。那么我们应该如何编写代码呢&#xff1f;本篇将会详细的介绍 本章重点&#xff1a; 本篇文章着重讲解如何设计一些特殊 的类,包括不能被拷贝,只能在栈/堆上…...

js版本之ES6特性简述【let和const、数组、函数、集合、Symbol】(四)

目录 let [块级作用域] 和const简述 Array.from Array.of Array.prototype中新增的方法 for...of 函数参数调整 集合类型 Map Set WeakMap WeakSet Set WeakSet Map WeakMap Symbol 类型 let [块级作用域] 和const简述 ES6 新增了let命令&#xff0c;用来声明变…...

重温设计模式--4、组合模式

文章目录 1 、组合模式&#xff08;Composite Pattern&#xff09;概述2. 组合模式的结构3. C 代码示例4. C示例代码25 .应用场景 1 、组合模式&#xff08;Composite Pattern&#xff09;概述 定义&#xff1a;组合模式是一种结构型设计模式&#xff0c;它允许你将对象组合成…...

解决Ubuntu下无法装载 Windows D盘的问题

电脑安装了 Windows 和 Ubuntu 24.04 后&#xff0c;在Ubuntu系统上装载 D盘&#xff0c;发现无法装载错误如下&#xff1a; Error mounting /dev/nvme0n1p4 at /media/jackeysong/Data: wrong fs type, bad option, bad superblock on /dev/nvme0n1p4, missing codepage or h…...

详细介绍如何使用rapidjson读取json文件

本文主要详细介绍如何使用rapidjson库来实现.json文件的读取&#xff0c;分为相关基础介绍、结合简单示例进行基础介绍、结合复杂示例进行详细的函数实现介绍等三部分。 一、相关基础 1、Json文件中的{} 和 [] 在 JSON 文件中&#xff0c;{} 和 [] 分别表示不同的数据结构&…...

Mybatis 如何复用 SQL

比如你的Mapper是这样写的&#xff1a; 但这个接口是没有分页的&#xff0c;你还想再写一个有分页的查询接口&#xff0c;两个接口SQL一模一样&#xff0c;只是多了分页特性。你可以直接重载一个方法&#xff0c;增加分页参数&#xff0c;即可复用该SQL。如下&#xff1a;...

使用 Python 操作 MySQL 数据库的实用工具类:MySQLHandler

操作数据库是非常常见的需求&#xff0c;使用 Python 和 pymysql 库封装一个通用的 MySQL 数据库操作工具类&#xff0c;并通过示例演示如何使用这个工具类高效地管理数据库。 工具类的核心代码解析 MySQLHandler 类简介 MySQLHandler 是一个 Python 类&#xff0c;用于简化…...

C++ 内存管理:原理、技巧与实战

目录 第一章:C++ 内存管理基础 1.1 C++ 内存布局剖析 1.2 内存分配与释放:核心机制详解 1.2.1 new/delete 操作符 1.2.2 malloc/free 函数 第二章:智能指针 —— 内存管理利器 2.1 智能指针概览 2.2 常用智能指针类型 2.2.1 unique_ptr 2.2.2 shared_ptr 2.2.3 we…...

算法学习(17)—— FloodFill算法

目录 关于FloodFill算法 部分OJ题详解 733. 图像渲染 200. 岛屿数量 695. 岛屿的最大面积 130. 被围绕的区域 417. 太平洋大西洋水流问题 529. 扫雷问题 LCR130. 衣橱整理 关于FloodFill算法 爆搜&#xff0c;深搜&#xff0c;回溯的算法原理并不难&#xff0c;这类题…...

Kubernetes ConfigMap的创建与使用

前提条件 拥有Kubernetes集群环境&#xff0c;可参考&#xff1a;Kubernetes集群搭建理解Kubernetes部署知识&#xff0c;可参考&#xff1a;使用Kubernetes部署第一个应用 、Deloyment控制器 ConfigMap简介 ConfigMap 是 Kubernetes&#xff08;通常简称为 K8s&#xff09;中…...

灵当CRM uploadfile.php 文件上传致RCE漏洞复现

0x01 产品简介 灵当CRM是一款专为中小企业打造的智能客户关系管理工具,由上海灵当信息科技有限公司开发并运营。广泛应用于金融、教育、医疗、IT服务、房地产等多个行业领域,帮助企业实现客户个性化管理需求,提升企业竞争力。无论是新客户开拓、老客户维护,还是销售过程管…...

老旧小区用电安全保护装置#限流式防火保护器参数介绍#

摘要 随着居民住宅区用电负荷的增加&#xff0c;用电安全问题日益突出&#xff0c;火灾隐患频繁发生。防火限流式保护器作为一种新型电气安全设备&#xff0c;能够有效预防因电气故障引发的火灾事故。本文介绍了防火限流式保护器的工作原理、技术特点及其在居民住宅区用电系统…...

在git commit之前让其自动执行一次git pull命令

文章目录 背景原因编写脚本测试效果 背景原因 有时候可以看到项目的git 提交日志里好多 Merge branch ‘master’ of …记录。这些记录是怎么产生的呢&#xff1f; 是因为在本地操作 git add . 、 git commit -m "xxxxx"时&#xff0c;没有提前进行git pull操作&…...

【实现100个unity特效之4】Unity ShaderGraph使用教程与各种特效案例(2023/12/1更新)

文章目录 一、前言二、ShaderGraph1.什么是ShaderGraph2.在使用ShaderGraph时需要注意以下几点&#xff1a;3.优势4.项目 三、实例效果边缘发光进阶&#xff1a;带方向的菲涅尔边缘光效果裁剪进阶 带边缘色的裁剪溶解进阶 带边缘色溶解卡通阴影水波纹积雪效果不锈钢效果、冰晶效…...

单机和微服务的区别,微服务有什么问题?数据一致性问题怎么解决?幂等问题怎么解决?

单机和微服务的区别&#xff0c;微服务有什么问题&#xff1f;数据一致性问题怎么解决&#xff1f;幂等问题怎么解决&#xff1f; 单机架构和微服务架构在设计理念、部署和扩展性上有显著区别。 单机架构 vs 微服务架构 单机架构 定义&#xff1a;所有组件&#xff08;前端…...

McDonald‘s Event-Driven Architecture 麦当劳事件驱动架构

原文链接 1 mcdonalds-technical-blog/ 原文链接 2 mcdonalds-technical-blog/ 麦当劳在异步、事务性和分析性处理用例中使用跨技术栈的事件&#xff0c;包括移动订单进度跟踪和向客户发送营销通信&#xff08;交易和促销&#xff09;。 统一事件平台&#xff08;unified eve…...

Clickhouse(Centos)

地址信息 官网地址&#xff1a;Fast Open-Source OLAP DBMS - ClickHouse 下载地址&#xff1a;packages.clickhouse.com/rpm/stable/ 1.clickhouse-client-23.1.3.5.x86_64.rpm 2.clickhouse-common-static-23.1.3.5.x86_64.rpm 3.clickhouse-common-static-dbg-23.1.3.5.x86_…...

赛博错题本

机构抽象老师非得让我们整一个错题本&#xff0c;我寻思都学计算机了&#xff0c;还在整高中做题呢一套是什么意思呢&#xff0c;更何况考试也就一周一次&#xff0c;你整个本完完全全没有必要&#xff0c;整个赛博错题本得了。以后错题都会存在这里&#xff0c;基本上一周一更…...

【MySQL初阶】Ubuntu 环境安装 MySQL

&#x1f389;博主首页&#xff1a; 有趣的中国人 &#x1f389;专栏首页&#xff1a; 数据库初阶 &#x1f389;其它专栏&#xff1a; C初阶 | C进阶 | 初阶数据结构 小伙伴们大家好&#xff0c;本片文章将会讲解 Ubuntu 系统安装 MySQL 的相关内容。 如果看到最后您觉得这篇…...

【Kubernetes 指南】基础入门——Kubernetes 基本概念(二)

目录 二、Pod 1、Pod 简介 2、Pod 图示 3、nginx 容器 二、Pod 1、Pod 简介 - Kubernetes 使用 Pod 来管理容器&#xff0c;每个 Pod 可以包含一个或多个紧密关联的容器。 - Pod 是一组紧密关联的容器集合&#xff0c;它们共享 PID、IPC、Network 和 UTS namespace&#…...

Ubuntu系统下 npm install -g tauri 报错问题处理

处理在安装 Tauri 时遇到的问题&#xff0c;可以按照以下步骤进行操作 npm install -g taurinpm warn deprecated inflight1.0.6: This module is not supported, and leaks memory. Do not use it. Check out lru-cache if you want a good and tested way to coalesce async …...

数字逻辑(六)——下载Digital软件

Digital是一种用于设计和仿真数字逻辑电路的教育工具&#xff0c;它是免费、开源和跨平台的。这款软件十分适合新人&#xff0c;可以使用画简单的电路。 1 下载Digital软件 首先Digital的下载地址是&#xff1a; https://github.com/hneemann/Digital ​ 下载完成之后&…...

Ruby Raider使用教程

Ruby Raider是什么&#xff1f; Ruby Raider 是一款生成器和脚手架 gem&#xff0c;可让 UI 测试自动化更容易 Github链接&#xff1a;https://github.com/RaiderHQ/ruby_raider 目前支持的框架 Web自动化测试 Cucumber and Selenium Rspec and Selenium Cucumber and Wa…...

音视频入门基础:AAC专题(13)——FFmpeg源码中,获取ADTS格式的AAC裸流音频信息的实现

音视频入门基础&#xff1a;AAC专题系列文章&#xff1a; 音视频入门基础&#xff1a;AAC专题&#xff08;1&#xff09;——AAC官方文档下载 音视频入门基础&#xff1a;AAC专题&#xff08;2&#xff09;——使用FFmpeg命令生成AAC裸流文件 音视频入门基础&#xff1a;AAC…...

Spring Boot 中的 @Scheduled 定时任务以及开关控制

Scheduled注解是Spring框架&#xff08;包括Spring Boot&#xff09;中用于实现定时任务的一种方式。以下是对Scheduled注解的详细解析&#xff1a; 一、基本概念 Scheduled注解允许开发者在Spring容器中定义定时任务。通过简单地在一个方法上添加Scheduled注解&#xff0c;S…...

基于PXE与NFS共享的Ubuntu安装配置过程

假设存在服务器A、B、C 其中A为待装系统的服务器&#xff0c;DHCP&#xff08;IP池&#xff1a;192.168.0.150~192.168.0.160&#xff09;&#xff0c;假设需要安装的系统为Ubuntu 22.04 Desktop 其中B为PXE服务端服务器&#xff0c;IP: 192.168.0.100&#xff0c;这里将以Cent…...

Dots 常用操作

游戏中有多个蚂蚁群落&#xff0c;每个蚂蚁属于一个群落&#xff0c;如何设计数据结构&#xff1f; 方法1&#xff1a;为蚂蚁组件添加一个属性 ID&#xff0c;会造成逻辑中大量分支语句&#xff0c;如果分支语句逻辑不平衡可能带来 Job 调度问题&#xff0c;每个蚂蚁会有一份蚂…...

力扣-图论-20【算法学习day.70】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非…...

ModbusTCP从站转Profinet主站案例

一. 案例背景 在复杂的工业自动化场景中&#xff0c;企业常常会采用不同品牌的设备来构建生产系统。西门子SINAMICS G120变频器以其高性能、高精度的速度和转矩控制功能&#xff0c;在电机驱动领域应用广泛。施耐德M580可编程逻辑控制器则以强大的逻辑控制和数据处理能力著称&…...

Linux 线程池

1.概念介绍 线程池是一种多线程处理形式&#xff0c;它维护着多个线程&#xff0c;这些线程处于等待状态&#xff0c;随时准备接受任务并执行。线程池的主要目的是为了提高系统的性能和资源利用率&#xff0c;避免在处理短时间任务时频繁创建和销毁线程所带来的开销。 线程池…...

计算机视觉目标检测-1

文章目录 摘要Abstract1.目标检测任务描述1.1 目标检测分类算法1.2 目标定位的简单实现思路1.2.1 回归位置 2.R-CNN2.1 目标检测-Overfeat模型2.1.1 滑动窗口 2.2 目标检测-RCNN模型2.2.1 非极大抑制&#xff08;NMS&#xff09; 2.3 目标检测评价指标 3.SPPNet3.1 spatial pyr…...

2024最新鸿蒙开发面试题合集(一)-HarmonyOS NEXT Release(API 12 Release)

1. HarmonyOS应用打包后的文件扩展名是? 打包后的文件扩展名为.hap&#xff08;HarmonyOS Ability Package&#xff09;&#xff0c;这是HarmonyOS应用的标准包格式 2. 页面和自定义组件生命周期有哪些? 页面和自定义组件生命周期说明 有Entry装饰器的component组件的生命…...

HarmonyOS NEXT 实战之元服务:静态案例效果--航空出行

背景&#xff1a; 前几篇学习了元服务&#xff0c;后面几期就让我们开发简单的元服务吧&#xff0c;里面丰富的内容大家自己加&#xff0c;本期案例 仅供参考 先上本期效果图 &#xff0c;里面图片自行替换 效果图1完整代码案例如下&#xff1a; import { authentication } …...

详解 Python 中的json.loads和json.dumps方法:中英双语

中文版 详解 Python 中的 json.loads 和 json.dumps 方法 在 Python 的标准库中&#xff0c;json 模块用于处理 JSON 数据格式。JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;广泛用于前后端交互以及数据存储。json.loads …...

成方金融科技后端部分笔试题 - 解析

单选题 1.以下关于JAVA自动类型转换&#xff0c;描述错误的是哪一项?(B) A.byte->short B.char->short C.char->int D.float->double 2.请选择运行以下代码后&#xff0c;系统显示的内容什么?(B) public class Test {static {int x1;}static int x,y;publ…...

互联网视频云平台EasyDSS无人机推流直播技术如何助力野生动植物保护工作?

在当今社会&#xff0c;随着科技的飞速发展&#xff0c;无人机技术已经广泛应用于各个领域&#xff0c;为我们的生活带来了诸多便利。而在动植物保护工作中&#xff0c;无人机的应用更是为这一领域注入了新的活力。EasyDSS&#xff0c;作为一款集视频处理、分发、存储于一体的综…...

Vue3 中使用axios

1.安装axios、js-cookie、pinia axios命令行&#xff1a; npm install axios js-cookie命令行&#xff1a; npm install js-cookie store命令行&#xff1a; npm install pinia 2.配置文件 (1)缓存文件配置 src/plugins/auth.js const sessionCache {set (key, valu…...

【JAVA高级篇教学】第五篇:OpenFeign 微服务调用注意事项

在微服务架构中&#xff0c;OpenFeign 是一种常用的 HTTP 客户端工具&#xff0c;用于实现服务之间的调用。它提供了声明式的接口调用方式&#xff0c;大幅简化了开发工作。然而&#xff0c;在实际使用中&#xff0c;需要注意一些细节&#xff0c;尤其是在处理 GET、POST 请求和…...

Llama 3 简介(一)

目录 1. 引言 1.1 Llama 3 的简介 1.2 性能评估 1.3 开源计划 1.4 多模态扩展 ps 1. 缩放法则 2. 超额训练&#xff08;Over-training&#xff09; 3. 计算训练预算 4. 如何逐步估算和确定最优模型&#xff1f; 2. 概述 2.1 Llama 3 语言模型开发两个主要阶段 2.2…...

路由器做WPAD、VPN、透明代理中之间一个

本文章将采用家中TP-Link路由器 路由器进行配置DNS DNS理解知识本文DNS描述参考&#xff1a;网络安全基础知识&中间件简单介绍_计算机网络中间件-CSDN博客 TP LINK未知的错误&#xff0c;错误编号&#xff1a;-22025 TP-LINK 认证界面地址&#xff1a;https://realnam…...

Xcode 16 编译弹窗问题、编译通过无法,编译通过打包等问题汇总

问题1&#xff1a;打包的过程中不断提示 &#xff1a;codesign 想要访问你的钥匙串中的密钥“develop 或者distribution 证书” 解决&#xff1a;打开钥匙串&#xff0c;点击证书---显示简介---信任----改为始终信任 &#xff08;记住 &#xff1a;不能只修改钥匙的显示简介的…...

【编辑器扩展】打开持久化路径/缓存路径/DataPath/StreamingAssetsPath文件夹

代码 [MenuItem("Assets/Open Explorer/PersistentDataPath")]public static void OpenPersistentDataPath(){Application.OpenURL(Application.persistentDataPath);}[MenuItem("Assets/Open Explorer/DataPath")]public static void OpenDataPath(){Appl…...

shardingsphere分库分表项目实践1-让shardingsphere运行起来

学习新技术最快的方式就是&#xff1a; 1. 先找一个比较完善的demo跑起来 2. 弄清楚用法&#xff1a;配置、原理、使用场景 3. 移植到自己项目上&#xff0c;按照自己需求进行修改优化。 找demo项目的方法&#xff1a;优先去官方git库找&#xff0c;如果没有或者过于简单那么…...

Java预加载

预加载&#xff08;Preload&#xff09;是一种在程序运行之前预先加载所需资源或对象的优化技术&#xff0c;旨在提高程序的性能和响应速度。以下是对预加载的详细解释&#xff1a; 一、预加载的定义 预加载是指在程序实际运行之前&#xff0c;将预计会频繁使用的资源&#x…...