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

索引的底层数据结构、B+树的结构、为什么InnoDB使用B+树而不是B树呢

索引的底层数据结构

MySQL中常用的是Hash索引和B+树索引

Hash索引:基于哈希表实现的,查找速度非常快,但是由于哈希表的特性,不支持范围查找和排序,在MySQL中支持的哈希索引是自适应的,不能手动创建

B+树的结构

        B+树 是一种高效的多路平衡树,适合磁盘存储和范围查询。它的结构特点包括数据集中在叶子节点、叶子节点连接成链表、内部节点仅存储键值和指针。在数据库和文件系统中,B+树 被广泛应用于索引和数据存储,具有查询性能稳定、适合高并发等优势。

 如图:B+树具有以下特点:

只有叶子结点才存放数据,中间节点都是用来存放目录项作为索引

非叶子节点分为不同层次,通过分层来降低每一层的搜索量

B+树的搜索策略:

从根节点开始,通过二分法快速定位到符合页内范围包含查询值的页,在中间结点中继续根据二分法来寻找符合页内范围复合查询值的页,接着在叶子节点中通过槽查找记录使用二分法快速定位要查询的记录在哪个槽,找到槽后再遍历槽中所有的记录,找到寻找的分组。

为什么InnoDB使用B+树而不是B树呢 

B-Tree:

  • 每个节点既存储数据也存储子节点的指针
  • 数据分布在所有的节点中,包括内部节点和叶子节点
  • 查找时可能会直接在内部节点中就能找到数据不需要遍历到叶子节点

B+Tree:

  • 只有叶子结点存储数据,内部节点仅存储键值和子节点的指针
  • 所有叶子节点通过指针连接成一个有序链表
  • 查找时必须遍历到叶子节点才能获取数据 

B+Tree的优势:

更适合磁盘I/O:

  • 因为B+树的内部节点不存储数据只存储键值和指针,所以每个节点可以存储更多的键值,从而降低树的高度,树的高度越低磁盘I/O次数越少,查询性能越高(索引数据量很大,一定是存储在磁盘中的,每访问一个节点就会进行一次磁盘IO操作,所以树的高度越低,一次查询的期望IO次数就越少,效率就越高)
  • B+树的叶子节点通过指针连接成链表,更适合范围查询如(BETWEEN,>,<等操作),而树的范围查询需要在不同层级的节点之间跳转,效率较低 

更适合数据库场景:

  • 数据集中在叶子节点上,查询时都需要遍历到叶子节点,这使得查询性能更稳定。B树的数据可能分布在内部节点和叶子结点,查询性能不稳定 
  • 数据库查询中经常需要使用范围查询,B+树的叶子节点链表结构非常适合这种场景,而B树需要多次遍历内部节点

更适合并发控制:

  • 在并发场景下,B+树的叶子节点链表可以更容易地支持范围查询和顺序访问
  • 而B树的结构在并发访问时可能需要更多的锁机制(数据分布在内部节点和叶子节点。节点分裂与合并涉及多个节点。锁的粒度较大,容易导致锁冲突)

B+树在InnoDB中的具体应用:

主键索引(聚簇索引):

        InnoDB使用B+树实现主键索引,叶子节点存储完整的数据行

        这种设计是的通过主键查询数据时可以直接获取数据,不需要回表

二级索引(非聚簇索引): 

        InnoDB的二级索引也是B+树,但是叶子节点存储的是主键值,通过二级索引查询时,先获取主键值再通过主键索引查找数据(回表)

相关文章:

索引的底层数据结构、B+树的结构、为什么InnoDB使用B+树而不是B树呢

索引的底层数据结构 MySQL中常用的是Hash索引和B树索引 Hash索引&#xff1a;基于哈希表实现的&#xff0c;查找速度非常快&#xff0c;但是由于哈希表的特性&#xff0c;不支持范围查找和排序&#xff0c;在MySQL中支持的哈希索引是自适应的&#xff0c;不能手动创建 B树的…...

【工欲善其事】利用 DeepSeek 实现复杂 Git 操作:从原项目剥离出子版本树并同步到新的代码库中

文章目录 利用 DeepSeek 实现复杂 Git 操作1 背景介绍2 需求描述3 思路分析4 实现过程4.1 第一次需求确认4.2 第二次需求确认4.3 第三次需求确认4.4 V3 模型&#xff1a;中间结果的处理4.5 方案验证&#xff0c;首战告捷 5 总结复盘 利用 DeepSeek 实现复杂 Git 操作 1 背景介绍…...

网络编程套接字(中)

文章目录 &#x1f34f;简单的TCP网络程序服务端创建套接字服务端绑定服务端监听服务端获取连接服务端处理请求客户端创建套接字客户端连接服务器客户端发起请求服务器测试单执行流服务器的弊端 &#x1f350;多进程版的TCP网络程序捕捉SIGCHLD信号让孙子进程提供服务 &#x1…...

前端学习-事件委托(三十)

目录 前言 课前思考 for循环注册事件 语法 事件委托 1.事件委托的好处是什么? 2.事件委托是委托给了谁&#xff0c;父元素还是子元素 3.如何找到真正触发的元素 示例代码 总结 前言 才子佳人&#xff0c;自是白衣卿相 课前思考 1.如果同时给多个元素注册事件&…...

线程池以及在QT中的接口使用

文章目录 前言线程池架构组成**一、任务队列&#xff08;Task Queue&#xff09;****二、工作线程组&#xff08;Worker Threads&#xff09;****三、管理者线程&#xff08;Manager Thread&#xff09;** 系统协作流程图解 一、QRunnable二、QThreadPool三、线程池的应用场景W…...

c语言操作符(详细讲解)

目录 前言 一、算术操作符 一元操作符&#xff1a; 二元操作符&#xff1a; 二、赋值操作符 代码例子&#xff1a; 三、比较操作符 相等与不相等比较操作符&#xff1a; 大于和小于比较操作符&#xff1a; 大于等于和小于等于比较操作符&#xff1a; 四、逻辑操作符 逻辑与&…...

【自然语言处理(NLP)】深度学习架构:Transformer 原理及代码实现

文章目录 介绍Transformer核心组件架构图编码器&#xff08;Encoder&#xff09;解码器&#xff08;Decoder&#xff09; 优点应用代码实现导包基于位置的前馈网络残差连接后进行层规范化编码器 Block编码器解码器 Block解码器训练预测 个人主页&#xff1a;道友老李 欢迎加入社…...

JavaScript 入门教程

JavaScript 入门教程 JavaScript 入门教程引言学习 JavaScript 的好处常见的 JavaScript 框架和库 安装开发环境下载并安装 Node.js 和 npm安装常用开发工具&#xff08;如 VS Code&#xff09;配置本地开发环境 基础语法入门数据类型变量与常量运算符算术运算符比较运算符 条件…...

浅析CDN安全策略防范

CDN&#xff08;内容分发网络&#xff09;信息安全策略是保障内容分发网络在提供高效服务的同时&#xff0c;确保数据传输安全、防止恶意攻击和保护用户隐私的重要手段。以下从多个方面详细介绍CDN的信息安全策略&#xff1a; 1. 数据加密 数据加密是CDN信息安全策略的核心之…...

代码随想录刷题day22|(字符串篇)344.反转字符串、541.反转字符串 II

目录 一、题目思路 二、相关题目 三、总结与知识点 3.1 字符数组转换成字符串 一、题目思路 344反转字符串比较容易&#xff0c;双指针即可在空间复杂度为O(1)的基础上解决&#xff1b; 541反转字符串II &#xff1a;其中for循环中 i 每次的取值&#xff0c;不是 i&#…...

python学opencv|读取图像(五十三)原理探索:使用cv.matchTemplate()函数实现最佳图像匹配

【1】引言 前序学习进程中&#xff0c;已经探索了使用cv.matchTemplate()函数实现最佳图像匹配的技巧&#xff0c;并且成功对两个目标进行了匹配。 相关文章链接为&#xff1a;python学opencv|读取图像&#xff08;五十二&#xff09;使用cv.matchTemplate()函数实现最佳图像…...

win10部署本地deepseek-r1,chatbox,deepseek联网(谷歌网页插件Page Assist)

win10部署本地deepseek-r1&#xff0c;chatbox&#xff0c;deepseek联网&#xff08;谷歌网页插件Page Assist&#xff09; 前言一、本地部署DeepSeek-r1step1 安装ollamastep2 下载deepseek-r1step2.1 找到模型deepseek-r1step2.2 cmd里粘贴 后按回车&#xff0c;进行下载 ste…...

冯·诺依曼体系结构

目录 冯诺依曼体系结构推导 内存提高冯诺依曼体系结构效率的方法 你使用QQ和朋友聊天时&#xff0c;整个数据流是怎么流动的&#xff08;不考虑网络情况&#xff09; 与冯诺依曼体系结构相关的一些知识 冯诺依曼体系结构推导 计算机的存在就是为了解决问题&#xff0c;而解…...

本地部署 DeepSeek-R1 模型

文章目录 霸屏的AIDeepSeek是什么&#xff1f;安装DeepSeek安装图形化界面总结 霸屏的AI 最近在刷视频的时候&#xff0c;总是突然突然出现一个名叫 DeepSeek 的玩意&#xff0c;像这样&#xff1a; 这样&#xff1a; 这不经激起我的一顿好奇心&#xff0c;这 DeepSeek 到底是个…...

Mybatis——sql映射文件中的增删查改

映射文件内的增删查改 准备工作 准备一张数据表&#xff0c;用于进行数据库的相关操作。新建maven工程&#xff0c; 导入mysql-connector-java和mybatis依赖。新建一个实体类&#xff0c;类的字段要和数据表的数据对应编写接口编写mybatis主配置文件 public class User {priva…...

【开源免费】基于Vue和SpringBoot的流浪宠物管理系统(附论文)

本文项目编号 T 182 &#xff0c;文末自助获取源码 \color{red}{T182&#xff0c;文末自助获取源码} T182&#xff0c;文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...

nth_element函数——C++快速选择函数

目录 1. 函数原型 2. 功能描述 3. 算法原理 4. 时间复杂度 5. 空间复杂度 6. 使用示例 8. 注意事项 9. 自定义比较函数 11. 总结 nth_element 是 C 标准库中提供的一个算法&#xff0c;位于 <algorithm> 头文件中&#xff0c;用于部分排序序列。它的主要功能是将…...

DNS缓存详解(DNS Cache Detailed Explanation)

DNS缓存详解 清空DNS缓存可以让网页访问更快捷。本文将从什么是DNS缓存、为什么清空DNS缓存、如何清空DNS缓存、清空DNS缓存存在的问题四个方面详细阐述DNS缓存清空的相关知识。 一、什么是DNS缓存 1、DNS缓存的定义&#xff1a; DNS缓存是域名系统服务在遇到DNS查询时自动…...

课设:【ID0022】火车票售票管理系统(前端)

技术栈&#xff1a;Java&#xff0c;JavaSwing&#xff0c;MySQL 数据库表数量&#xff1a;12个 1.功能描述 管理员功能 管理员是系统的高级用户&#xff0c;拥有对整个系统的全面管理权限。管理员的功能模块包括以下六个方面&#xff1a; 对用户管理增删查改 对售票员…...

Ruby 类和对象

Ruby 类和对象 引言 在软件开发中,类和对象是面向对象编程(OOP)的核心概念。Ruby 作为一种动态、解释型编程语言,也以简洁的方式支持面向对象编程。本文将深入探讨 Ruby 中的类和对象,包括它们的定义、创建、使用以及一些高级特性。 类与对象的定义 类 在 Ruby 中,类…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

VSCode 使用CMake 构建 Qt 5 窗口程序

首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...

【R语言编程——数据调用】

这里写自定义目录标题 可用库及数据集外部数据导入方法查看数据集信息 在R语言中&#xff0c;有多个库支持调用内置数据集或外部数据&#xff0c;包括studentdata等教学或示例数据集。以下是常见的库和方法&#xff1a; 可用库及数据集 openintro库 该库包含多个教学数据集&a…...