【MySQL实战45讲】索引部分整理

为什么要有索引?索引的作用是什么?

索引的出现其实就是为了提高数据查询的效率,就像书的目录一样。一本书我们可以通过目录中快速的定位其中的某一个知识点;对于数据库而言索引其实就是它的目录,可以通过索引快速的定位都某一条或多条记录。

常见索引模型

Hash表

哈希表是一个以 键-值(key-value) 存储数据的结构,我们只要输入待查找的值即 key,就可以找到对应的值即 value。

结构特点

把值放在数组里,用一个哈希函数把 key 转换成一个确定的位置,然后把 value 放在数组的这个位置。当多个 key 值经过哈希函数的换算会出现同一个值的情况。这时候会拉出一个链表进行存储。

案例

假设现在维护一个身份证信息和姓名的表,表示根据身份证查找对应的名字,这时对应的哈希索引示意图如下

image.png

图 1 哈希表示意图

图中,User2 和 User4 根据身份证号算出来的值都是 N,所以后边跟了一个链表存储。如果要找到 User2 对应的名字是什么,首先通过哈希函数计算出 ID_card_n2 的值为 N,然后按顺序遍历找到 User2。

在这里四个 ID_card_n 的值并不是递增的,这样做的好处就是增加的时候会很快,直接往后边追加;缺点是数据的存储并不是有序的,所以在做区间查询时会进行全表扫描,速度会非常慢。

哈希表这个结构只适用于等值查询。

有序数组

结构特点

将数据存放到数组中,数据在数组中是按顺序存储的,从左到右依次从大到小或从小到大。

案例

以哈希表中的例子,使用有序数组实现的结果如下

image.png

图 2 有序数组示意图

这里假设身份证是没有重复的,这个数组是按照身份证的递增顺序保存的。这时候如果刷要查询 ID_card_n2 对应的姓名,用二分查找法可以快速定位到这条记录,同时如果要进行范围查询也是很快的,比如要查找身份证号在 [ID_card_X, ID_card_N] 区间的 User,可以先用二分查找法找到 ID_card_X 的值,如果没有则找到大于 ID_card_X 的第一个值,然后向右遍历,知道找到第一个大于 ID_card_N 的值退出循环。

但是往数组中插入一条记录的时候需要挪动后边所有的元素,这样的成本太高,同样的删除一条记录也会导致后边所有的元素往前挪动。

有序数组结构适用于等值和范围查询,但是插入和删除的效率太慢。

二叉搜索树

结构特点

二叉搜索树每个节点大于左儿子小于右儿子。

案例

上文例子,二叉搜索树实现如下

image.png
图 3 二叉搜索树示意图

如果我们要找到 ID_card_n2 的话,根据二叉搜索树的特点,按照图中的搜索顺序依次是:UserA→UserC→UserF→User2。

InnoDB索引模型

InnoDB 使用了 B+ 树索引模型,数据都是存储在 B+ 树中的,每一个索引都对应一棵 B+ 树。

B-Tree

image.png

B树 是一棵多路平衡树且有以下特点:

  1. m阶B树 表示该树每个节点最多有 m 个孩子;
  2. 除根节点和叶子节点外,其它每个节点至少有 ceil(m / 2) 个孩子;
  3. 若根节点不是叶子节点,则至少有两个孩子;
  4. 所有叶子节点都在同一层,叶子节点不包含任何关键字;
  5. 每个叶子节点包含 n 个关键字信息;
    • Ki(i = 1…n) 为关键字,且关键字按顺序升序排序 k(i-1)<Ki;
    • Pi 为指向子树根的节点,且指针 P(i-1) 指向子树中所有节点的关键字均小于 Ki,但都大于 K(i-1);
    • 关键字个数 n 必须满足: ceil(m / 2) - 1 <= n <= m-1

image.png

B+树作为数据库索引的优势

image.png

B+ Tree 是在 B-Tree 基础上的优化,使其更适合实现外存储索引结构,InnoDB引擎就是基于它实现索引结构,B+Tree 相对于 B-Tree 的优势:

  1. B+树的磁盘读取代价低:B+树 所有的内部节点没有关键字的具体信息(只存储了key的信息),这样可以使内部节点相对更小。一个硬盘块中包含的节点信息越多,一次性读取内存中的关键字也就越多,相对来说就是 IO 读写次数的降低,也可以说是每次 IO 操作的可观看数据也就越多;
  2. B+树便于执行扫库操作:B树在分支节点上都保存着数据,要找到具体的顺序数据,必须用中序遍历的方式按序扫库;由于B+树的数据都存储在叶子节点上,所有节点均为索引,所以 B+树 直接从叶子节点挨个扫一遍就完了;B+树 支持范围查询(rang-query)非常方便,而B树不支持;
  3. B+ 树查询效率更加稳定:由于 B+树 的数据都存储在叶子节点上,分支节点均为索引,所以对于任意关键字的查找都必须从根节点走到分支节点,所有关键字查询路径长度相同,每个数据的查询效率差不多。对于 B树 而言,分支节点也保存有数据,对于每一个数据的查询所走的路径长度也是不一样的,效率也就不一样;

B+Tree 与 B-Tree 的不同

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

索引维护

image.png

B+树 为了维护索引的有序性,在插入新值的时候需要做必要的维护,如果插入新的行 ID 值为 700,则只需要在 R5 的记录后插入一个新的将是。如果插入值的 ID 为400,需要逻辑上挪动后面的数据,空出位置。

如果 R5 所在的数据页已经满了,根据 B+树 的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去,这个过程称为页分裂。页分裂还会影响数据页的利用率,原本在一个页的数据,现在分到两个页中,整体的空间利用率降低大约 50%。

当相邻的两个页由于删除了数据,利用率很低之后,会将数据页做合并,合并的过程可以认为是分裂过程的逆过程。

关于索引重建

对于以下这两个重建索引的作法,说出你的理解。如果有不合适的,为什么,更好的方法是什么?

// 方案1
alter table T drop index k;
alter table T add index(k);
// 方案2
alter table T drop primary key;
alter table T add primary key(id);

为什么重建索引?

索引可能因为删除,或者页分裂等原因,导致数据页有空洞,重建索引的过程会创建一个新的索引,把数据按顺序插入,这样页面的利用率最高,也就是索引更紧凑、更省空间。

解答

重建主键的过程不合理:

  1. 不论是删除还是创建主键都会整个表重建
  2. 连续执行两个语句,相当于第一个语句白做
  3. 两个语句可以使用 alter table T engine=InnoDB 代替

索引类型

主键索引

主键索引叶子节点中存储的是整行数据,从物理结构的角度也叫 聚簇索引

非主键索引

  • 非主键索引的叶子节点存储的是主键的值,从物理存储的角度也叫 二级索引
  • 二级索引存储主键,是为了减少出现行移动或数据页分裂时二级索引的维护工作,但会让二级索引占用更多的空间。

基于主键索引和普通查询的查询的区别

  • 主键索引:只需要搜索主键这棵树。
  • 普通索引:先搜索普通索引对应的树得到ID,在根据ID在主键索引的树上找到对应的数据,这个过程称为回表。

聚簇索引的注意点有哪些?

聚簇索引最大限度的提高了 IO 密集型应用的性能,但它也有限制:

  1. 插入速度严重依赖于插入顺序,按照主键的顺序插入是最快的,否则会出现页分裂,严重影响性能。所以一般 InnoDB 表,都会定义一个自增的id作为主键。

    面试问题:为什么主键需要自增ID,或者为什么主键需要带有时间行关联。

  2. 更新主键的代价很高,因为将会导致被更新的行移动。因此,InnoDB表一般主键不可更新。

    MySQL默认情况下,主键是允许更新的。MongoDB主键是不允许更新的。

  3. 二级索引访问需要回表。

    有种情况无需二次查找,就是索引覆盖。

  4. 主键ID建议使用整型。因为,每个主键索引的 B+Tree 节点的键值可以存储更多主键ID,每个非主键索引的 B+Tree 节点的数据可以存储更多的主键ID。

什么场景适合使用业务字段直接做主键?

  • 只有一个索引
  • 该索引必须有唯一索引
  • KV场景,由于没有其他索引,所以不用考虑其他索引的叶子节点大小的问题
  • 此时直接将这个索引设置为主键,可以避免回表

覆盖索引

如果执行的语句是 select ID from T where k between 3 and 5; ,这时只需要查 ID 的值,而ID的值已经在 k 索引树上了,因此可以直接拿到查询结果,不需要回表。也就是说索引 k 已经覆盖了我们的查询需求,我们称为覆盖索引

覆盖索引的优势

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

联合索引

业务例子

一个市民信息表上,是否有必要将身份证号 和 名字 建立联合索引?

如果有一个高配请求,要根据市民的身份照查询他的姓名,这个联合索引就很有意义了。它可以在这个高配请求上用到覆盖索引,不需要回表。

最左前缀原则

image.png

前提

现在有这么一个联合索引,(name,age)。

索引项是按照索引定义里面出现的字段顺序排序的,不只是索引的全部定义,只要满足最左前缀,就可以利用索引来加速检索。

  • 这个最左前缀可以是联合索引的最左N个字段
  • 也可以是字符串索引的最左M个字符

例子

  • 查询条件 name='张三',可以快速定位到 ID4,然后向后遍历得到所有的结果集
  • 查询条件 name like '张%' 时,此时也可以用上索引,查找到 ID3,然后向后遍历得到所有结果集

建立索引时,如何安排索引内的字段排序?

  • 原则是,如果通过调整顺序,可以少维护一个索引,name这个顺序往往就是需要优先考虑采用的。
  • 如果既有联合索引,又有基于 a、b 各自的查询。查询条件里只有 b 的查询,是无法使用 (a, b) 这个联合索引的,此时就要同时维护 (a, b) ,(b) 这两个索引。
  • 考虑空间问题,比如市民表,name 字段比 age 字段大,建议创建一个 (name, age) 和一个 (age)

索引创建合理性例子

create table `geek` (
    `a` int(11) not null,
    `b` int(11) not null,
    `c` int(11) not null,
    `d` int(11) not null,
    primary key (`a`, `b`),
    key `c` (`c`),
    key `ca` (`c`, `a`),
    key `cb` (`c`, `b`),
) engine=InnoDB;

既然主键包含了a、b这两个字段,那意味着单独在字段c上创建一个索引,就已经包含三个字段了,为什么要创建“ca”、“cb”这两个索引?

同事告诉他,是因为他们的业务里面有这样的两种语句:

select * from geek where c=N order by a limit 1;select * from geek where c=N order by b limit 1;

问题,这位同事解释的对吗,为了这两个查询模式,这两个索引是否都是必须的?为什么?

  • 索引ca 的组织是先按c 排序,再按a 排序,同时记录主键,主键部分只有b,这个跟索引c的排序结果是一样的
  • 索引cb 的组织是先按c 排序,再按b 排序,同时记录主键,主键部分只有a
  • 所以,ca 可以去掉,cb 需要保留

索引下推

此处还是以市民表的联合索引 (name, age) 为例,需求为 检索出表中 名字第一个字是张,而且年龄是 10岁的所有男孩。

select * from tuser where name like '张%' and age=10 and ismale=1;

根据最左前缀原则,这个语句在搜索索引树的时候,只能用 “张”,找到一个满足条件的记录 ID3。然后判断其他条件是否满足条件。

在 MySQL5.6 之前,只能从 ID3 开始一个个的回表,到主键索引上找出数据行,在对比字段。

image.png

在 MyQL5.6 之后引入了索引下推优化(index condition pushdown),可以在索引遍历的过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,从而减少了回表的次数。

image.png

MyISAM索引实现

索引实现原理

MyISAM 引擎同 InnoDB 一样,都是使用 B+Tree 作为索引结构。差别在于:

  • InnoDB 的数据文件本身就是索引文件。MyISAM 索引文件和数据文件是分离开的,索引文件仅保存数据记录的地址。

主键索引和辅助索引

image.png

image.png

上图分别为主索引和辅助索引,由于 MyISAM 的索引文件中仅保存了数据的地址,所以在 MyISAM 中主索引和辅助索引在结构上没有本质的区别,只是主索引要求 key 的唯一性,而辅助索引的 key 是可以重复的。

由于 MyISAM 的 data 域中保存的是数据记录的地址,所以 MyISAM 索引检索的算法为首先按照 B+Tree 搜索算法搜索索引,如果指定的 key 存在,则取出 data 域的值,然后以 data 域的值为地址,读取相应的数据记录。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

MyISAM 与 InnoDB 的区别

  1. 事务处理上

    MyISAM:强调的是性能,查询的速度比 InnoDB 类型更快,但是不提供事务支持。

    InnoDB:提供事务支持。

  2. 外键

    MyISAM:不支持外键。

    InnoDB:支持外键。

  3. MyISAM:只支持表级锁。

    InnoDB:支持行级锁和表级锁,默认是行级锁,行锁大幅度提高了多用户并发操作的性能。InnoDB 比较适合于插入和更新操作比较多的情况,而 MyISAM 则适用于频繁的查询的情况。另外, InnoDB 表的行锁也不是绝对的,如果在执行一个 SQL 语句时, MySQL 不能确定要扫描的范围,InnoDB 表同样会锁全表,例如: update table set num=1 where name like '%aaa%';

  4. 全文检索

    MyISAM:支持全文检索。

    InnoDB:不支持全文检索。

  5. 表主键

    MyISAM:允许没有主键的表存在。

    InnoDB:如果没有主键,则会自动生成一个 6 字节的主键(用户不可见)。

  6. 表的具体行数

    MyISAM: select count(*) from table ,MyISAM 只要简单的读出保存好的行数。因为 MyISAM 内置了一个计数器, count(*) 时它直接从计数器中读。

    InnoDB:不保存表的具体行数,也就是说,执行 select count(*) from table 的时候,InnoDB 要扫描一遍整表来计算有多少行。


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×