一文读懂MySQL中的索引

【虚拟资源买卖网www.cnused.com】源码虚拟资源交易平台,免费开通VIP商户!
吆喝资源网官方客服QQ:787749153官方唯一QQ号码
文字广告位招租      好位置不等人!200元/月

什么是索引

索引是一种数据结构,其作用就是用来提高数据查询效率。比较常用的比喻就是将其类比为书籍的目录。通过目录可以精确的找到某一章节的内容所在页。

在数据量较小的时候使用索引其实也没有什么意义,即使没有索引需要一条一条遍历数据对于计算机来说也并不需要太多时间。而一旦数据量较大,要保证我们能正常的对外提供服务,保证用户使用体验那么索引就是必要的了。

索引类型

索引是一种数据结构,为了应对不同的场景会有多种实现。在MySQL中主要就是Hash索引和B+Tree。

Hash索引

hash相信大家应该都很熟悉,hash是一种key-value形式的数据结构。实现一般是数组+链表的结构,通过hash函数计算出key在数组中的位置,然后如果出现hash冲突就通过链表来解决(拉链法)。当然还有其他的解决hash冲突的方法。hash这种数据结构是很常用的,比如我们系统使用HashMap来构建热点数据缓存,存取效率很好。

hash结构存数据首先通过计算key的hash值来确定其在数组中的位置,如果有冲突就在该数组位置建一个链表。这样很明显有几个问题:

即使是具有相同特征的key计算出来的位置可能相隔很远,连续查询效率低下。即不支持范围查询。

hash索引存储的事计算得到的hash值和行指针,而不存储具体的行值,所以通过hash索引查询数据需要进行两次查询(首先查询行的位置,然后找到具体的数据)

hash索引查询数据的前提就是计算hash值,也就是要求key为一个能准确指向一条数据的key,所以对于like等一类的匹配查询是不支持的。

所以我们可以知道的是hash索引适用于快速选取某一行的数据。

B+Tree结构

从名字上看这明显是一种树结构,在大学期间数据结构的课本上树结构是必讲的。树结构是一种特别重要的数据结构,在很多地方都会使用到。

上面我们说到hash索引无法进行范围查询,在树结构中也有一种方便进行有序查询的结构--二叉搜索树。二叉搜索树的结构中要求父节点的值大于左孩子节点并且小于右孩子节点,如下图:

1564735832(1).png

上图中二叉树的查询的时间复杂度为O(log(n)),当然要保证O(log(n))的时间复杂度就需要保证二叉树时刻保持平衡。

而在MySQL索引中虽然也使用了树结构,但是并不是使用的二叉树。因为在数据库中数据最终都是存放在磁盘上的,而如果树的节点过多的话,那么在节点之间转移会花费较多的时间。在MySQL的实现中选择将更多内容放在同一个节点,对同一个节点的操作转入在内存中完成,减少在外存中节点之间转移的次数,以达到提高效率的目的。这就是B+Tree,在B+Tree的实现中一个三层的树结构就基本上可以满足我们几乎所有的需求了。

本文转自PHP中文网,吆喝网(http://yaoohe.com)搜集整理,如有疑问请联系本站客服!

本文来源网络,其内容均为发表者提供,文章内容系作者个人观点,不代表本站对观点赞同或支持。如需有侵权,请在7日内联系本站客服进行处理,否则视为放弃追究权利,客服QQ:787749153,请注明。
1

发表评论