索引

索引模型

  • 哈希表

    哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值即Value。但是不可避免的就是哈希冲突，常用的是用拉链法（每个key节点后面拉一个链表）

    缺点：只适用于等值查询的场景

  • 有序数组

    一个按照一定顺序排序的数组，有序数组在等值查询和范围查询场景中的性能就都非常优秀。

    缺点：只适用于静态存储引擎，因为插入删除效率很低。

  • 搜索树

    二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。为了维持O(log(N))的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是O(log(N))。但是二叉树的存储量太低了，所以一般使用的都是N叉树；例如B树、B+树。

InnoDB 的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。

例子：

  • 创表语句：

    1
    2
    3
    4
    5
    6
    7
    8
    mysql> create table T (
    ID int primary key,
    k int NOT NULL DEFAULT 0, 
    s varchar(16) NOT NULL DEFAULT '',
    index k(k))
    engine=InnoDB;

    insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

  • 索引结构：

    image-20230414144202021

  • 查询执行流程：select * from T where k between 3 and 5

    • 在k索引树上找到k=3的记录，取得 ID = 300；
    • 再到ID索引树查到ID=300对应的R3；
    • 在k索引树取下一个值k=5，取得ID=500；
    • 再回到ID索引树查到ID=500对应的R4；(回表操作)
    • 在k索引树取下一个值k=6，不满足条件，循环结束。

索引特性

覆盖索引

覆盖索引主要针对与回表操作的优化，比如上面的操作如果这时只需要查ID的值，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表。通常使用联合索引来实现。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段

最左前缀原则

B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录。不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

正是这种原则，可以对索引的安排有所优化。

  • 如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

    • 例如有了(a,b)联合索引，就可以不需要单独建立a索引

  • 空间问题：

    • 如果a字段比b字段需要更大的空间，可以建立(a,b)联合索引，再单独建立b索引

索引下推

由于最左前缀原则，最左前缀可以用于在索引中定位记录。但有多个条件时，这个时候MySQL 5.6 引入的索引下推优化（index condition pushdown)**， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数**。

例如：联合索引（a, b）查询语句是select * from t where a = 1 and b=2;

这样根据最左前缀原则，会找到所有满足a=1的索引，如果在MySQL 5.6之前，会获取主键ID回表进行再次对比。但是有了索引下推，就可以不用回表继续对比，不满足直接筛掉。