关于对索引底层数据结构的理解

淡淡的烟草味﹌ 2024-03-30 12:10 58阅读 0赞

**目录**

我们在谈论索引底层的数据结构之前，我们不妨先想一下索引是什么以及索引存在的作用

Hash

二叉搜索树与二叉平衡树

多叉平衡查找树（B树）

B+树

--------------------

## 我们在谈论索引底层的数据结构之前，我们不妨先想一下索引是什么以及索引存在的作用 ##

> **索引：是一种特殊的文件，包含着对数据库表中所有记录的引用指针，而其的作用也体现的很明确了，我们通过创建索引来达到提高查询效率的目的（创建索引需要一定的空间，而索引的出现是典型空间换时间策略的体现），每种不同的索引均采用了不同的数据结构**

## Hash ##

> **hash的插入和删除效率很高，在大多数情况下能达到O（1）的时间复杂度，但是mysql数据库并没有选择这种数据结构，为什么呢？我们不妨去思考，虽然其时间复杂度很低，但对于hash而言，其创建和添加数据并不是通过排序和比较的方式，所以他不支持做范围查询，大于号小于号 between and 这种操作，是不支持的**

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

![582790cb861d4bc88399395c946cac95.png][]

> **相对于hash这种数据结构而言，虽然它能够实现范围查询，其查找的时间复杂度也相对较低（logN）,但是我们不妨去想一下，数据库采用所以的目的是为了降低多次IO操作所产生的的时间效率，对于二叉搜索树而言，每一层2^n-1(n>=0)个结点，也就是说，随着树越来越高，其IO操作所消耗的时间成本仍然很高，除此之外，二叉搜索树很容易出现的一种情况是出现斜树问题，即所有的结点出现在二叉树的同一侧，在这种情况下使IO的时间复杂度陡然增加，因此引入平衡二叉树**

**平衡二叉树（AVL）**

> **平衡二叉树具有二叉搜索树的所有特点，除此之外，它新增了一个规则：所有树的左右结点的高度差的绝对值不能超过1，通过左旋和右旋的方式实现平衡，但是其仍然无法解决存在大量结点时出现的树高过多而导致的时间复杂度过高的问题**

![b48787f76c4e4b349cda15ee78fb3a9e.png][]

## **多叉平衡查找树（B树）** ##

![a13d10fde25d4fac83099a568d2b91bb.png][]

> **为了解决树高很高的问题，后来出现了多叉树，同一层能够储存多个节点，很大程度上解决了二叉搜索树所存在的问题，虽然多叉树时间效率相对较高且支持范围查询，mysql并没有选择它，而是在他的基础上进行了优化，选择了B+树**

## B+树 ##

![9976fb6f880a43798e0254d4a2560090.png][]

> **我们去说一下B+树的过人之处：**
> 
> **1.B+树通过一层多个节点的引用，控制了树的高度，减少了IO次数，提高了时间效率**
> 
> **2.相对于B树而言，mysql的B+树采用了双向循环列表并且有序，支持范围查询且时间效率较高**
> 
> **3.相对于B树，其每个节点值都在叶子结点上，在同一层进行查询操作，性能相对均衡，也就是在控制树高的情况下，其性能是可控的。**
> 
> **4.只有叶子页点存储了真实完整的数据，非叶子页点，只能了主键(索引)的值和子节点的引用**

[582790cb861d4bc88399395c946cac95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e2a8de253022490c9ea71da746c2b70b.png
[b48787f76c4e4b349cda15ee78fb3a9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/667f4d84d7b6435f97d30ef04ee91209.png
[a13d10fde25d4fac83099a568d2b91bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c6302d772f6d494e9f4892b6453de3c5.png
[9976fb6f880a43798e0254d4a2560090.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/98b9b3ea69904f6a88808308a198b268.png