MySQL 数据库深度解析:历史、技术(b树和b+树)

news/2024/12/22 15:24:22/

一. MySQL 的历史与作用

        MySQL 诞生于 90 年代,它具有免费开源的特性,这使得其在互联网开发领域广受欢迎,逐渐成为了互联网开发的主流标准。数据库最为核心的任务就是存储数据,并且能够实现快速查询,而在这当中,索引起着极为关键的作用,它是加快查询速度的重要手段,能让数据库在面对大量数据时,高效地定位到用户所需的数据。

二、索引与平衡二叉树:查询效率的基石

        索引的本质是一种数据结构,它能够对数据库表中的一列或多列数据进行排序和组织,从而大大加速数据的查询过程。想象一下,如果把数据库表看作是一本厚重的书籍,索引就如同书籍的目录,通过目录可以快速定位到特定章节的内容,而无需逐页翻阅整本书。

        在众多索引数据结构中,平衡二叉树是一种经典的选择。平衡二叉树具有严格的结构特性,它的左右子树高度差绝对值不超过 1,并且左右子树均为平衡二叉树。这种结构使得在进行数据查找时,可以通过不断比较节点值与目标值的大小,每次都能将搜索范围缩小一半,就像进行二分查找一样高效。例如,对于一个包含 100 万个节点的平衡二叉树,最多只需进行约 20 次比较就能找到目标节点,而如果是顺序查找,则平均需要 50 万次比较。

 

   然而,平衡二叉树在数据库索引应用中也存在一些局限性。由于每个节点只能存储一个数据元素,当数据量非常大时,树的高度会迅速增加,导致磁盘 I/O 操作频繁。因为在数据库中,数据通常存储在磁盘上,每次从磁盘读取一个节点的数据都需要耗费一定的时间,树越高,磁盘 I/O 次数就越多,查询效率也就越低。

三、B 树:多叉平衡树的优势与应用

        为了克服平衡二叉树的局限性,B 树应运而生。B 树是一种多叉平衡树,它的每个节点可以存储多个数据元素以及多个子节点指针。这种结构允许 B 树在每个节点中存储更多的信息,从而大大降低了树的高度。例如,一个阶数为 100 的 B 树,每个节点可以存储 99 个数据元素,相比于平衡二叉树,其高度会显著降低。

        在 B 树中进行数据查找时,首先从根节点开始,将目标值与节点中的数据元素进行比较。如果目标值等于某个数据元素,则查找成功;如果目标值小于某个数据元素,则沿着对应的左子节点继续查找;如果目标值大于某个数据元素,则沿着对应的右子节点继续查找。通过这种方式,每次比较都能跳过大量的数据元素,快速定位到目标数据所在的子树,从而减少磁盘 I/O 操作次数,提高查询效率。

查询速度直接起飞

        以一个存储大量用户信息的数据库表为例,假设表中有用户 ID、姓名、年龄、地址等字段,如果经常需要根据用户 ID 查询用户信息,那么可以为用户 ID 字段创建一个 B 树索引。当执行查询语句时,数据库系统会利用 B 树索引快速定位到用户 ID 对应的记录,而无需扫描整个表。

b树的局限性

(1)、查找性能不稳定

原理

        B 树的结构特点是每个节点可以有多个子节点,数据分布在各个节点中。在查找操作中,根据查找值与节点中键值的比较,决定下一步查找的子节点方向。

        但是,由于数据在树中的分布可能不均匀,不同的查找值可能导致查找路径长度差异较大。例如,在图中查找 7 时很快,因为它在较上层的节点中就能找到;而查找 23 时就较慢,因为需要经过更多层的节点。

影响

        在实际应用中,这种查找性能的不稳定可能导致某些查询操作耗时较长,尤其是在数据量较大、树的高度较高时。对于对性能要求较高、对响应时间有严格要求的应用场景,这种不稳定的查找性能可能会成为一个严重的问题。

四、B + 树:优化查询性能的卓越数据结构

        在 B 树的基础上,B + 树进一步优化了数据存储和查询性能。B + 树与 B 树的主要区别在于数据的存储位置和叶子节点的连接方式。在 B + 树中,所有的数据都存储在叶子节点上,并且叶子节点之间通过指针相互连接,形成一个有序的链表。

        这种结构使得 B + 树在范围查询时表现尤为出色。例如,当执行查询语句 “SELECT * FROM users WHERE age BETWEEN 20 AND 30” 时,如果 users 表的 age 字段上创建了 B + 树索引,数据库系统可以从 B + 树的根节点开始,快速定位到 age 值在 20 到 30 之间的第一个叶子节点,然后通过叶子节点之间的指针顺序遍历后续的叶子节点,获取所有符合条件的记录,而无需像 B 树那样在非叶子节点和叶子节点之间频繁切换。

        由于 B + 树的非叶子节点只存储索引数据,不存储实际数据,这使得每个节点可以存储更多的索引信息,进一步降低了树的高度,减少了磁盘 I/O 操作次数。

 

1、B + 树的结构特点

数据存储位置

        B + 树的所有数据都存储在叶子节点上,而非叶子节点只用于索引。这与 B 树不同,B 树的数据可以分布在各个节点。

                例如,在图中的 B + 树结构中,最底层的蓝色块(数据块)存储了实际的数据,而上面的黄色块(主节点)主要用于索引,帮助定位数据所在的叶子节点。

叶子节点的连接

        B + 树的叶子节点之间通过指针相互连接,形成一个有序的链表。这种结构使得范围查询变得非常高效。

        例如,在图中可以看到,所有的叶子节点(蓝色数据块)是顺序连接的,这对于查找一个范围内的数据(如查找 >=16 and <23 的数据)非常方便。

2、B + 树的查找操作

等值查找

        当进行等值查找时(例如查找一个特定的值),从根节点开始,根据节点中的键值比较,逐步向下层查找,最终在叶子节点找到目标值。

        例如,在图中如果要查找一个特定的值,会从最上层的节点开始,通过比较键值,沿着路径找到对应的叶子节点。

范围查找

        对于范围查找(如查找 >=16 and <23 的数据),首先通过索引找到范围下限对应的叶子节点(如 16 对应的叶子节点),然后通过叶子节点之间的指针顺序遍历,直到找到范围上限对应的叶子节点(如 23 对应的叶子节点)。

        图中用红色线条展示了查找 >=16 and <23 的数据的路径,从 16 对应的叶子节点开始,沿着叶子节点的连接顺序查找,直到接近 23 对应的叶子节点。

3、B + 树的优势

查询性能

        由于数据都存储在叶子节点且叶子节点有序连接,B + 树在范围查询和排序操作上比 B 树更高效。无论是查找单个值还是一个范围内的值,都能快速定位。

磁盘 I/O 优化

        B + 树的非叶子节点只存储索引信息,使得每个节点可以存储更多的索引项,从而降低树的高度。树的高度降低意味着在查找数据时,磁盘 I/O 操作次数减少,提高了查询速度。

 

 


http://www.ppmy.cn/news/1557220.html

相关文章

Python tkinter写的《电脑装配单》和 Html版 可打印 可导出 excel 文件

Python版 样图&#xff1a; 说明书&#xff1a; markdown # 电脑配置单使用说明书 ## 一、软件简介 电脑配置单是一个用于创建和比较两套电脑配置方案的工具软件。用户可以选择各种电脑配件,输入数量和价格,软件会自动计算总金额,并支持导出和打印配置单。 ## 二、主要功能 1. …

电脑excel词典(xllex.dll)文件丢失是或损坏是什么原因?“xllex.dll文件缺失“要怎么解决?

Excel词典&#xff08;xllex.dll&#xff09;文件丢失或损坏&#xff1f;别担心&#xff0c;这里有解决之道&#xff01; 在日常的电脑使用和办公软件操作中&#xff0c;我们偶尔会碰到一些让人头疼的问题&#xff0c;比如Excel突然提示“Excel词典&#xff08;xllex.dll&…

半连接转内连接规则的原理与代码解析 |OceanBase查询优化

背景 在查询语句中&#xff0c;若涉及半连接&#xff08;semi join&#xff09;操作&#xff0c;由于半连接不满足交换律的规则&#xff0c;连接操作必须遵循语句中定义的顺序执行&#xff0c;从而限制了优化器根据参与连接的表的实际数据量来灵活选择优化策略的能力。为此&am…

相机与NAS的奇妙组合,如何使用相机拍照自动上传或备份到NAS

相机与NAS的奇妙组合&#xff0c;如何使用相机拍照自动上传或备份到NAS 哈喽小伙伴们好&#xff0c;我是Stark-C~ 对于喜欢使用专业器材拍照摄影的小伙伴来说&#xff0c;想要将相机存储卡中的照片或视频导出到电脑上&#xff0c;要么是使用数据线直接和相机连接&#xff0c;…

LLaMA-Factory 单卡3080*2 deepspeed zero3 微调Qwen2.5-7B-Instruct

环境安装 git clone https://gitcode.com/gh_mirrors/ll/LLaMA-Factory.git 下载模型 pip install modelscope modelscope download --model Qwen/Qwen2.5-7B-Instruct --local_dir /root/autodl-tmp/models/Qwen/Qwen2.5-7B-Instruct 微调 llamafactory-cli train \--st…

如何更改 maven 指定的 java 版本 set JAVA_HOME=C:\Program Files\Java\jdk1.8

当我们用 mvn 在终端执行的时候 例如 mvn clean test执行结果如下&#xff1a; 此时我们想要修改 maven 指定的JAVA_HOME 找到maven的安装目录&#xff0c;打开 mvn.cmd 然后鼠标右键&#xff0c;点击编辑按钮 将 第一行 JAVA_HOME 设置为自己的本地java目录即可 然后再次…

Vue 环境变量配置、使用方法、注意事项

注意事项&#xff1a; 环境变量必须以 VUE_APP_ 开头&#xff0c;只有 VUE_APP_ 开头的变量才会被 webpack 处理NODE_ENV 是内置的环境变量&#xff0c;NODE_ENV 不需要 VUE_APP_ 前缀修改环境变量后需要重启开发服务器才能生效环境变量在构建时会被静态替换环境变量在客户端代…

踩准智能汽车+机器人两大风口,速腾聚创AI+机器人应用双线爆发

日前&#xff0c;RoboSense速腾聚创交出了一份亮眼的Q3财报。受到多重利好消息影响&#xff0c;其股价也应势连续大涨。截止12月9日发稿前&#xff0c;速腾聚创股价近一个月内累计涨幅已超88%。 财务数据方面&#xff0c;速腾聚创在今年前三季度实现总收入约11.3亿元&#xff0…