数据库-索引结构(B-Tree,B+Tree,Hash,二叉树)

文章目录
- 索引结构有哪些?
- 二叉树详解?
- B-Tree详解?
- B+Tree详解?
- Hash详解?
- 本篇小结
更多相关内容可查看
索引结构有哪些?
MySQL的索引是在存储引擎层实现的,不同的存储引擎有不同的索引结构,主要包含以下几种

上述是MySQL中所支持的所有的索引结构,接下来,我们再来看看不同的存储引擎对于索引结构的支持情况。

注意: 我们平常所说的索引,如果没有特别指明,都是指B+树结构组织的索引
二叉树详解?
假如说MySQL的索引结构采用二叉树的数据结构,比较理想的结构如下

如果主键是顺序插入的,则会形成一个单向链表,结构如下:

所以,如果选择二叉树作为索引结构,会存在以下缺点:
- 顺序插入时,会形成一个链表,查询性能大大降低。
- 大数据量情况下,层级较深,检索速度慢。
此时大家可能会想到,我们可以选择红黑树,红黑树是一颗自平衡二叉树,那这样即使是顺序插入数据,最终形成的数据结构也是一颗平衡的二叉树,结构如下:
但是,即使如此,由于红黑树也是一颗二叉树,所以也会存在一个缺点:大数据量情况下,层级较深,检索速度慢。所以,在MySQL的索引结构中,并没有选择二叉树或者红黑树,而选择的是B+Tree
B-Tree详解?
B-Tree,B树是一种多叉路平衡查找树,相对于二叉树,B树每个节点可以有多个分支,即多叉。
以一颗最大度数(max-degree)为5(5阶)的b-tree为例,那这个B树每个节点最多存储4个key,5个指针:

注: 树的度数指的是一个节点的子节点个数。
我们可以通过一个数据结构可视化的网站来简单演示一下。 https://www.cs.usfca.edu/~galles/visualization/BTree.html

插入一组数据: 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。然后观察一些数据插入过程中,节点的变化情况。

特点:
- 5阶的B树,每一个节点最多存储4个key,对应5个指针。
- 一旦节点存储的key数量到达5,就会裂变,中间元素向上分裂。
- 在B树中,非叶子节点和叶子节点都会存放数据。
B+Tree详解?
B+Tree是B-Tree的变种,我们以一颗最大度数(max-degree)为4(4阶)的b+tree为例,来看一下其结构示意图:
B+Tree : 只有叶子节点存储数据

我们可以看到,两部分:
- 绿色框框起来的部分,是索引部分,仅仅起到索引数据的作用,不存储数据。
- 红色框框起来的部分,是数据存储部分,在其叶子节点中要存储具体的数据。
我们可以通过一个数据结构可视化的网站来简单演示一下。 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

插入一组数据: 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。然后观察一些数据插入过程中,节点的变化情况。

最终我们看到,B+Tree 与 B-Tree相比,主要有以下三点区别:
- 所有的数据都会出现在叶子节点。
- 叶子节点形成一个单向链表。
- 非叶子节点仅仅起到索引数据作用,具体的数据都是在叶子节点存放的。
上述是标准的B+Tree的数据结构,接下来,我们再来看看MySQL中优化之后的B+Tree。
MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上,增加一个指向相邻叶子节点的链表指针,就形成了带有顺序指针的B+Tree,提高区间访问的性能,利于排序

Hash详解?
MySQL中除了支持B+Tree索引,还支持一种索引类型—Hash索引
哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中。

如果两个(或多个)键值,映射到一个相同的槽位上,他们就产生了hash冲突(也称为hash碰撞),可以通过链表来解决

特点
- Hash索引只能用于对等比较(=,in),不支持范围查询(between,>,< ,…)因为他是通过映射到hash槽的方式去获取索引,无顺序可言,也无范围可言
- 无法利用索引完成排序操作
- 查询效率高,通常(不存在hash冲突的情况)只需要一次检索就可以了,效率通常要高于B+tree索引
存储引擎支持
在MySQL中,支持hash索引的是Memory存储引擎。 而InnoDB中具有自适应hash功能,hash索引是InnoDB存储引擎根据B+Tree索引在指定条件下自动构建的。
本篇小结
其他索引的相关问题链接如下
数据库-索引(高级篇)
索引分类(主键索引、唯一索引、普通索引、全文索引)
索引语法
相关文章:
数据库-索引结构(B-Tree,B+Tree,Hash,二叉树)
文章目录 索引结构有哪些?二叉树详解?B-Tree详解?BTree详解?Hash详解?本篇小结 更多相关内容可查看 索引结构有哪些? MySQL的索引是在存储引擎层实现的,不同的存储引擎有不同的索引结构,主要包…...
Microsoft Azure AI语音服务
一:文字转语音SDK安装 安装语音 SDK - Azure AI services | Microsoft Learn 二:基于文本转语音Rest API 文本转语音 API 参考 (REST) - 语音服务 - Azure AI services | Microsoft Learn 三:基于文本合成语音 如何基于文本合成语音 - 语…...
【Linux】常用指令、热键与权限管理
一、常用指令 (1)ls 功能:列出指定目录下的所有子目录与文件 用法:ls (选项) (目录或文件名) 常用选项: -a:列出目录下的所有文件,包括隐藏…...
深度学习知识点全面总结
目录 1.深度学习的一些重要知识点 神经网络: 深度学习模型: 深度学习技术: 深度学习应用: 2.深度学习、机器学习、人工智能 3.用python实现简单神经网络模型 4.用于深度学习显卡推荐排序 5.深度学习如何入门? 掌握基础知识: 选择学习资源&…...
【编写控制手机压测的脚本】
编写一个控制手机压测的脚本可以使用Python语言来实现。以下是一个简单的示例脚本: import subprocess import time# 打开app subprocess.call(["adb", "shell", "am", "start", "-n", "com.example.app/.…...
计算机网络-路由策略与路由控制一
到目前为止我们学习了路由与交换基础,路由协议有静态、RIP、OSPF、IS-IS等,但是根据实际组网需求,往往需要实施一些路由策略对路由信息进行过滤、属性设置等操作,通过对路由的控制,可以影响数据流量转发。 因此我们开始…...
在线3D展示软件三维展示软件推荐哪家?
博维数孪、动动三维和sketchfab的在线网页3D展示软件工具选择哪一比较好? 选择在线3D展示软件时,需要考虑几个关键因素,包括软件的功能、用户界面、价格、社区支持和兼容性等。以上几款软件工具都有各自的优势,具体取决于需求和偏…...
VS Code中PlatformIO IDE的安装并开发Arduino
VS Code中PlatformIO IDE的安装并开发Arduino VS Code的安装 略 PlatformIO IDE的安装 PlatformIO IDE是是什么 PlatformIO IDE 是一个基于开源的跨平台集成开发环境(IDE),专门用于嵌入式系统和物联网(IoT)开发。…...
Java入门——异常
异常的背景 初识异常 我们曾经的代码中已经接触了一些 "异常" 了. 例如: //除以 0 System.out.println(10 / 0); // 执行结果 Exception in thread "main" java.lang.ArithmeticException: / by zero //数组下标越界 int[] arr {1, 2, 3}; System.out.…...
智慧园区:视频系统建设的核心要素与实践路径
一、背景分析 园区作为城市的基本单元,是最重要的人口和产业聚集区。根据行业市场调研,90%以上城市居民工作与生活在园区进行,80%以上的GDP和90%以上的创新在园区内产生,可以说“城市,除了马路都是园区”。 园区形态…...
基于ChatGLM+Langchain离线搭建本地知识库(免费)
目录 简介 服务部署 实现本地知识库 测试 番外 简介 ChatGLM-6B是清华大学发布的一个开源的中英双语对话机器人。基于 General Language Model (GLM) 架构,具有 62 亿参数。结合模型量化技术,用户可以在消费级的显卡上进行本地部署(INT…...
MySQL 进阶使用【函数、索引、视图、存储过程、存储函数、触发器】
前言 做数仓开发离不开 SQL ,写了很多 HQL 回头再看 MySQL 才发现,很多东西并不是 HQL 所独创的,而是几乎都来自于关系型数据库通用的 SQL;想到以后需要每天和数仓打交道,那么不管是 MySQL 还是 Oracle ,都…...
SCSS详解
SCSS(Sassy CSS)是Sass 3引入的新语法,完全兼容CSS3,并且继承了Sass的强大功能。与原始的Sass语法不同,SCSS语法使用了和CSS一样的块语法,即使用大括号“{}”将不同的规则分开,使用分号“;”将具…...
Vue 问题集
Q:MaxListenersExceededWarning: Possible EventEmitter memory leak detected. 11 connection listeners added. Use emitter.setMaxListeners() to increase limit A: 可能由多个问题导致,我的是情况1 1. vue.config.js - devServer 代理设置只能添加10个&#…...
Elasticsearch 8.1官网文档梳理 -综述
积累 Elasticsearch 的常用知识,以及日常维护、学习用到的 API。因为相关内容太多,所以根据模块整理成了不同的文章,并在这里做汇总,整个系列的文章都会持续更新 目录 Elasticsearch 8.1官网文档梳理 - 四、Set up Elasticsearc…...
当自身需要使用的 gcc版本 和Linux 默认版本 存在大版本差异时怎样处理
前言 本文档意在说明 当使用者 gcc 版本 和 Linux系统默认的gcc版本 存在 大版本差异 时,怎样处理,能够兼用多个版本 并且对已有 程序影响最小。 问题描述 linux系统默认的gcc版本:7.5.0我们程序需要使用的gcc版本:8.4.0 安装…...
深度学习之卷积神经网络理论基础
深度学习之卷积神经网络理论基础 卷积层的操作(Convolutional layer) 在提出卷积层的概念之前首先引入图像识别的特点 图像识别的特点 特征具有局部性:老虎重要特征“王字”仅出现在头部区域特征可能出现在任何位置下采样图像,…...
控制台的高度可调有哪些重要意义解析
在现代办公环境中,控制台的高度可调性越来越受到重视。它不仅为员工提供了更加舒适的工作环境,还提高了工作效率和生产力。本文将详细探讨控制台高度可调的重要性,并解析其在实际应用中的优势。 个性化适应需求 对于长时间在控制台前工作的用…...
智能招聘?远在天边,近在眼前
2023年曾被称为“史上最卷毕业季”,当年应届高校毕业生高达1158万人。人力资源社会保障部公布的数据显示,即将到来的2024毕业季,全国普通高校毕业生规模预计将达1179万人,同比增加21万人,就业总量压力依然高企。看来&a…...
文字游侠AI丨简直是写作神器,头条爆文一键生成稳定赚米!附渠道和详细教程(只需四步)!
在数字时代的浪潮中,人们不断寻求网络空间中的商机,期望在互联网的浩瀚海洋里捕捉到稳定的财富。随着人工智能技术的突飞猛进,越来越多的AI工具被融入到各行各业,开辟了新天地,带来了创新的盈利模式。 其中,…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
