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

本文摘抄自 极客时间【MySQL实战45讲】

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

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

<!-- more -->

常见索引模型

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 要扫描一遍整表来计算有多少行。

本文由博客一文多发平台 OpenWrite 发布!
Image placeholder
Jacian
未设置
  36人点赞

没有讨论,发表一下自己的看法吧

推荐文章
滴滴从KV存储到NewSQL实战

桔妹导读:本文讲诉滴滴在分布式Nosql存储Fusion之上构建NewSQL的实践之路。详细描述Fusion-NewSQL的特性,应用场景,设计方案。1.背景Fusion-NewSQL是由滴滴自研的在

【Golang+MySQL】记一次 MySQL 数据库迁移(一)

【Golang+mysql】记一次mysql数据库迁移(一)文章地址:https://github.com/stayfoo/stayfoo-hub一、准备目标: 腾讯云CVM自建mysql数据迁移到腾

MySQL优化之覆盖索引的使用

查看测试表结构:mysql>showcreatetableim_message\G ***************************1.row**************************

为什么mysql索引要使用B+树,而不是B树,红黑树

我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片

MySQL 性能优化:8 种常见 SQL 错误用法!

1、LIMIT语句分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般DBA想到的办法是在type,name,create_time字段上加组合索引。这样条件排序都

Oracle/云MySQL/MsSQL“大迁移”真相及最优方案

最近一段时间碰到一些数据迁移的项目,如:Oracle迁移到MySQL,MsSQL迁移到MySQL,云MySQL迁移到本地MySQL。对于这方面做了系统的整理。包括:迁移方案的选择、如何跳出迁移遇到的坑

一条SQL语句在MySQL中如何执行的

前两天发了一条SQL慢的原因有哪些,在那篇文章我没有说到优化器之类的,我觉得如果配合一条SQL是如何执行的,会更好,所以特地找了一篇。来源:JavaGuide  |作者:木木匠本篇文章会分析一个sql

mysql 进行update时,要更新的字段中有单引号或者双引号导致不能批量生成sql的问题

前言将数据从一张表迁移到另外一张表的过程中,通过mysql的concat方法批量生成sql时遇到了一个问题,即进行UPDATE更新操作时如果原表中的字段中包含单引号'或者双引号",那么就会生成不正确的

MySQL 中 JSON 字段的使用技巧

mysql5.7.8之后开始原生支持json.在类似mongodb这种nosql数据库中,json存储数据是非常自然的,在mysql中合理的使用json,能够带来极大的便利 Json字段的使用场景 在

Ubuntu18.04 安装 MySQL 以及设置远程访问

安装MySQL sudoapt-getinstallmysql-server sudoaptisntallmysql-client sudoaptinstalllibmysqlclient-dev

基础信息:MySQL 特性

MySQL数据库的优缺点: 关系型数据库管理系统(RDBMS):MySQL是一个典型的关系型数据库管理系统。 易用:MySQL很容易上手。只要你掌握一些简单的SQL知识,就可以构建SQL语句与My

基础信息:什么是 MySQL?

MySQL是一个开源的深受欢迎的关系型数据库管理系统(简称RDBMS)。目前排名第二,仅次于Oracle数据库。 MySQL可以免费下载,但是,还提供了几个付费版本,这些版本提供了附加功能。 顾名思义

MySQL 数据库操作:创建和查看数据库

数据库是数据的集合。MySQL允许我们高效地存储和检索数据库中的数据。在MySQL中,我们可以使用CREATEDATABASE语句创建数据库。但是,如果数据库已经存在,则会引发错误。为了避免该错误,我

MySQL 表结构生成 Markdown 文档 | 工具篇

背景 在实施软件工程的时候,当要将某一版本归档时,需要汇总的文档要求还是比较高的、各类文档齐全,包括项目架构、项目安装、接口等文档,而数据库表结构说明文档亦属于其一。记得很早之前想找一个可以导出MyS

MySQL 数据库操作:删除数据库

使用MySQL的DROPDATABASE命令可以很容易的删除一个数据库。数据库删除的同时,所属的数据表将一起被删除。如果删除的数据库不存在,则会引发错误。为了避免错误的发生,可以在DROPDATABA

MySQL 定时备份

1设置好crontab定时任务备份 #每天备份三次数据库 05,15,22***sh/data/script/alldatabase_back.sh&>/dev/null #每天2点备份 02***s

Laravel-Binlog 扩展(用于实时监听 MySQL 数据变更、数据同步等场景)

Laravel-Binlogv0.2.1 (该扩展当前用于我司测试环境实时同步Mysql数据变更到ElasticSearch,稳定性待测试!!哈哈哈)我司正式环境走的阿里云DTS数据订阅 基于Sw

MySQL 读后总结

一条SQL查询语句是如何执行的? Mysql基本架构示意图Mysql分为Server层和存储引擎层两部分 Server层包括连接器、查询缓存、分析器、优化器、执行器等,涵盖MySQL的大多数核心服务

MySQL 优化笔记

优化方向 SQL优化 sql优化分析 索引优化 优化数据库对象 优化表的数据类型 表拆分(水平、垂直) 反范式 使用中间表 优化mysqlserver mysql内存管理优化 log机制及优化

MySQL 优化笔记

优化方向 SQL优化 sql优化分析 索引优化 优化数据库对象 优化表的数据类型 表拆分(水平、垂直) 反范式 使用中间表 优化mysqlserver mysql内存管理优化 log机制及优化

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

MySQL 安装和配置

MySQL安装和配置 MySQL安装 Mysql安装官网:http://www.mysql.com/ 官网下载:http://dev.mysql.com/downloads/mysql/ 官网5.5下

2019年8月数据库流行度排行:双星闪耀 MySQL 成月度最大赢家

炎炎夏日,DB-Engines的8月榜单已经发布,本月积分MySQL获得了最显著的增长,较上月增加了24分,Oracle获得了18分的增长,Oracle公司的两个王牌产品,闪耀8月。以下是前10名的榜

MySQL是怎么保证数据一致性的

在《写数据库同时发mq消息事务一致性的一种解决方案》一文的方案中把分布式事务巧妙转成了数据库事务。我们都知道关系型数据库事务能保证数据一致性,那数据库到底是怎么设计事务这一特性的呢?一、MySQL事务

《关于MySQL的一些骚操作》

概要回顾以前写的项目,发现在规范的时候,还是可以做点骚操作的。假使以后还有新的项目用到了MySQL,那么肯定是要实践一番的。为了准备,创建测试数据表(建表语句中默认使用utf8mb4以及utf8mb4