mysql索引原理------为什么mysql索引要选择B+树这种数据结构，而不是二叉树，红黑树，B树？

桃扇骨 2023-07-11 11:07 129阅读 0赞

### 文章目录 ###

*  二叉树
 *   *  什么是二叉树
     *  二叉树的结构
 *  红黑树
 *   *  什么是红黑树
     *  红黑树的特性
     *  红黑树的平衡
     *  红黑树的结构
 *  B树
 *   *  什么是B树
     *  B树的结构
 *  B+树
 *   *  什么是B+树？
     *  B+树的特点
 *  什么是mysql中的页
 *   *  计算高度为3的B+树能存放多少记录

# 二叉树 #

## 什么是二叉树 ##

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。  
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

## 二叉树的结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70]  
图片上可以明显看到树的高度是6，如果我们要查询6这个元素的话我们要进行6次查询，这显然不满足实际开发得需求。  
然后是

# 红黑树 #

## 什么是红黑树 ##

红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

## 红黑树的特性 ##

性质1：每个节点要么是黑色，要么是红色。  
性质2：根节点是黑色。  
性质3：每个叶子节点（NIL）是黑色。  
性质4：每个红色结点的两个子结点一定都是黑色。  
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。  
从性质5又可以推出：

性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

## 红黑树的平衡 ##

前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。  
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。  
变色：结点的颜色由红变黑或由黑变红。

## 红黑树的结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 1]  
可以明显的看到同样的元素，在红黑树的存储的高度比二叉树要低，红黑树会同股哟左旋右旋的操作来减少树的高度，从而到达减少我们查询树种元素的次数来提高查询效率，当然这个就满足我们对数据库查询的要求了吗？  
下面我们来看看B树

# B树 #

## 什么是B树 ##

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树

## B树的结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 2]  
图片上可以明显看到，B树和红黑树相比，B树变胖了，一个node上可以存储多分数据，而且B树是多叉树，就是说一个B树的node可以有多个子节点，这相比红黑树又进一步减少了树的高度，当然这还是不满足索引的需要。我们再看看B+树：

# B+树 #

## 什么是B+树？ ##

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

## B+树的特点 ##

特点

1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；

2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。  
为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 3]  
图片上我们可以看到，B+树的数据都会浓郁（）存储在叶子结点，而且叶子结点之间都又指针指向，这会提高查询范围的效率。

所以B+树才是最适合做查询索引的树结构。

# 什么是mysql中的页 #

我们都知道mysql中的数据只存放在磁盘上的，那么我们查询数据的时候会从磁盘上去读取数据，这样读取一次就是一次磁盘IO，一次磁盘IO最多可以读取16K，这就是mysql中的一页。

## 计算高度为3的B+树能存放多少记录 ##

上面说到mysq的中默认一页是16K，我们可以用  
SHOW VARIABLES LIKE ‘innodb\_page\_size’;查到  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 4]  
所以我们B+树的叶子结点也要存储16K的数据，这是为什么呢？因为如果叶子结点数据小于16k，那么我们还是要做一次磁盘IO去读取到内存，这样会造成IO的浪费，如果大于16K我们就需要两次磁盘IO。所以16K最为合适。

在B+树中的非叶子结点最会存储指针和主健，这里我假设在msyql innodb引擎中主健是bigint类型 为8字节，指针为6字节，那么在一棵高度为2的B+树中，非叶子结点能存放的指针数就是16384（16K）/（8+6）=1170  
如果高度为3的话 就是1170^3-1=1170X1170  
（这里可能有些同学有点疑惑为啥是1170X1170，这里很好理解，在根节点能存1170个指针那个每一个指针能指向一个非叶子结点，一个非叶子结点又能存1170个指针，所以是这颗高度为3的B+树总共有1170X1170个指针）  
，这里假设每行记录的大小是1K，一个叶子结点就能存储16行  
所以高度为3的B+树能存储1170X1170X16=21902400行。约等于2.19千万行数据。本文大多手动码字，有描述错误或者不清的地方，请指正。谢谢

本文参考：  
https://zhuanlan.zhihu.com/p/27700617  
https://www.jianshu.com/p/e136ec79235c  
https://www.cnblogs.com/fanBlog/p/11394035.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200305094254779.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200305094605867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200305094937757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200305095330652.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200305115655569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3MDExNDIz,size_16,color_FFFFFF,t_70