欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

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


前言

不得不说数据库里有太多太多需要了解的东西,闲来无事数据库的内容总会有一番新的感悟,无不验证一句话“温故而知新”
数据库中有太多太多的知识,也许在大多数开发的过程中,可能无需了解的太过深入,只需要学会完美的使用即可。但是如何使用才能完美的使用呢?接下来我通过常见的数据库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

相关标签: 数据库 索引