【数据库】透彻的了解数据库索引结构

文章目录

• 前言
• 一、谈一谈数据结构

---

前言

不得不说数据库里有太多太多需要了解的东西，闲来无事数据库的内容总会有一番新的感悟，无不验证一句话“温故而知新”
数据库中有太多太多的知识，也许在大多数开发的过程中，可能无需了解的太过深入，只需要学会完美的使用即可。但是如何使用才能完美的使用呢？接下来我通过常见的数据库mysql讨论下如何完美的使用，请大家多多参考。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、谈一谈数据结构

1.1、二叉查找树

问题：比如有一个乱序的集合中有1-10这样的数据，如何查找某一个数据的位置呢？
这也是索引根本的目的。此时，在脑海中众多查找算法中，很快就可以定位到二叉查找树。

如上是乱序生成的一个二叉查找树的一个结构图，不太美观，因为这种树不是一个平衡的结构，比如，查找数字2和查找数字5。

而且，在极端的情况下二叉树可能会有如此情况，极度失衡，这样如果在查找数据10的时候，这个结构丝毫起不到总用。因此，想到了平衡的树形结构，红黑树。

1.2、红黑树

红黑树的结构比普通的二叉树要好看很多了，平衡很多，在查找每个数据时，要查找的次数也基本一致。这时会感觉mysql的索引是不是基于红黑树的结构形成的呢？这种树形结构很好的。但是慢慢的，发现，虽然这个树比较平衡，但是树的深度会慢慢的增加，这时是18个数据，就这么多层，数据库中的数据可能会有好几百万，在百万数据的时候会不会有几万层深度呢？这样一来红黑树也慢慢的吃力了。

1.3、b-tree

就红黑树数据量太多的时候数据深度问题，b-tree对此问题进行优化。如上图，同样18条数据，树的深度得到了明显的优化。其实b-tree在新增数据的时候有一个Max.Degree的设置，通过这样的设置，在树的非叶节点中多个数据。如此的结构即使数据再多，可以通过调节非叶节点的范围来调节树的深度。

1.4、b+tree

在数据查询方面，b-tree已经是非常友好的数据结构了，但是在b+tree再次进行了优化，在叶节点上增加了下一个节点的指针，这样在范围查询或者排序的时候会更加友好。

在mysql中建立索引的时候有选择hash索引和btree索引，其中的btree索引指的是b+tree数据结构。

1.5、hash结构

hash理解起来比较简单，这里可以回想一下java中HashMap的数据结构。hash索引在数据的插入和查找时原理类似。

如上数据3个数据，经过hash之后经过一些列的运算（比如与数组的长度进行取模）之后，得到数组的位置3，然后将数据3放到3后面。如此简单的数据结构可谓查询起来速度也会很快。因为只需要将数据经过同样的运算即可得到数据的位置。
这样看来如果使用hash索引，插入索引为3，数据为x 插入的步骤可以总结为2步

1-》计算hash。2-》插入。

同样查询的步骤也可以有两步

1-》计算索引3的hash。2-》查询到位置的数据为x。

这样看来相比tree型结构速度查询速度快了很多。但是hash索引用的少肯定有hash索引的弊端。弊端总结：

1. hash索引不支持范围查询。这个可以仔细思考hash的数据结构便可得到解释。
2. hash索引不支持排序。毕竟同一个数据后面的链表插入的时候是无序的。
3. 在hash碰撞严重的时候，链表长度过长，查询的效率会逐渐降低。如上如果3条数据在同一个链表中，如果查询索引10中的数据的时候2步就发生了改变。
   3.1. 计算hash得到索引Key在数组中的位置。
   3.2 挨个比对链表的Key和查询的Key。

就如上几个弊端，在数据库索引选择的时候，大部分情况会优先b+tree的结构。虽然单单支出了hash索引的弊端，但是并不是指hash绝对的不好，要知道存在即合理。在需要进行完全匹配的时候，没有范围查询的时候，就可以使用hash索引。手机号，身份证号码是不是就可以试一hash索引呢？

数据结构演示地址

本文地址：https://blog.csdn.net/qq_30285985/article/details/111070617