光与影的个人博客

NEUCoder

0%

MySQL索引总结

发表于 更新于 分类于 ，

索引相关知识总结

索引作为数据库的重要知识，在本科的数据库学习中基本没有接触过，在大四找工作准备面试笔试时才了解到这个常考的概念，本博客是对于以往索引相关知识缺失的补足和系统整理。

索引是什么？

A database index is a data structure that improves the speed of data retrieval operations on a database table) at the cost of additional writes and storage space to maintain the index data structure. -Wikipedia

索引(index)是用来加速数据库表数据检索的一种特殊数据结构，其作用类似于目录，通过减少检索过程中的磁盘IO，提升检索效率，索引的优点可以概括为以下三点

  1. 减少服务器需要扫描的数据量
  2. 避免因检索导致的排序和临时表
  3. 将随机I/O变为顺序I/O

索引缺点总结如下：

  1. 索引来源于数据表中的数据，创建和维护索引需要消耗时间（由数据量决定）
  2. 索引会占用额外的存储空间（InnoDB中每个B+树节点为一个数据页，每个数据页占16KB空间）

正因为索引以上的缺点，在设计索引时需要在检索性能、索引大小、索引更新性能几个因素之间进行权衡。

索引按照和数据项的关系可以分为两种：

  1. 聚簇索引（Clustered）：表数据物理上按照索引的逻辑大小排列存储，即按照索引从小到大存储，具有相邻索引值的表项存储在相邻的位置。
    • 由于聚簇索引决定了数据的物理存储方式，一个表上只能定义一个聚簇索引。
    • 聚簇索引对于数据的顺序检索性能有较大的提升，例如排序查找、范围查找等
    • 缺点：由于索引即数据，数据的增删改涉及到数据页的合并和拆分，对性能影响较大；非聚簇索引由于实际存储不需要满足索引定义的顺序，相应的修改影响相对较小
  2. 非聚簇索引（not clustered，二级索引、辅助索引）：区别于聚簇索引，表数据的存储方式和索引的逻辑顺序没有关系，可以以任意顺序存储
    • 这类索引通常应用于非主键列，用来加速JOIN, WHERE, and ORDER BY等操作
    • 联合索引（composite index）是一类特殊的非聚簇索引，即索引的逻辑顺序由多个属性共同决定。例如在(fisrt_name, second_name)上创建的联合索引，会首先比较 fisrt_name 然后比较second_name确定索引的顺序
    • InnoDB中非聚簇索引叶子节点存储的主键值，使用非聚簇索引需要回表操作，即首先在当前索引检索到对应主键值，再通过主键上的聚簇索引检索到对应的数据项。与之不同的是，MyISAM中非聚簇索引叶子节点存储的是对应数据项的物理存储地址。
    • 缺点：InnoDB中由于回表操作，检索效率相较于非聚簇索引更差；

按照索引的性质可以分为四类：

  1. 普通索引

  2. 唯一性索引：unique约束会自动建立唯一性索引

  3. 主键索引：主键上的索引，在InnoDB中主键索引等价于聚簇索引，决定了表数据的存储方式，InnoDB对于主键的处理如下：

    • 有主键，聚簇索引即为主键索引
    • 无主键，InnoDB会使用第一个唯一非空索引作为聚簇索引（unique not null）
    • 全无，InnoDB 会生成一个名为 GEN_CLUST_INDEX（6个字节的长整数） 的隐藏聚簇索引。MyISAM没有聚簇索引。

  4. 全文索引：用于全文搜索，只能用在CHAR、VARCHAR、TEXT属性列上

    1
    SELECT * FROM articles WHERE MATCH (属性列) AGAINST ('查询字符串');

按照排列顺序可以分为：

  1. 升序索引

  2. 降序索引：在MySQL8.0以后开始支持，如果一个查询，需要对多个列进行排序，且顺序要求不一致。在这种场景下，要想避免数据库额外的排序-“filesort”，只能使用降序索引

索引的数据结构

为了加速访问，数据库采用B+Tree作为索引的数据结构，下面分析BTree 和B+Tree的结构和插入删除等操作细节

B-Tree

B-Tree是一种自平衡树形数据结构，B-Tree允许节点拥有两个以上的孩子节点，可以理解为多叉平衡搜索树，B-Tree的结构性质使其适用于存储读写大量数据的存储系统，其查找/删除/插入的(最坏)时间复杂度均为log(n)

m叉B-Tree的定义如下：

  1. 每个节点最多有 $m$ 个孩子节点，即最多$m-1$个key
  2. 每个内部节点（非根和叶子节点）至少有$⌈m/2⌉$个孩子节点，即至少有$⌈m/2⌉ - 1$个key
  3. 每个非叶子节点至少有2个孩子节点
  4. 一个包含k-1个key的非叶子节点有k个孩子节点

B-Tree同样满足搜索树性质，即当前节点key序列中的key大小大于其左边子树元素，小于右边子树元素

B+Tree的插入类似于AVL树，只是在树高平衡操作上有一定的区别：

  1. 首先找到插入元素位置的叶子节点，插入到叶子节点key序列的对应位置中
  2. 若此时叶子节点的key个数达到$m$，则需要进行叶子节点分裂操作
    • 将叶子节点key序列分为三部分[0...m/2 - 1, m/ 2, m/2 + 1...m],左右两边差分为两个叶子节点，中间一个key上推到父亲节点
    • 若上推之后父亲节点key个数达到$m$，同样需要分裂操作
    • 不断重复分裂-上推的循环， 直到结束分裂
  3. 完成插入

B+Tree的删除类似于插入时的反推，需要当前节点从孩子节点借：

  1. 首先找到插入元素位置，删除对应key，若为非叶子节点需要从下‘借’节点
  2. 从删除key位置的左边子树，或者右边子树上推一个最大/最小key，替代对应被删除的key
  3. 相当于将父节点的删除转化为了子节点删除，不断重复上述过程，直到删除转移到叶子节点
  4. 若叶子节点删除后key为空，则需要进行合并操作，类似于上推的逆操作
    • 与相邻叶子节点以及对应的父亲节点合并成为新的叶子节点
    • 若父亲节点不满足性质2，重复上述过程
    • 直到向上传递到对应节点满足性质2

B-Tree应用到数据库中作为索引加速访问

  • 每个key对应一条数据项，每个节点相当于邻近的一系列表项
  • 假设key之间的比较复杂度为为C，相较于普通的二分查找的复杂度log2(N) * C，m叉B-Tree遍历比较key进行查找的复杂度为logm-1(N) * (m-1) * C
  • 由于内存查找比较的速度远远快于从磁盘中读取数据的数据，两者的查找成本区别在于访问磁盘次数，m叉B-Tree的logm-1(N)次远小于二分查找的log2(N)次

B+Tree是B-Tree的变种，相当于只在叶子节点存储数据的B-Tree，两者的主要区别有

  1. B+Tree只在叶子节点存储数据，叶子节点按顺序连接成为双向链表
  2. m阶B+Tree，每个节点最多有 $m$ 个孩子节点，即最多$m$个key
  3. 每个key对应一个孩子节点，孩子节点中的key范围为：[左边key+1,key]

几个概念性问题

  1. 为什么不使用查询插入速度为O(1)的hash索引?
    • hash索引支支持等值比较查询，不支持任何的范围查询，例如where age > 10
    • 若数据分布不均匀，或选取的hash函数不合适，出现大量哈希冲突影响检索和索引维护的成本
    • InnoDB不支持hash索引，但是支持自适应哈希索引（类似于缓存），Memory引擎显式支持哈希索引

  2. 为什么不使用B-Tree而使用B+Tree？

    • B-Tree由于非叶子节点同样存储数据，查询可能在叶子节点或者非叶子节点命中，导致查询性能波动较大，无法预测（Mysql8.0删除缓存的原因）
    • B-Tree的非叶子节点存储数据占用更多的空间，B+Tree在相同节点大小下，能够存储更多key，也就意味着B+Tree的深度更小，查询成本更低
    • B+Tree叶子节点以双向链表形式组织，对于范围查询支持更好

    索引使用

索引的创建分为两种方式

  1. 在创建表时声明约束(主键、唯一、外键)会创建对应的索引

  2. 主动通过CREATE语句在现有的表上添加索引

    1
    CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX indexName ON mytable(column(length));

索引操作示例：

  1. 创建两个表，查看对应约束

    • 创建表

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      mysql> create table department(
          -> dept_id int PRIMARY KEY NOT NULL AUTO_INCREMENT,
          -> dept_name varchar(100) default "待定"
          );
      Query OK, 0 rows affected (0.06 sec)
      mysql> create table empolyee(
          -> emp_id int PRIMARY KEY,
          -> dept_id int, 
          -> phone_num int UNIQUE,
          -> CONSTRAINT FOREIGN KEY(dept_id) REFERENCES department(dept_id)
          -> );
      Query OK, 0 rows affected (0.02 sec)

    • 查看约束：SHOW INDEX FROM 表名

  2. 手动创建索引

    • 同样可使用ALTER ADD
    1
    2
    mysql> create index test_index on employee(phone_num);
    Query OK, 0 rows affected (0.01 sec)

  3. 删除索引

    • 同样可使用DROP INDEX index_name ON table_name
    1
    2
    mysql> alter table employee drop index test_index;
    Query OK, 0 rows affected (0.01 sec)

当检索涉及到指定资源的顺序(order by)、比较(where on等)时，可以考虑使用索引。

索引失效场景

并不是在属性列上设置索引后，所有用到对应属性列的查询都能够用到索引，个人总结索引生效的条件为：检索条件必须为常量，即能够让数据库根据某个值在B+树上逐层深入，而是需要遍历所有数据项确定是否满足where条件。

常见的索引失效场景有：

  1. 查询条件中存在计算函数、类型转换等

    1
    select * from student where left(name, 4) = 'wang'

  2. 不等于(<> ，!=，not like，not null)等条件

    1
    select * from student where name != 'zhangsan'

  3. or前后存在非索引列

    • 因为非索引列需要遍历所有数据项
    1
    select * from student where name = 'zhangsan' or age = 100

  4. 联合索引范围条件右边索引失效

    • 联合索引index(name, age, home)
    • age范围条件，导致该联合索引只能用到前两个属性，相当于index(name, age)
    1
    select * from student where name = '100' and age > 100 and home like "cn%"