当前位置:   article > 正文

MySQL索引类型(按数据结构分类)

mysql索引类型

索引是在存储引擎中实现的,而不是在服务器层中实现的。所以,每种存储引擎的索引都不一定完全相同,并不是所有的存储引擎都支持所有的索引类型。

1、树索引

二叉查找树
BST,binary search tree,二叉查找树是一种支持数据快速查找的数据结构,时间复杂度是O(lgn),支持范围查找。致命缺点:极端情况下会退化为线性链表,二分查找也会退化为遍历查找,时间复杂退化为O(N),检索性能急剧下降。在数据库中,数据的自增是一个很常见的形式,比如一个表的主键是 id,而主键一般默认都是自增的,如果采取二叉树这种数据结构作为索引,什么提到的致命缺点,即不平衡状态导致的线性查找的问题必然出现。因此,简单的二叉查找树存在不平衡导致的检索性能降低的问题,是不能直接用于实现MySQL底层索引的。
在这里插入图片描述
红黑树
二叉查找树存在不平衡问题,因此学者提出通过树节点的自动旋转和调整,让二叉树始终保持基本平衡的状态,就能保持二叉查找树的最佳查找性能。基于这种思路的自调整平衡状态的二叉树有 AVL 树和红黑树。

红黑树,自动左旋右旋节点以及节点变色,调整树的形态,使其保持基本的平衡状态,时间复杂度为O(logn),保证查找效率不会明显减低。

但红黑树并没有完全解决退化为链表的这个问题,虽然右倾趋势远没有二叉查找树退化为线性链表那么夸张,但是数据库中的基本主键自增操作,主键一般都是数百万数千万的,若红黑树存在这种问题,对于查找性能而言也是巨大的消耗,我们数据库不可能忍受这种无意义的等待的。
![在这里插入图片描述](https://img-blog.csdnimg.cn/f3b9754a89324c4aa620070b65cbfdc4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAc3RvbmVfbWlu,size_20,color_FFFFFF,t_70,g_se,x_16

AVL树
更为严格的自平衡二叉树 AVL 树。因为 AVL 树是个绝对平衡的二叉树,因此他在调整二叉树的形态上消耗的性能会更多。
AVL 树不存在红黑树的“右倾”问题,大量的顺序插入不会导致查询性能的降低。

AVL 树的优点:
时间复杂度是O(lgn),不错的查找性能,不存在极端的低效查找的情况。
可以实现范围查找、数据排序。
问题
数据库查询数据的瓶颈在于磁盘 IO,如果使用的是 AVL 树,每一个树节点只存储一个数据,一次磁盘 IO 只能取出来一个节点上的数据加载到内存里。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

磁盘IO的特点,从磁盘读取1B数据和1KB数据所消耗时间是基本一样,根据这个思路,在一个树节点上尽可能多地存储数据,一次磁盘 IO就多加载点数据到内存,即B树,B+树的的设计原理。
在这里插入图片描述
B 树
尽可能在一次磁盘 IO 中多读一点数据到内存,反映到树的结构就是,每个节点能存储的 key 可以适当增加。
B树优点:
优秀检索速度,时间复杂度:B 树的查找性能等于O(h*logn),其中h 为树高,n 为每个节点关键词的个数;
尽可能少的磁盘 IO,加快了检索速度;
可以支持范围查找。
如下图就是一颗B-tree,是一颗三路树:
在这里插入图片描述

B+树
B 树和 B+树有什么不同呢?

B 树一个节点里存的是数据,而 B+树存储的是索引(地址),所以 B 树里一个节点存不了很多个数据,但是 B+树一个节点能存很多索引,B+树叶子节点存所有的数据。
B+树的叶子节点是数据阶段用一个链表串联起来,便于范围查找。
B+树节点存储的是索引,在单个节点存储容量有限的情况下,单节点也能存储大量索引,使得整个 B+树高度降低,减少磁盘 IO。其次,B+树的叶子节点是真正数据存储的地方,叶子节点用有序链表连接起来,在范围查找时效率更高。因此MySQL的索引用的就是 B+树,B+树在查找效率、范围查找中都有着非常不错的性能。
在这里插入图片描述

B tree 和 B+ tree
B-Tree能加快数据的访问速度,因为存储引擎不再需要进行全表扫描来获取数据,数据分布在各个节点之中。
B+ tree 是B-Tree的改进版本,同时也是数据库索引索引所采用的存储结构。数据都在叶子节点上,并且增加了顺序访问指针,每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说,进行范围查找时只需要查找两个节点,进行遍历即可。而B-Tree需要获取所有节点,相比之下B+Tree效率更高。

为什么索引结构默认使用B-Tree,而不是hash,二叉树,红黑树?
hash:虽然可以快速定位,但无序,IO复杂度高
二叉树:树的高度不均匀,不能自平衡,查找效率跟数据有关(树的高度),IO代价高
红黑树:树的高度随着数据量增加而增加,IO代价高

问:为什么官方建议使用自增长主键作为索引?
结合B+Tree的特点,自增主键是连续的,在插入过程中尽量减少页分裂,即使要进行页分裂,也只会分裂很少一部分。并且能减少数据的移动,每次插入都是插入到最后。总之就是减少分裂和移动的频率。

绝大多数的存储引擎,比如MyISAM和InnoDB都支持这种索引,但是不同的存储引擎在具体实现时会稍有不同,比如MyISAM会使用前缀压缩的方式对索引进行压缩,InnoDB则不会。

2、Hash索引

哈希索引基于哈希表实现,只有精确索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码,哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希存储在索引中,同时在哈希表中保存指向每个数据的指针。

MySQL中,只有Memory存储引擎显示支持hash索引,是Memory表的默认索引类型,尽管Memory表也可以使用B-Tree索引。Memory存储引擎支持非唯一hash索引,这在数据库领域是罕见的,如果多个值有相同的hash code,索引把它们的行指针用链表保存到同一个hash表项中。
在这里插入图片描述
针对上图的理解:

keys:代表创建索引的列值;
buckets: 就是计算出来的hash值和对应的数据的物理位置组成的hash表;
entries:就是代表具体的数据行;
创建hash索引后,会为每个键值通过特定的算法计算出一个哈希码(hash code),需要注意的是不同的键值计算出来的hash值可能是相同的,例上图上的 John Smith 和Sandra Dee算出来的hash值都是152,然后找到hash值为152在hash表中的存储数据的物理位置,这个位置对应着两条数据也(就是John Smith 521-1234 和Sandra Dee 521-9655),然后再次遍历这两条数据,找到需要的数据,这就解释了为啥hash冲突严重了,hash索引效率降低的原因。
hash索引检索数据的过程(摘杂网络)
当我们为某一列或某几列建立hash索引时(目前就只有MEMORY引擎显式地支持这种索引),会在硬盘上生成类似如下的文件:
在这里插入图片描述
hash值即为通过特定算法由指定列数据计算出来,存储地址即为所在数据行存储在硬盘上的地址(也有可能是其他存储地址,其实MEMORY会将hash表导入内存)。
这样,当我们进行WHERE age = 18 时,会将18通过相同的算法计算出一个hash值==>在hash表中找到对应的储存地址==>根据存储地址取得数据==>最后一步确定这行数据是否是需要查询的数据。
所以,每次查询时都要遍历hash表,直到找到对应的hash值,数据量大了之后,hash表也会变得庞大起来,性能下降,遍历耗时增加;
Hash索引的优缺点
优点:
因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快

缺点:
1、不能避免读取行
哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能的影响并不明显。

2、无法用于排序
哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。

3、无法使用部分索引列匹配查找
哈希索引也不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如,在数据列(A,B)上建立哈希索引,如果查询只有数据列A,则无法使用该索引。

4、只支持等值查找
哈希索引只支持等值比较查询,包括=、IN()、<=>(注意<>和<=>是不同的操作)。也不支持任何范围查询,例如WHERE price>100。

5、存在Hash冲突
访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值却有相同的哈希值)。当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,直到找到所有符合条件的行。

同时,当哈希冲突很多的时候,一些索引维护操作的代价也会很高。例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应行的引用,冲突越多,代价越大。

综上,Hash索引只适用于某些特定的场景(也就是说实际使用中用得非常少-_-!)

InnoDB引擎有一个特殊的功能叫做“自适应哈希索引”。当InnoDB注意到某些索引值被使用得非常频繁时,它会在内存中基于B-Tree索引上再创建一个哈希索引,这样就像B-Tree索引也具有哈希索引的一些优点,比如快速的哈希查找。

查看当前自适应哈希索引的使用状况:ON表示开启自适应哈希索引

SHOW VARIABLES LIKE '%ap%hash_index';
  • 1

创建哈希索引:如果存储引擎不支持哈希索引,则可以模拟像InnoDB一样创建哈希索引,这可以享受一些哈希索引的便利,例如只需要很小的索引就可以为超长的键创建索引。

思路很简单:在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事,因为还是使用B-Tree进行查找,但是它使用哈希值而不是键本身进行索引查找。你需要做的就是在查询的where子句中手动指定使用哈希函数。这样实现的缺陷是需要维护哈希值。可以手动维护,也可以使用触发器实现。

如果采用这种方式,记住不要使用SHA1和MD5作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串,会浪费大量空间,比较时也会更慢。SHA1和MD5是强加密函数,设计目标是最大限度消除冲突,但这里并不需要这样高的要求。简单哈希函数的冲突在一个可以接受的范围,同时又能够提供更好的性能。

如果数据表非常大,CRC32会出现大量的哈希冲突,CRC32返回的是32位的整数,当索引有93000条记录时出现冲突的概率是1%。

处理哈希冲突:当使用哈希索引进行查询时,必须在where子句中包含常量值。

3、空间(R-Tree)索引

MyISAM支持空间索引,主要用于地理空间数据类型,例如GEOMETRY。和B-TREE索引不同,这类索引无须前缀查询。空间索引会从所有到维度来索引数据。查询时,可以有效地使用任意维度来组合查询。必须使用MySQL的GIS相关函数如MBRCONTAINS()等来维护数据。MySQL的GIS支持并不完善,所以大部分人都不会使用这个特性。开源关系数据库系统中对GIS的解决方案做得比较好的是PostgreSQL的PostGIS。

4、全文(Full-text)索引

全文索引是MyISAM的一个特殊索引类型,innodb的5.6以上版本也支持,它查找的是文本中的关键词主要用于全文检索。

全文索引是一种特殊类型的索引,它查找都是文本中的关键词,而不是直接比较索引中的值。全文搜索和其他几类索引匹配方式完全不一样。它有许多需要注意的细节,如停用词、词干和复数、布尔搜索等。全文索引更类似于搜索引擎做的事情,而不是简单的WHERE条件匹配。

在相同的列上同时创建全文索引和基于值对B-Tree索引不会有冲突,全文索引适用于MATCH AGAINST操作,而不是普通的WHERE条件操作。

总结

在这里插入图片描述

B-Tree索引使用最广泛,主流引擎都支持。
哈希索引性能高,适用于特殊场合。
R-Tree不常用。
全文索引适用于海量数据的关键字模糊搜索。

相关链接:
MySQL索引类型(逻辑角度)
MySQL之MVCC实现原理
MySQL 索引底层原理
MySQL之InnoDB中一棵B+树能存多少行数据
MySQL数据库优化的八种方式
MySQL数据库优化-运维角度浅谈

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/193368
推荐阅读
相关标签
  

闽ICP备14008679号