【数据库】透彻的了解数据库索引结构
前言
不得不说数据库里有太多太多需要了解的东西,闲来无事数据库的内容总会有一番新的感悟,无不验证一句话“温故而知新”
数据库中有太多太多的知识,也许在大多数开发的过程中,可能无需了解的太过深入,只需要学会完美的使用即可。但是如何使用才能完美的使用呢?接下来我通过常见的数据库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索引的弊端。弊端总结:
- hash索引不支持范围查询。这个可以仔细思考hash的数据结构便可得到解释。
- hash索引不支持排序。毕竟同一个数据后面的链表插入的时候是无序的。
- 在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
上一篇: 难以言喻的情绪和线条
下一篇: ren 命令在使用通配符时需要注意的地方