红黑树及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 等多种存储引擎。