MySQL索引

索引：是一种用于快速查询和检索数据的数据结构，本质可以看成是一种排序好的数据结构。

索引的优缺点

优点：

  • 提高查询效率：索引可以大幅减少查询所需扫描的数据量，从而提高查询速度。
  • 加速排序和分组：索引可以加速ORDER BY和GROUP BY操作
  • 保证数据的唯一性：通过创建唯一索引（Unique Index）可以确保数据的唯一性，防止重复数据的插入

缺点：

  • 占用存储空间：索引需要额外的存储空间来维护数据结构，尤其是当表中有大量数据时，索引可能会占用较多的空间。
  • 创建和维护耗时：创建索引需要时间。此外，在数据插入、更新和删除时，索引也需要进行维护，这可能会增加写操作的开销。
  • 可能被误用或失效：如果查询条件不适合使用索引，或者索引设计不合理，可能会导致查询性能下降。

索引底层的数据结构

Hash表

Hash表：是键值对的集合，通过键(key)即可快速计算出对应的值(value)。

优点：

  • 查询效率高：Hash表的查询时间复杂度为O(1)，适合等值查询（=、IN）
  • 适合频繁的插入和删除操作

缺点：

  • 存在Hash冲突：JDK1.8之前HashMap使用链地址法解决哈希冲突，JDK1.8之后使用红黑树解决哈希冲突
  • 不支持顺序和范围查询

MySQL的InnoDB存储引擎不支持常规的哈希索引，但是InnoDB存在一种特殊的自适应哈希索引(Adaptive Hash Index)。
Adaptive Hash Index：在MySQL运行的过程中，如果InnoDB发现：

  • 有很多寻路很长（比如B+树层数太多、回表次数多等情况）的SQL；
  • 有很多SQL会命中相同的页面（Page）。
    InnoDB会在自己的内存缓冲区（Buffer Pool）里，开辟一块区域，建立自适应哈希索引（Adaptive Hash Index），以加速查询。简单来说，Adaptive Hash Index就是InnoDB在运行时基于热点等值查询自动构建的内存哈希加速层，用于绕过B+Tree的部分查找路径，从而提升查询性能。详见MySQL各种“Buffer”之Adaptive Hash Index

二叉查找树（BST）

二叉查找树（Binary Search Tree，BST）：是一种特殊的二叉树，其中每个节点的值都大于其左子树的所有节点的值，并且小于其右子树的所有节点的值。

查找效率：

  • 最优：当二叉查找树是平衡的时候，查询的时间复杂度为 O(log2(N))。
  • 最坏：当二叉查找树不平衡时，树会退化成线性链表，查询效率急剧下降，时间复杂退化为 O(N)。

AVL树

AVL树：是一种自平衡的二叉查找树，满足：每个节点的左子树和右子树的高度差不超过1。

AVL树通过旋转操作来保持平衡，确保查询效率始终为 O(log2(N))。

缺点：每个树节点仅存储一个数据，每次进行磁盘IO只能读取一个节点的数据，效率较低。

红黑树

红黑树：是一种自平衡的二叉查找树，满足以下性质（左中右，根叶黑，不红红，黑路同）：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL节点）是黑色。
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

红黑树的应用还是比较广泛的，TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。对于数据在内存中的这种情况来说，红黑树的表现是非常优异的。

B树&B+树

B树：是一种自平衡的多路搜索树，适用于磁盘存储系统。B树的每个节点可以有多个子节点，并且所有叶子节点都在同一层。
B+树：是B树的一种变体，所有数据都存储在叶子节点中，非叶子节点只存储索引信息。

B树和B+树的区别：

  • B树的所有节点既存放键(key)又存放数据(data)，而B+树只有叶子结点存放key和data，非叶子结点只存放key。
  • B树的叶子节点都是独立的，而B+树的叶子节点通过指针连接成一个链表，方便范围查询。
  • B树检索过程相当于在树中进行二分查找，而B+树任何查找都是从根节点到叶子结点，效率稳定。
  • B树进行范围查询时，首先要找到要查找的上下限，然后再进行范围扫描；而B+树的范围查询只需要对链表进行遍历即可。

主键索引(Primary Key)

主键索引：数据表的主键列使用的就是主键索引，一张数据表只能有一个主键索引，主键索引不允许有NULL值，并且每个值必须唯一。

MySQL的InnoDB中，当没有显示的指定表的主键时，InnoDB会自动先检查表中是否有唯一索引且不允许存在null值的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个6Byte的自增主键。

二级索引

二级索引：叶子结点存储的数据是主键的值，通过二级索引可以定位主键的位置，二级索引又称为辅助索引/非主键索引。

唯一索引、普通索引、前缀索引等索引都属于二级索引。

  • 唯一索引(Unique Index)：索引列不能出现重复的数据，但是允许数据为NULL，一张表允许创建多个唯一索引。
  • 普通索引(Index)：蔚蓝快速查询数据，允许创建多个普通索引，并允许数据重复和NULL。
  • 前缀索引(Prefix)：只适用于字符串类型的数据。前缀索引是用字符串的前几个字符创建索引。
  • 全文索引(Full Index)：主要是为了检索大文本数据中的关键字信息。