关于对索引底层数据结构的理解-Toy模板网

这篇具有很好参考价值的文章主要介绍了关于对索引底层数据结构的理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

Hash

二叉搜索树与二叉平衡树

多叉平衡查找树（B树）

B+树

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

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

Hash

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

二叉搜索树与二叉平衡树

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

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

平衡二叉树（AVL）

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

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

多叉平衡查找树（B树）

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

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

B+树

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

我们去说一下B+树的过人之处：

1.B+树通过一层多个节点的引用，控制了树的高度，减少了IO次数，提高了时间效率

2.相对于B树而言，mysql的B+树采用了双向循环列表并且有序，支持范围查询且时间效率较高

3.相对于B树，其每个节点值都在叶子结点上，在同一层进行查询操作，性能相对均衡，也就是在控制树高的情况下，其性能是可控的。

4.只有叶子页点存储了真实完整的数据，非叶子页点，只能了主键(索引)的值和子节点的引用文章来源地址https://www.toymoban.com/news/detail-490479.html

到了这里，关于关于对索引底层数据结构的理解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！