MySQL索引

时间:2024-07-12 07:51:57

什么是索引

索引是一种数据结构,用于快速查询和检索数据,本质是一种排序好的数据结构。
底层数据结构有很多类型,常见的有B树、B+树和Hash、红黑树。
在MySQL中,Innodb和MuIsam都使用B+树作为索引结构。

索引的优缺点

优点

  1. 能够实现快速检索,减少IO次数
  2. 通过创建唯一性索引,能保证数据库表中每一行数据的唯一性。

缺点

  1. 创建和维护索引消耗时间。增删改时索引也需要对应的修改,会降低SQL执行效率。
  2. 消耗空间。(物理文件存储)

底层数据结构

Hash表

哈希表是键值对的集合。
其中使用哈希算法(散列算法)。

哈希算法

一种不可逆的加密算法,在哈希表中,key根据哈希算法得到Index即可快速找到value

Hash冲突

不同的key可能得到相同的Index。
解决方法:链地址法,即将哈希冲突数据存放在链表中。【JDK1.8之前的HashMap使用链地址法,后来引入红黑树】

MySQL中的InnoDB存储引擎不直接支持常规的哈希索引,但存在“自适应哈希索引”。本质上是每一个哈希桶为B+Tree结构,可以存储多个键值对。

缺点

不支持顺序和范围查询。

二叉查找树(BST)

  1. 左子树所有节点的值均小于根节点的值。
  2. 右子树所有节点的值均大于根节点的值。
  3. 左右子树也分别为二叉查找树。

查找性能与平衡程度强相关,在平衡(每个节点左右子树深度差不超过1)时,查询的时间复杂度为O(log2N),最差会退化成O(N)。

AVL树

最早的自平衡二叉查找树。查找、插入、删除的时间复杂度都是logN。
通过旋转操作保持平衡,会有较大的计算开销,降低了写操作的性能。
应用并不多。

红黑树

自平衡二叉查找树,通过颜色变换和旋转实现平衡。

查询效率稍有下降,但增删效率提高。

应用于:TreeMap、TreeSet、JDK1.8的HashMap

B树和B+树

B树全称为多路平衡查找树。

索引类型总结

按数据结构

  • BTree:MySQL中默认和最常用的索引类型。
  • 哈希索引
  • RTree索引:仅支持geometry数据类型,优势在于范围查找。
  • 全文索引:一般不会使用。对文本内容进行分词。可用于CHAR、VARCHAR、TEXT

按底层存储方式

根据索引结构和数据是否存放在一起划分。

  • 聚簇索引:例如InnoDB中的主键索引
  • 非聚簇索引:MyISAM引擎都用非聚簇索引。

按应用维度

  • 主键索引:加速查询+列值唯一(不可以有NULL)+表中只有一个
  • 普通索引:加速查询
  • 唯一索引:加速查询+列值唯一(可以有NULL)
  • 覆盖索引:一个索引包含所有需要查询的字段的值。
  • 联合索引:多列值组成一个索引。
  • 全文索引

主键索引

一张表只能有一个主键,且主键不能为null,不能重复。

二级索引

又称辅助索引/非主键索引。二级索引可以定位主键的位置。

聚簇索引与非聚簇索引

聚簇索引

索引结构与数据一起存放。

优点
  • 查询速度快
  • 对排序查找和范围查找优化
缺点
  • 依赖于有序的数据
  • 更新代价大

非聚簇索引

索引结构与数据分开存放。
二级索引即属于非聚簇索引。
叶子节点不一定存放数据的指针。

优点

更新代价小于聚簇索引

缺点
  • 依赖于有序的数据(同聚簇索引)
  • 可能会二次查询(回表)