Jean's Blog

一个专注软件测试开发技术的个人博客

0%

MySQL索引

发表于 分类于
学习mysql数据库笔记第五讲

什么是索引

  • 官方定义：一种帮助MySQL提高查询效率的数据结构
  • 索引数据结构：
  • 索引的优点
    • 大大加快数据查询速度
  • 索引的缺点
    1. 维护索引需要耗费数据库资源
    2. 索引需要占用磁盘空间
    3. 当对表的数据进行增删改的时候，因为要维护索引，速度会受到影响

索引常见模型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多中，所以这里引入了索引模型的概念。可以用于提高读写效率的数据结构很多，以下介绍常见也比较简单的数据结构：

  • 哈希表
  • 有序数组
  • 搜索树

哈希表

哈希表是一种以key-value键值存储数据的结构，我们只要输入待查的key键值，就可以查找到对应的value。哈希的思路是把值放在数组中，用一个哈希函数把可以换算炒年糕一个确定的位置，然后把value放在数组这个位置。

不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

下面场景，现在维护一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

image-20220829150912506

图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。

需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

可以设想下，如果要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户，就必须全部扫描一遍了。

所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面身份证号查询名字的例子，以下示例图是使用有序数组实现：

image-20220829151349280

假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。

同时很显然，这个索引结构支持范围查询。要查身份证号在[ID_card_X, ID_card_Y]区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。

仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

搜索树

还是以以上的根据身份证号查找名字的例子，我们使用二叉搜索树来实现的话，示意图如下：

image-20220829152007291

二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。

当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

索引分类

主键索引

设定为主键后数据库会自动建立索引，innodb为聚簇索引，主键索引索引列值不能有空

单值索引

也称：单列索引、普通索引

即一个索引只包含单个列，一个表可以有多个单列索引

唯一索引

索引列的值必须唯一，但允许有空值，唯一索引索引列值可以存着null，但是只能存着一个null

复合索引

即一个索引包含多个列

Full Text 全文索引(My5.7版本之前 只能用于MYISAM引擎)

全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引可以在CHAR、VARCHAR、TEXT类型列上创建。MYSQL只有MYISAM存储引擎支持全文索引

索引的基本操作

主键索引(自动创建)

  • 建表 主键自动创建主键索引

    1
    2
    3
    4
    5
    CREATE TABLE t_user
    (
        id   VARCHAR(20) PRIMARY KEY,
        name VARCHAR(20)
    );

  • 查看索引

    image-20220829154028663

单列索引(普通索引|单值索引)

  • 建表时创建索引

    1
    2
    3
    4
    5
    6
    CREATE TABLE t_user
    (
        id   VARCHAR(20) PRIMARY KEY,
        name VARCHAR(20),
        KEY (name)
    );
    • 注意:随表一起建立的索引索引名同列名一致

  • 建表后创建索引

    1
    CREATE INDEX nameindex ON t_user (name);

  • 查看索引

    image-20220829154126538

  • 删除索引

    1
    DROP INDEX 索引名 ON 表名

唯一索引

  • 建表时创建索引

    1
    2
    3
    4
    5
    6
    CREATE TABLE t_user
    (
        id   VARCHAR(20) PRIMARY KEY,
        name VARCHAR(20),
        UNIQUE (name)
    );

  • 建表后创建索引

    1
    CREATE UNIQUE INDEX nameindex ON t_user(name);

  • 查看索引

    image-20220829154156544

复合索引

  • 建表时创建索引

    1
    2
    3
    4
    5
    6
    7
    CREATE TABLE t_user
    (
        id   VARCHAR(20) PRIMARY KEY,
        name VARCHAR(20),
        age  INT,
        KEY (name, age)
    );

  • 建表后创建索引

    1
    CREATE INDEX nameageindex ON t_user(name,age);

  • 查看索引

    image-20220829154356697

  • 复合索引注意：

    1. 最左前缀（左包含）原则
    2. mysql引擎在查询为了更好利用索引，在查询过程中会动态调整查询字段顺序以便利用索引

面试题：现在一张表有复合索引，name age bir，问以下情况能否使用索引？

  • name bir age — 可以，索引自动会调整为name age bir
  • name age bir — 可以
  • age bir — 不行，缺少左包含原则
  • bir age name — 可以，索引自动会调整为name age bir
  • age bir — 不行，缺少左包含原则

索引的底层原理

思考题

目前有如下表：

  1. 建表

    1
    2
    3
    4
    5
    6
    CREATE TABLE t_emp
    (
        id   INT PRIMARY KEY,
        name VARCHAR(20),
        age  INT
    );

  1. 插入数据

    1
    2
    3
    4
    5
    6
    7
    8
    9
    INSERT INTO t_emp VALUES(5,'d',22);
    INSERT INTO t_emp VALUES(6,'d',22);
    INSERT INTO t_emp VALUES(7,'e',21);
    INSERT INTO t_emp VALUES(1,'a',23);
    INSERT INTO t_emp VALUES(2,'b',26);
    INSERT INTO t_emp VALUES(3,'c',27);
    INSERT INTO t_emp VALUES(4,'a',32);
    INSERT INTO t_emp VALUES(8,'f',53);
    INSERT INTO t_emp VALUES(9,'v',13);

    注意：数据在插入的时候，并没有按数字的顺序插入

  2. 查询

    image-20220829154514642

    查询看到，插入的数据进行了排序

为什么上面数据明明没有按顺序插入,为什么查询时却是有顺序呢?

  • 原因是:mysql底层为主键自动创建索引，会以创建的索引进行排序

  • mysql底层真正存储结构，虽然插入的是无序的，但是底层的数据结构进行了排序

  • 为什么要排序呢?
    • 因为排序之后在查询就相对比较快了 如查询 id=3的我只需要按照顺序找到3就行啦(如果没有排序大海捞针,全靠运气😸!)

image-20220829154550437

为了进一步提高效率mysql索引又进行了优化

  • 就是基于页的形式进行管理索引
  • 如 查询id=4的 直接先比较页 先去页目录中找,再去 数据目录中找

image-20220829154633270

上面这种索引结构称之为B+树数据结构,那么什么是B+树呢?

参考资料：https://www.cnblogs.com/lianzhilei/p/11250589.html

image-20220829154727137

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

上面的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

  1. 非叶子节点只存储键值信息。
  2. 所有叶子节点之间都有一个链指针。
  3. 数据记录都存放在叶子节点中。

  • InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 10^3 10^3 = 10亿 条记录。

  • 实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。注意：顶层页为常驻内存

聚簇索引和非聚簇索引

  • 聚簇索引： 将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据
  • 非聚簇索引：将数据与索引分开存储，索引结构的叶子节点指向了数据对应的位置

注意:在Innodb中，在聚簇索引之上创建的索引称之为主键索引，非聚簇索引都是辅助索引，像复合索引、前缀(普通)索引、唯一索引。辅助索引叶子节点存储的不再是行的物理位置，而是主键值，辅助索引访问数据总是需要二次查找。

image-20220829154753633

InnoDB

  • InnoDB使用的是聚簇索引，将主键组织到一棵B+树中，而行数据就储存在叶子节点上，若使用”where id = 14”这样的条件查找主键，则按照B+树的检索算法即可查找到对应的叶节点，之后获得行数据。
  • 若对Name列进行条件搜索(二次查找)，则需要两个步骤：
    • 第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键。
    • 第二步使用主键在主索引B+树种再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。（重点在于通过其他键需要建立辅助索引）
  • 聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一且非空的索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键（类似oracle中的RowId）来作为聚簇索引。如果已经设置了主键为聚簇索引又希望再单独设置聚簇索引，必须先删除主键，然后添加我们想要的聚簇索引，最后恢复设置主键即可。

MYISAM

  • MyISAM使用的是非聚簇索引，非聚簇索引的两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。

    image-20220829154826093

使用聚簇索引的优势

问题: 每次使用辅助索引检索都要经过两次B+树查找，看上去聚簇索引的效率明显要低于非聚簇索引，这不是多此一举吗？聚簇索引的优势在哪？

  1. 由于行数据和聚簇索引的叶子节点存储在一起，同一页中会有多条行数据，访问同一数据页不同行记录时，已经把页加载到了Buffer中（缓存器），再次访问时，会在内存中完成访问，不必访问磁盘。这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键Id来组织数据，获得数据更快。
  2. 辅助索引的叶子节点，存储主键值，而不是数据的存放地址。好处是当行数据放生变化时，索引树的节点也需要分裂变化；或者是我们需要查找的数据，在上一次IO读写的缓存中没有，需要发生一次新的IO操作时，可以避免对辅助索引的维护工作，只需要维护聚簇索引树就好了。另一个好处是，因为辅助索引存放的是主键值，减少了辅助索引占用的存储空间大小。

聚簇索引需要注意什么?

  • 当使用主键为聚簇索引时，主键最好不要使用uuid，因为uuid的值太过离散，不适合排序且可能出线新增加记录的uuid，会插入在索引树中间的位置，导致索引树调整复杂度变大，消耗更多的时间和资源。
  • 建议使用int类型的自增，方便排序并且默认会在索引树的末尾增加主键值，对索引树的结构影响最小。而且，主键值占用的存储空间越大，辅助索引中保存的主键值也会跟着变大，占用存储空间，也会影响到IO操作读取到的数据量。

为什么主键通常建议使用自增id

聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。如果主键不是自增id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。

什么情况下无法利用索引呢?

  1. 查询语句中使用LIKE关键字
    • 语句中使用 LIKE 关键字进行查询时，如果匹配字符串的第一个字符为“%”，索引不会被使用。如果“%”不是在第一个位置，索引就会被使用。
  2. 查询语句中使用多列索引
    • 多列索引是在表的多个字段上创建一个索引，只有查询条件中使用了这些字段中的第一个字段，索引才会被使用。
  3. 查询语句中使用OR关键字
    • 查询语句只有OR关键字时，如果OR前后的两个条件的列都是索引，那么查询中将使用索引。如果OR前后有一个条件的列不是索引，那么查询中将不使用索引。