MySQL索引底层结构为什么选择B+树

╰半橙微兮° 2022-08-28 12:47 204阅读 0赞

### 文章目录 ###

**1.Hash索引**  
Hash索引把数据以hash形式组织起来，因此查找某一条记录的时候，速度非常快。同时.hash算法的索引有个缺点，因为它不是按照大小排序的。所以，它无法按照范围进行查找。

**2.二叉树结构索引**  
二叉树的定义：  
1.任意节点左子树不为空,则左子树的值均小于根节点的值；  
2.任意节点右子树不为空,则右子树的值均大于于根节点的值；  
3.任意节点的左右子树也分别是二叉查找树；  
4.没有键值相等的节点；  
如图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_9_color_FFFFFF_t_70_g_se_x_16]  
很显然，这种结构的树查询最坏的情况就会像一个线性结构，这种结构对I/O的操作次数增加，若想减少查询次数。可以看下最好的状态，平衡二叉树。

**3.平衡二叉树索引（AVL）**  
AVL的必要条件如下：  
1.必须是二叉查找树  
2，每个节点的左子树和右子树的高度差至多为1  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_17_color_FFFFFF_t_70_g_se_x_16]

左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；  
右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。  
进一步研究平衡二叉树，如果要查询10，按照AVL的查找方法，则需要对I/0进行四次操作  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]

而同等数据量的情况下，B树和B+树的查找次数要少。

**4.B树的索引结构**  
1、根节点至少有两个孩子  
2、每个非根节点至少有M/2（上取整）个孩子，至多有M个孩子。  
3、每个非根节点至少有M/2-1(上取整)个关键字，至多有M-1个关键字。并以升序排列；key\[i\]和key\[i+1\]之间的孩子节点的值介于key\[i\]和key\[i+1\]之间。  
4、所有的叶子结点都位于同一层。  
用B树的结构，查找的话，只需要对I/O进行3次操作  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 1]

**5.B+树**  
B+树是B树的一个升级版。  
新增特性  
叶子节点冗余了所有的非叶子节点的key  
每个叶子节点增加了一个指向相龄叶子节点的指针  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 2]

这里可以看到，虽然这里查找10，也只是和B树一样需要操作3次I/O。但是B+树将所有的非叶子节点的索引都存放在叶子节点，并且还增加了顺序访问的指针，每个叶子节点都有指向相邻叶子节点的指针，这样当其他操作或者大量数据查询时，可以大大减少对I/O磁盘的读取操作。

**综上：减少对磁盘的I/O操作，所以选B+树更合适作为数据库的索引。**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/43681843290a4752b7a0a24f707aab12.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b1e80ca29e63402a8b3d315c3535ccbd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d7f82dc35b9e40eab9d97f39ce65f6e0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/da6ebab9f87b4f2c8a78ad6bbaa19316.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/3df0162e0ce44be590935522f6a7ddc1.png