红黑树及MySQL 基础架构

红黑树简介及左旋、右旋、变色
红黑树(Red Black Tree)是一种自平衡二叉搜索树(二叉查找树),是一种特殊的二叉搜索树,在进行插入和删除时通过特定操作保持二叉树自身的平衡,从而获得较高的查找性能。

红黑树的平衡操作通过左旋、右旋和变色来实现,平衡的过程是比较复杂的,但通过平衡操作,可以获得更高效的性能。对二叉搜索树进行平衡后,最坏情况的运行时间得到优化,可以在O(logN)的时间复杂度内完成查找、插入和删除,N是二叉搜索树中的节点数。

一、二叉搜索树的性能分析

红黑树是一种特殊的二叉搜索树,所以本文先从二叉搜索树说起。

二叉搜索树是一种特殊的二叉树,具有如下特性:

1. 如果二叉树的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。

2. 如果二叉树的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。

3. 如果独立地看,左子树、右子树也分别为二叉搜索树。

二叉搜索树的实现,可以参考:Python实现二叉搜索树_小斌哥ge的博客-CSDN博客

向二叉搜索树中插入数据时,为了满足二叉搜索树的特性,会递归地比较插入节点的值与根节点的值,将数据插入正确的位置。

如在一棵空二叉搜索树中插入 [50, 77, 55, 29, 10, 30, 66, 80, 51, 18, 90] ,得到的二叉搜索树结构如下图:

 

二、红黑树简介

红黑树是一种自平衡二叉搜索树,每个节点都有颜色,颜色为红色或黑色,红黑树由此得名。除了满足二叉搜索树的特性以外,红黑树还具有如下特性:

1. 节点是红色或黑色。

2. 根节点是黑色。

3. 所有叶子节点都是黑色的空节点。(叶子节点是NIL节点或NULL节点)

4. 每个红色节点的两个子节点都是黑色节点。(从每个叶子节点到根的所有路径上不能有两个连续的红色节点)

5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

要知道什么是红黑树,必须记住这5条特性。这5条特性其实是5条规定,只有满足这5条规定才属于红黑树。对于二叉搜索树的特性,只要理解了,很容易记住,但对于红黑树的5条特性,需要“死记硬背”。

如上面例子中的二叉搜索树,可以加上颜色变成一颗红黑树。(实际的红黑树是一个节点一个节点插入的,如下的构造过程只是为了先理解红黑树的5条特性)

1. 先加上叶子节点,并把所有节点都标记为黑色。

2. 这棵二叉树显然不满足红黑树的特性5,如节点10到左子树的叶子节点的路径上有一个黑节点,到右子树的叶子节点的路径上有两个黑节点,所以要将一些黑节点变成红节点。

从根节点50开始,使根节点到每个叶子节点的路径上都有4个黑节点,得到的红黑树如下。

 

当然,也可以使根节点到每个叶子节点的路径上都有3个黑节点,得到的红黑树如下。

 

现在看一下这两棵树是否满足红黑树的5条特性,可以一条一条的对比,至于构造的过程先不管(这其实是硬拼出来的),后面再讲怎么构造。

根据红黑树的特性5,任意节点到其所有叶节点的路径上的黑节点数都相同,从而保持红黑树的平衡。如果只看黑节点,这种平衡是完美的平衡,所以红黑树的平衡也称为黑色完美平衡。当然,因为红节点的存在,红黑树并不是完美平衡的,甚至有可能不满足平衡二叉树的特性。

当在红黑树中插入节点或删除节点时,红黑树的平衡很可能会被破坏(不满足其中一条或多条特性),要立即对红黑树进行调整,使红黑树重新满足5条特性。

调整平衡的操作包含左旋、右旋和变色,下面依次对这些操作进行介绍。

三、红黑树的左旋和右旋操作

对于一棵红黑树,它满足红黑树的5条特性。插入或删除节点之后,红黑树就发生了变化,很可能不再完全满足红黑树的5条特性了,也就是不再是一棵红黑树了,而是一棵普通的二叉搜索树。这时候,为了使二叉搜索树重新变成红黑树,就需要对二叉搜索树进行操作,使它满足红黑树的5条特性。

通过旋转,可以使二叉搜索树重新满足红黑树的5条特性。旋转分为左旋和右旋。

1. 红黑树的左旋

左旋:以某个节点作为支点(旋转节点),其右子节点变为旋转节点的父节点,右子节点的左子节点变为旋转节点的右子节点,旋转节点的左子节点保持不变。右子节点的左子节点相当于从右子节点上“断开”,重新连接到旋转节点上。

为了不失一般性,可以看下图中的例子。左边是左旋前的红黑树局部结构,先不考虑整体,只看局部,左旋前不满足红黑树的特性5。

左旋时,旋转节点为节点50,左旋后,旋转节点的右子节点70变为旋转节点50的父节点,右子节点的左子节点60从右子节点70上“断开”,成为旋转节点50的右子节点。

2. 红黑树的右旋

右旋:以某个节点作为支点(旋转节点),其左子节点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子节点,旋转节点的右子节点保持不变。左子节点的右子节点相当于从左子节点上“断开”,重新连接到旋转节点上。

不难看出,左旋和右旋是相反的,可逆的。

下图中的例子仍然是红黑树的局部,左边的结构不满足红黑树的特性5。

右旋时,旋转节点为节点70,右旋后,旋转节点的左子节点50变为旋转节点70的父节点,左子节点的右子节点60从左子节点50上“断开”,成为旋转节点70的左子节点。右旋后(右图),重新满足了红黑树的特性5。

四、红黑树的变色操作

当对红黑树进行插入或删除节点之后,如果不再完全满足红黑树的5条特性,除了旋转,变色也可以使二叉搜索树重新满足红黑树的5条特性。

变色:将节点的颜色由红变黑或由黑变红。

向红黑树中插入节点时,新节点的颜色都设置为红色。不管新节点是什么颜色,特性3都不可能被破坏,特性1、2、4都有可能被破坏。如果插入的节点是黑色,则一定会破坏特性5,需要进行调整,如果插入的节点是红色,则一定不会破坏特性5。所以将新节点设置为红色,可以降低破坏红黑树特性的可能性。

MySQL 基础架构 :

下图是 MySQL 的一个简要架构图,从下图你可以很清晰的看到客户端的一条 SQL 语句在 MySQL 内部是如何执行的。

从上图可以看出, MySQL 主要由下面几部分构成:

  • 连接器: 身份认证和权限相关(登录 MySQL 的时候)。
  • 查询缓存: 执行查询语句的时候,会先查询缓存(MySQL 8.0 版本后移除,因为这个功能不太实用)。
  • 分析器: 没有命中缓存的话,SQL 语句就会经过分析器,分析器说白了就是要先看你的 SQL 语句要干嘛,再检查你的 SQL 语句语法是否正确。
  • 优化器: 按照 MySQL 认为最优的方案去执行。
  • 执行器: 执行语句,然后从存储引擎返回数据。 执行语句之前会先判断是否有权限,如果没有权限的话,就会报错。
  • 插件式存储引擎:主要负责数据的存储和读取,采用的是插件式架构,支持 InnoDB、MyISAM、Memory 等多种存储引擎。

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/912494.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ElasticSearch向量检索技术方案介绍

1、背景 在人工智能快速发展的今天,推荐技术、以文搜图、以文搜视频、以图搜图等技术已经得到了广泛的应用,在百度、小红书、抖音、快手等app上随便输入一段文本,搜索结果已不像早些年那么单一:只有一些文字信息,现在的…

MySql中索引为什么用B+树,他有什么特点?时间复杂度是多少?能存多少数据?是不是只能三层?他与B-树有什么不同?还有其它的树你是是否知道?

平衡二叉树 平衡二叉树又被称为AVL树平衡二叉树是一颗空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右子树也是平衡树非叶子节点值大于左子节点值而小于右子节点值非叶子节点最多拥有两个子节点 平衡二叉树的不足之处及时间复杂度 如果每次插入的数据都…

3DMAX城镇建筑区块生成插件TownBlocks使用方法详解

3DMAX城镇建筑区块生成插件TownBlocks使用教程 3DMAX城镇建筑区块生成插件TownBlocks,是一款专为城镇建筑区块生成设计的实用工具,它能够实现从2D轮廓到低多边形城镇建筑群的一键批量转换。该插件不仅操作简便,而且提供了丰富的参数设置选项&…

手机内卷下一站,AI Agent

作者 | 辰纹 来源 | 洞见新研社 2024年除夕夜,OPPO在央视春晚即将开始前举办了一场“史上最短发布会”,OPPO首席产品官刘作虎宣布,“OPPO正式进入AI手机时代”。 春节假期刚过,魅族又公开表示,将停止“传统智能手机…

A021基于Spring Boot的自习室管理和预约系统设计与实现

🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹 赠送计算机毕业设计600…

浮点数二进制在线转换器

具体请前往:浮点数在线转二进制工具--在线将10进制浮点数(float)转化为4字节32位的二进制序列

探索 Python 的新边疆:sh 库的革命性功能

文章目录 **探索 Python 的新边疆:sh 库的革命性功能**第一部分:背景介绍第二部分:sh 库是什么?第三部分:如何安装 sh 库?第四部分:简单库函数使用方法1. 执行 ls 命令2. 使用 grep 搜索文件内容…

【GeoJSON在线编辑平台】(2)吸附+删除+挖孔+扩展

前言 在上一篇的基础上继续开发,补充上吸附功能、删除矢量、挖孔功能。 实现 1. 吸附 参考官方案例:Snap Interaction 2. 删除 通过 removeFeature 直接移除选中的要素。 3. 挖孔 首先是引入 Turf.js ,然后通过 mask 方法来实现挖孔的…

吾店云介绍 – 中国人的WordPress独立站和商城系统平台

经过多年在WordPress建站领域的摸索和探索,能轻松创建和管理各种类型网站的平台 – 吾店云建站平台诞生了。 应该说这是一个艰苦卓绝的过程,在中国创建一个能轻松创建和使用WordPress网站的平台并不容易,最主要是网络环境和托管软件的限制。…

【动手学电机驱动】STM32-FOC(6)基于 IHM03 的无感方波控制

STM32-FOC(1)STM32 电机控制的软件开发环境 STM32-FOC(2)STM32 导入和创建项目 STM32-FOC(3)STM32 三路互补 PWM 输出 STM32-FOC(4)IHM03 电机控制套件介绍 STM32-FOC(5&…

94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删

目录 1.双向链表 2.结构体的定义 3.示意图 3.代码示例 1.双向链表的尾插 示意图 代码 main.c List.h List.c 详细分析代码的执行过程 双向链表的初始化 2.双向链表的打印 代码 3.双向链表的尾删 1.双向链表 以一种典型的双向链表为例:带头双向循环链表(带头:带…

「QT」几何数据类 之 QPoint 整型点类

✨博客主页何曾参静谧的博客📌文章专栏「QT」QT5程序设计📚全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasolid…

黑马点评1 session实现短信验证码登录

1 什么是session cookie的session的应用场景:cookie可以用来保存用户的登陆信息,如果删除cookie则下一次用户仍需要重新登录 session就类似于我们拿到钥匙去开锁,拿到的就是我们个人的信息,一般我们可以在session中存放个人的信息…

[Docker#3] LXC | 详解安装docker | docker的架构与生态

目录 1.LXC容器操作 安装LXC LXC容器操作步骤 2.理论 LXC 是什么? Docker 是什么 Docker 和虚拟机的区别 Docker 和 JVM 虚拟化的区别 Docker 版本 ⭕Docker 官方网站(建议收藏) Docker 架构 生活案例 Docker 生态 Docker 解决…

MySQL数据库专栏(五)连接MySQL数据库C API篇

摘要 本篇文章主要介绍通过C语言API接口链接MySQL数据库,各接口功能及使用方式,辅助类的封装及调用实例,可以直接移植到项目里面使用。 目录 1、环境配置 1.1、添加头文件 1.2、添加库目录 2、接口介绍 2.1、MySql初始化及数据清理 2.1.…

从0开始深度学习(27)——卷积神经网络(LeNet)

1 LeNet神经网络 LeNet是最早的卷积神经网络之一,由Yann LeCun等人在1990年代提出,并以其名字命名。最初,LeNet被设计用于手写数字识别,最著名的应用是在美国的邮政系统中识别手写邮政编码。LeNet架构的成功证明了卷积神经网络在…

如何用C#和Aspose.PDF实现PDF转Word工具

在本篇博文中,我将详细讲解如何用C#实现一个PDF转Word工具。这款工具基于Aspose.PDF库,实现PDF文件转为Word(DOC/DOCX)格式的功能,并通过用户友好的界面和状态提示提升用户体验。希望通过这篇文章帮助大家理解软件的实…

运维技术之文件系统(File System for 0peration and Maintenance Technology)

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 本人主要分享计算机核心技…

IoTDB 与 HBase 对比详解:架构、功能与性能

五大方向,洞悉 IoTDB 与 HBase 的详尽对比! 在物联网(IoT)领域,数据的采集、存储和分析是确保系统高效运行和决策准确的重要环节。随着物联网设备数量的增加和数据量的爆炸式增长,开发者和决策者们需要选择…

【Vue】Vue2和Vue3响应式原理

前言 Vue 3 的核心部分可以分为三个主要模块:Compiler、Reactivity 和 Runtime。响应式的处理逻辑在 Reactivity 部分。 Compiler(编译器):Template > 渲染函数 将 Vue 的模板(Template)转换成 JavaS…