InnoDB索引的数据结构

深碍√TFBOYSˉ_ 2023-10-13 10:04 62阅读 0赞

#### InnoDB索引的数据结构 ####

*  MySQL中的数据存储在磁盘而不是内存的原因
 *  InnoDB采用B+树作为索引的数据结构的原因
 *  其他数据结构
 *  二叉搜索树和平衡二叉树
 *   *  二叉搜索树
     *  平衡二叉树
 *  B树
 *  B+树
 *   *  相比B树的优势

## MySQL中的数据存储在磁盘而不是内存的原因 ##

内存容量小，而且发生意外时（比如断电或者发生故障重启）会导致数据丢失。

## InnoDB采用B+树作为索引的数据结构的原因 ##

1.  速度：内存寻址>>顺序I/O>随机I/O (使查询速度快，则要减少磁盘I/O次数)。
2.  查询类型：等值查询，范围查询（支持等值查询和范围查询）。

## 其他数据结构 ##

数组：更新操作需要移动元素，效率低。  
链表：虽然它更新的效率比较高，但是查询的时候需要全表查询。  
哈希：只支持等值查询，不支持范围查询。

## 二叉搜索树和平衡二叉树 ##

### 二叉搜索树 ###

**二叉搜索树**：节点的左子树小于该节点，节点的右子树大于该节点的二叉树。

存在一个特殊的情况，可能会演变成一个链表。前面也提到了，链表的查询效率是非常低的，不太符合要求。  
![在这里插入图片描述][9c2587f53f364f149c7e2078f1a5f905.png]

### 平衡二叉树 ###

**平衡二叉树**：在二叉搜索树的基础上，节点的左子树和节点的右子树的高度差不能超过1。

平衡二叉树支持等值查询，也支持范围查询。但是平衡二叉树一个节点只存储一行的数据，当数据量比较大的时候，它的高度就会越来越大，那么磁盘I/O也就会越来越大。所以他是不符合咱们的要求的。  
![在这里插入图片描述][a5838e06d8a74e57a2ef0b4fa0968b08.png]

## B树 ##

平衡的多路搜索树。M阶表示一个节点最多包括M个子节点，平衡二叉树就是二阶B树。  
![在这里插入图片描述][c5be068e00ae46ab8bf541c193ca5db1.png]  
图中最大的子节点数量是3，所以该B树是一个三阶B树。

## B+树 ##

B+树：是B树的变种，既非叶子节点只存储索引，叶子节点存储索引和数据。  
![在这里插入图片描述][09379c4cbfce46f9b89812cbc26e0efa.png]

### 相比B树的优势 ###

1.  B+树在分叶节点上只是存储索引，而B树是既要存储索引又要存储数据。那么他的存储行数一定比B树少。因此B+树可以存储更多的内容。
2.  B树有回旋，假设要查询大于等于1的数，首先咱们定位到叶子，找到1。然后再回去找页3，然后找页12。页12又回去找页3，有一个回旋出现。B+树则没有这个情况的出现。B+树在叶子节点上遍历链表就能查询相关数据。

**参考资料**：[InnoDB索引的数据结构][InnoDB]

[9c2587f53f364f149c7e2078f1a5f905.png]: https://img-blog.csdnimg.cn/9c2587f53f364f149c7e2078f1a5f905.png
[a5838e06d8a74e57a2ef0b4fa0968b08.png]: https://img-blog.csdnimg.cn/a5838e06d8a74e57a2ef0b4fa0968b08.png
[c5be068e00ae46ab8bf541c193ca5db1.png]: https://img-blog.csdnimg.cn/c5be068e00ae46ab8bf541c193ca5db1.png
[09379c4cbfce46f9b89812cbc26e0efa.png]: https://img-blog.csdnimg.cn/09379c4cbfce46f9b89812cbc26e0efa.png
[InnoDB]: https://www.bilibili.com/video/BV1DG4y1q74q/?spm_id_from=333.880.my_history.page.click&vd_source=a1af903e57688df870625021f7f3a7eb