浅谈B树 B+树 红黑树

• 二叉查找树（BST）
• • 特性
  • 结构
• 红黑树
• • 定义
  • 结构
  • 性质
  • 变换方式
  • • 1.改变颜色（红变黑，黑变红）
    • 2.左旋
    • 3.右旋
  • mysql索引是否可以使用红黑树
• B树（二叉排序树） B-Tree：B树 N叉的排序树
• • 定义
  • m 阶的定义
  • 结构
  • • 根节点
    • 内部节点
    • 叶子节点
  • 分裂
  • • 分裂示例
• B+树
• • 定义
  • 结构
  • B+Tree和BTree的区别
  • 构建一个B+Tree的过程
  • 每一个结点中是如何决定要存储多少数据的呢
  • 为什么mysql使用B+Tree做索引而不是使用BTree或者是红黑树
• 参考文章

二叉查找树（BST）

特性

1.如果它的左子树不为空，则左子树上结点的值都小于根结点

2.如果它的右子树不为空，则右子树上结点的值都大于根节点

3.子树同样也要遵循以上两点

4.二叉树的遍历方式：前 中 后 层次

5.只要一棵树是二叉搜索树，那么它的中序遍历一定是有序的。

结构

红黑树

定义

一种自平衡的二叉查找树。

结构

性质

1.每个结点不是红色就是黑色

2.不可能有连在一起的红色结点

3.根结点都是黑色root

4.每个红色结点的两个子结点都是黑色；叶子节点都是黑色：出度为0，满足了性质就可以近似为0了。

5.每个叶子节点（NIL）是黑色。 注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点

6.如果一个结点是红色的，则它的子结点必须是黑色的

7.从一个结点到该结点的子孙结点的所有路径上包含相同数目的黑节点。确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树。

变换方式

为了满足红黑树的性质，红黑树有三种变换方式：

1.改变颜色（红变黑，黑变红）

当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）
1）把父节点设为黑色
2）把叔叔结点设为黑色
3）把祖父也就是父亲的父亲设为红色（爷爷）
4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则
           

2.左旋

针对于左旋，但是点上面的子树也要跟着旋转。

当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋以父结点作为左旋。
           

3.右旋

当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树，进行右旋。
1）把父结点变为黑色
2）把祖父结点变为红色
3）以祖父结点旋转（爷爷）
           

总之：

左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。

右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

mysql索引是否可以使用红黑树

首先我们先了解一下磁盘，内存和固态硬盘的速度，从快到慢依次为：内存>固态硬盘>磁盘。原因：在磁盘中存储数据的时候，是一页一页的存储的。每一页可以存储16k左右的数据，且一批数据存储的时候，在磁盘上存储的位置是不连续的。因此从磁盘读取数据的时候，无法连续的获取到数据。如：A和B数据存储在了磁盘上，但是存储到了不同的区间，读取的时候，先获取到了A数据，然后再进行第二次磁盘读取去获取B数据。

因此通过磁盘读取数据的时候，存在两个问题：

1.读取磁盘的次数过多

2.读取磁盘的浪费太多

B树（二叉排序树） B-Tree：B树 N叉的排序树

BTree和B+Tree的参考链接

https://www.jianshu.com/p/ac12d2c83708.

定义

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。（相对于二叉，B树每个内结点有多个分支，即多叉）

B树又可以写成B-树/B-Tree，并不是B“减”树，横杠为连接符，容易被误导

通常我们说m阶的B树，它必须满足如下条件：

每个节点最多只有m个子节点。

每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。

如果根不是叶节点，则根至少有两个子节点。

具有k个子节点的非叶节点包含k -1个键。

所有叶子都出现在同一水平，没有任何信息（高度一致）。

m 阶的定义

一个节点能拥有的最大子节点数来表示这颗树的阶数。

举个例子：

如果一个节点最多有 n 个key，那么这个节点最多就会有 n+1 个子节点，这棵树就叫做 n+1（m=n+1）阶树

结构

B树中一个节点的子节点数目的最大值，用m表示，假如最大值为10，则为10阶，如图

根节点

节点【10】即为根节点，特征：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有俩个子节点（不然就变成单支了）。在m阶B树中（根节点非树中唯一节点），那么有关系式2<= M <=m，M为子节点数量；包含的元素数量 1<= K <=m-1,K为元素数量。

内部节点

节点【13,16,19】、节点【3,6】都为内部节点，特征：内部节点是除叶子节点和根节点之外的所有节点，拥有父节点和子节点。假定m阶B树的内部节点的子节点数量为M，则一定要符合（m/2）<= M <=m关系式，包含元素数量M-1；包含的元素数量 （m/2）-1<= K <=m-1,K为元素数量。m/2向上取整。

叶子节点

节点【1,2】、节点【11,12】等最后一层都为叶子节点，叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。特征：在m阶B树中叶子节点的元素符合（m/2）-1<= K <=m-1。

分裂

红黑树如果不满足红黑树性质的时候，会发生改变颜色，左旋和右旋。同理，B树如果不满足它的性质的时候，会发生分裂。

分裂示例

如上图是一个5阶的B树，此时需要插入8。正常来说会被插入到7和14之间，但是由于该B树是5阶，因此需要进行分裂。分裂过程为：7所在的结点为中间结点，因此将7结点升级为父节点，左侧的1核3作为7的左子节点，右侧的8核14作为7的右子节点。

B+树

定义

mysql的索引主要有两种结构：B+Tree索引和Hash索引。我们平常所说的索引，如果没有特别指明，一般都是指B树结构组织的索引(B+Tree索引)。

结构

B+Tree和BTree的区别

1.叶子结点连接起来了（看第三层）

2.非叶子结点不存储数据

3.数据和结点一样多

从上图中可以看到，在根节点中有两个数据，一个是9，一个是18，9是左子节点的最右侧，18是右子节点的最右侧。在左子节点中：有三个子节点，其中1是最左的子节点的最右侧，8是中间子节点的最右侧，9是右边子节点的最右侧。同理右子节点。因此这样在第三行的结点中，数据便是一个有序的顺序了。

BTree所有的点都会存储数据，那么就会造成空间浪费。没有解决范围查找。B+Tree解决了这个问题：

B+Tree的性质：所有非叶子结点都不存mysql的数据，在叶子结点上加了一个双向链表。

1.每个结点最多有m个子节点

2.除了根节点之外，每个结点至少有m/2个子节点，如果结果除不尽，就向上取整。

3.根节点要么是空，要么是独根，否则至少有2个子节点。

4.有k个子节点的结点必有k个关键码

5.叶子结点的高度一致。

构建一个B+Tree的过程

mysql索引查询的时候有最左原则

假设我们使用了A+B+C建立了联合索引，实际上是使用A作为root结点建立了一个树。当我们查询的时候，根据查询条件中的A=x从root开始查找，找到x之后，在x的子节点中寻找B，然后再找C，这样就走了索引。因此如果在查询条件中没有A的话，就不会走root索引了。

但是如果查询条件是B+C，而没有A的话，其实还是走了索引的，只不过是进行全表扫描所有的索引。

另外：

每一个结点中是如何决定要存储多少数据的呢

首先磁盘中的每一页能够存储的数据大小是16k左右。当我们给mysql建立索引的时候，选择了某一个字段建立索引，这个字段值是有大小的。如果该字段值小，那么每一个结点中能够存储的数量就可以多，如果字段值大，那么每一个结点中能够存储的数量就会小，这样的话，该B+Tree的层级就会很高，不利于快速查找。

为什么mysql使用B+Tree做索引而不是使用BTree或者是红黑树

首先，BTree和红黑树都是在结点上存储数据，而B+Tree的结点只存储索引，只有叶子结点存储数据。

B树的内部节点都是存储实际数据的，增大了节点大小，增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时）

B+树内部节点只作为导向作用，b+树的每个节点的孩子数更多，整个树的高度就更低，大大增加查询效率。

B+树的叶子节点有链表相连，适合范围查询，相邻页直接读取。

在大规模数据存储的时候，红黑树往往出现由于树的深度过深而造成磁盘 IO 读写过于频繁，进而导致效率低下的情况。

B+ 树的深度更小，IO较少，效率更高

参考文章

https://blog.csdn.net/endlu/article/details/51720299.

https://www.cnblogs.com/skywang12345/p/3245399.html.

https://www.jianshu.com/p/e136ec79235c.

https://blog.csdn.net/qq_36610462/article/details/83277524.

https://www.cnblogs.com/lianzhilei/p/11250589.html.