索引

索引是一种用于快速查询和检索数据的数据结构。常见的索引结构有:B树和B+树、Hash

索引优缺点
优点:

  • 使用索引可以加快数据检索速度(大大减少索引数据量)
  • 通过创建唯一索引,可以保证数据库表中每一行数据的唯一性

缺点:

  • 创建和维护索引需要耗费许多时间,当对表中数据进行增删改的时候,如果数据有索引,索引也需要动态修改,会降低SQL的执行效率
  • 索引需要物理文件存储,也会耗费一定空间

大多数情况下,索引查询比全表扫描快,如果数据库的数据量不大,使用索引不一定能带来很大的提升。

索引的底层数据结构
Hash表
哈希表是键值对的集合,通过键(key)即可快速取出对应的值(value),因此哈希表可以快速检索数据(接近O(1))

哈希算法,可以快速找到value对应的index,找到index也就找到对应的value。

hash = hashfunc(key)
index = hash % array_size

hash

哈希算法有hash冲突问题,多个key最后可能得到相同的index。通常解决办法是链地址法。链地址法是将哈希冲突数据存放在链表中。比如HashMap,就是通过链地址法解决冲突的。

为了减少 Hash 冲突的发生,一个好的哈希函数应该“均匀地”将数据分布在整个可能的哈希值集合中。

为什么Mysql没有使用哈希表作索引的数据结构呢

  1. 哈希冲突问题
  2. 哈希索引不支持顺序和范围查询:hash索引不支持顺序和范围查询是最大的缺点。

B树和 B+树
B树也叫B-树,全称是多路平衡查找树,B+树是B树的一种变体。B树和B+树种的B是balance的意思

目前大部分数据库系统及文件系统都采用B树或B+树作为索引结构

B树 B+树

  • B树的所有节点既存放key也存放data,而b+树所有的非叶子节点只存放key,叶子节点存放key和data
  • B树的所有叶子节点都是独立的,B+树的叶子节点有一条引用链指向相邻的叶子节点
  • B树的检索过程相当于对范围内的每个节点的关键字作二分查找,可能没有到叶子节点就检索结束,而B+树检索效率稳定,任何查找都是从根节点到叶子节点的过程,叶子节点的顺序检索很明显
    20210420165409106.png

在MySQL中,MYISAM引擎和InnoDB引擎都是使用B+树作为索引结构,但是,两者实现方式不太一样。

MyISAM引擎中,B+树叶节点的data域存放的是数据的地址,在检索时,首先按照B+树搜索算法搜索引擎,如果指定的key存在,取出其data域的值,然后以data域的值作为地址读取对应的数据记录。 非聚簇索引

InnoDB引擎中,其数据文件本身就是索引文件。树的叶节点data域保存了完整的数据记录。聚簇索引 。如果这个索引的 key 是数据表的主键,主键索引。其余的索引都作为辅助索引,辅助索引的 data 域存储相应记录主键的值而不是地址,这也是和 MyISAM 不同的地方。在根据主索引搜索时,直接找到 key 所在的节点即可取出数据;在根据辅助索引查找时,则需要先取出主键的值,在走一遍主索引。 因此,在设计表的时候,不建议使用过长的字段作为主键,也不建议使用非单调的字段作为主键,这样会造成主索引频繁分裂。

索引类型

主键索引(Primary Key)

数据表的主键列使用的就是主键索引

一张表只能有一个主键,并且主键不能为null,不能重复

在 MySQL 的 InnoDB 的表中,当没有显示的指定表的主键时,InnoDB 会自动先检查表中是否有唯一索引的字段,如果有,则选择该字段为默认的主键,否则 InnoDB 将会自动创建一个 6Byte 的自增主键。

二级索引(辅助索引)

二级索引又称辅助索引,因为二级索引的叶子节点存储的数据是主键。通过二级索引,可以定位主键的位置。

唯一索引,普通索引,前缀索引等索引属于二级索引。

  • 唯一索引:唯一索引也是一种约束。唯一索引的属性列不能出现重复值,但允许数据为NULL,一张表允许创建多个唯一索引。建立唯一索引的目的大部分时候是为了该属性列的数据的唯一性,而不是为了查询效率
  • 普通索引:普通索引的唯一作用就是为了快速查询数据,一张表允许创建多个普通索引,并允许数据重复和NULL。
  • 前缀索引:前缀索引只使用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引,相比普通索引建立的数据更小,因为只取前几个字符
  • 全文索引:全文索引主要是为了减速哦大文本数据中的关键字的信息。是目前搜索引擎数据库使用的一种技术。Mysql5.6 之前只有 MYISAM 引擎支持全文索引,5.6 之后 InnoDB 也支持了全文索引。

二级索引
二级索引

聚集索引和非聚集索引

聚集索引

聚集索引即索引结构和数据存放在一起的索引。主键索引属于聚集索引

Mysql中,InnoDB引擎中,.ibd文件就包含了该表的索引和数据,对于 InnoDB 引擎表来说,该表的索引的每个非叶子节点存储索引,叶子节点存储索引和对应的数据

优点

聚集索引的查询速度非常快,因为B+树本身就是一颗多叉平衡树,叶子节点也都是有序的,定位到索引的节点,就相当于定位到了数据

缺点

  1. 依赖有序的数据:B+树是多路平衡树,如果索引的数据不是有序的,那么就需要在插入的时排序,如果数据是整型还好,如果是是类似字符串或UUID这种又长又难比较的数据,插入和查找的速度肯定比较慢
  2. 更新代价大: 如果对索引列的数据被修改时,那么对应的索引也将会被修改, 而且况聚集索引的叶子节点还存放着数据,修改代价肯定是较大的, 所以对于主键索引来说,主键一般都是不可被修改的。

非聚集索引

非聚集索引就是索引结构和数据分开存放的索引

二级索引属于非聚集索引

MYISAM 引擎的表的.MYI 文件包含了表的索引, 该表的索引(B+树)的每个叶子非叶子节点存储索引, 叶子节点存储索引和索引对应数据的指针,指向.MYD 文件的数据。

非聚集索引的叶子节点并不一定存放数据的指针, 因为二级索引的叶子节点就存放的是主键,根据主键再回表查数据。

优点

更新代价比聚集索引更小。非聚集索引的更新代价没有聚集索引大,非聚集索引的叶子节点是不存放数据的。

缺点

  1. 跟聚集索一样,非聚集索引也依赖于有序数据
  2. 可能会二次查询(回表):也是非聚集索引最大的缺点。当查到索引对应的指针或主键后,可能还需要根据指针或主键再到数据文件或表中查询

20210420165311654.png

聚集索引和非聚集索引
20210420165326946.png

非聚集索引一定回表查询吗?(覆盖索引)

不一定回表查询。

用户准备使用 SQL 查询用户名,而用户名字段正好建立了索引。

SELECT name FROM table WHERE name='ww';

那么这个索引的 key 本身就是 name,查到对应的 name 直接返回就行了,无需回表查询。

即使是 MYISAM 也是这样,虽然 MYISAM 的主键索引确实需要回表, 因为它的主键索引的叶子节点存放的是指针。但是如果 SQL 查的就是主键呢?

主键索引本身的 key 就是主键,查到返回就行了。这种情况就称之为覆盖索引。

覆盖索引

如果一个索引包含(或者说覆盖)所有需要查询的字段的值,则称之为覆盖索引。

覆盖索引即需要查询的字段正好是索引的字段,那么直接根据该索引,就可以查到数据, 而无需回表查询。

如主键索引,如果一条 SQL 需要查询主键,那么正好根据主键索引就可以查到主键。

再如普通索引,如果一条 SQL 需要查询 name,name 字段正好有索引, 那么直接根据这个索引就可以查到数据,也无需回表。

20210420165341868.png

创建索引的注意事项

  1. 选择合适的字段创建索引
  • 不为 NULL 的字段 :索引字段的数据应该尽量不为 NULL,因为对于数据为 NULL 的字段,数据库较难优化。如果字段频繁被查询,但又避免不了为 NULL,建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
  • 被频繁查询的字段 :我们创建索引的字段应该是查询操作非常频繁的字段
  • 被作为条件查询的字段 :被作为 WHERE 条件查询的字段,应该被考虑建立索引。
  • 频繁需要排序的字段 :索引已经排序,这样查询可以利用索引的排序,加快排序查询时间。
  • 被经常频繁用于连接的字段 :经常用于连接的字段可能是一些外键列,对于外键列并不一定要建立外键,只是说该列涉及到表与表的关系。对于频繁被连接查询的字段,可以考虑建立索引,提高多表连接查询的效率
  1. 被频繁更新的字段应该慎重建立索引。
    虽然索引能带来查询上的效率,但是维护索引的成本也是不小的。 如果一个字段不被经常查询,反而被经常修改,那么就更不应该在这种字段上建立索引了。
  2. 尽可能的考虑建立联合索引而不是单列索引。
    因为索引是需要占用磁盘空间的,可以简单理解为每个索引都对应着一颗 B+树。如果一个表的字段过多,索引过多,那么当这个表的数据达到一个体量后,索引占用的空间也是很多的,且修改索引时,耗费的时间也是较多的。如果是联合索引,多个字段在一个索引上,那么将会节约很大磁盘空间,且修改数据的操作效率也会提升。
  3. 注意避免冗余索引
    冗余索引指的是索引的功能相同,能够命中索引(a, b)就肯定能命中索引(a) ,那么索引(a)就是冗余索引。如(name,city )和(name )这两个索引就是冗余索引,能够命中前者的查询肯定是能够命中后者的 在大多数情况下,都应该尽量扩展已有的索引而不是创建新索引。
  4. 考虑在字符串类型的字段上使用前缀索引代替普通索引。
    前缀索引仅限于字符串类型,较普通索引会占用更小的空间,所以可以考虑使用前缀索引带替普通索引。

使用索引的一些建议

  • 对于中到大型表索引都是非常有效的,但是特大型表的话维护开销会很大,不适合建索引
  • 避免 where 子句中对字段施加函数,这会造成无法命中索引。
  • 在使用 InnoDB 时使用与业务无关的自增主键作为主键,即使用逻辑主键,而不要使用业务主键。
  • 删除长期未使用的索引,不用的索引的存在会造成不必要的性能损耗 MySQL 5.7 可以通过查询 sys 库的 schema_unused_indexes 视图来查询哪些索引从未被使用
  • 在使用 limit offset 查询缓慢时,可以借助索引来提高性能

MySQL如何为字段添加索引

  1. 添加主键索引(primary key)
    ALTER TABLE 'table_name' ADD PRIMARY KEY ('column')
  2. 添加UNIQUE(唯一索引)
    ALTER TABLE 'table_name' ADD UNIQUE ('column')
  3. 添加index(普通索引)
    ALTER TABLE 'table_name' ADD INDEX index_name('column')
  4. 添加FULLTEXT(全文索引)
    ALTER TABLE `table_name` ADD FULLTEXT ( `column`)
  5. 添加多列索引
    ALTER TABLE 'table_name' ADD INDEX index_name('column1','column2')

MySQL日志

MySQL日志主要包括错误日志、查询日志、慢查询日志、事务日志、二进制日志等几大类。其中,比较重要的是二进制日志binlog(归档日志) 和 事务日志 redo log(重做日志) 和 undo log(回滚日志)
01.png

redo log

重做日志是InnoDB存储引擎独有的,让MySQL拥有崩溃恢复的能力。

比如MySQL实例挂了或者宕机了,重启时,InnoDB存储引擎会使用redo log 恢复数据,保证数据的持久性和完整性
02.png

MySQL中的数据是以页为单位,查询一条记录,会从硬盘把一页的数据加载出来,加载出来的数据叫做数据页,会放入到Buffer Pool中。后续的查询都是从Buffer Pool中找,没有命中再去硬盘加载,减少硬盘IO开销,提升性能。更新表数据的时候,也是这样,发现在buffer Pool中存在,就直接在buffer Pool中更新数据。然后会把“在某个数据页做了什么修改”记录到重做日志缓存(redo log buffer)中,接着就刷盘到redo log文件里
03.png

理想情况,事务一提交就会进行刷盘操作,但实际上,刷盘的时机是根据策略来进行的。

每条redo记录:表空间号 + 数据页号 + 偏移量 + 修改数据长度 + 具体修改的数据 组成

redo log 刷盘时机

InnoDB存储引擎为redo log 的刷盘策略提供了innodb_flush_log_at_trx_commit 参数,提供三种策略:

  • 0 :设置为0的时候,表示每次事务提交时不进行刷盘操作
  • 1 :设置为1的时候,表示每次事务提交时进行刷盘操作(默认值)
  • 2 :设置为2的时候,表示每次事务提交时将redo log buffer内容写入文件系统缓存 page cache 中

innodb_flush_log_at_trx_commit 参数默认值为1,也就是事务提交时调用fsync对redo log 进行刷盘。

InnoDB存储引擎有一个后台线程,每隔1s,就会把redo log buffer中的内容写到文件系统缓存(page cache),然后调用fsync刷盘。
04.png

也就是说,一个没有提交事务的redo log记录,也可能会刷盘。

事务在执行过程中记录会写入redo log buffer,然后是会被后台线程刷盘
05.png

除了后台线程每秒1次的轮询操作,还有一种情况,当 redo log buffer 占用的空间即将达到 innodb_log_buffer_size 一半的时候,后台线程会主动刷盘。

innodb_flush_log_at_trx_commit=0

06.png
为0时,如果MySQL挂了或者宕机了,可能会有1s的数据丢失

innodb_flush_log_at_trx_commit=1

07.png
为1时,只要事务提交成功,redo log记录就一定在硬盘里,不会任何数据丢失。如果事务执行期间,MySQL挂了或者宕机,这部分日志丢了,事务没有提交,不会有损失

innodb_flush_log_at_trx_commit=2

09.png
为2时,只要事务提交成功,redo log buffer中的内容只写入文件系统缓存(page cache)。仅仅只是MySQL挂了不会有任何数据丢失,如果宕机了,可能会有1s的数据丢失

日志文件组

硬盘上存储的redo log 日志文件不只一个,而是以一个日志文件组的形式出现,每个redo的日志文件大小都一样。采用的是环形数组形式,从头开始写,写到末尾又回头循环写。
10.png

在个日志文件组中还有两个重要的属性,分别是 write pos、checkpoint

  • write pos:当前记录位置,一边写一边后移
  • checkpoint:当前擦除位置,也是往后推移

每次刷盘redo log记录到日志文件组中,write pos位置就会后移更新

每次MySQL加载日志文件组恢复数据时,会情况加载过的redo log记录,并把checkpoint后移更新

write pos 和 checkpoint 之间的还空着的部分可以用来写入新的 redo log 记录。
11.png

如果 write pos 追上 checkpoint ,表示日志文件组满了,这时候不能再写入新的 redo log 记录,MySQL 得停下来,清空一些记录,把 checkpoint 推进一下。
12.png

redo log 小结

思考一个问题: 只要每次把修改后的数据页直接刷盘不就好了,还有 redo log 什么事?

数据页大小是16KB,刷盘比较耗时,可能就修改了数据页里的几 Byte 数据,有必要把完整的数据页刷盘吗?

而且数据页刷盘是随机写,因为一个数据页对应的位置可能在硬盘文件的随机位置,所以性能是很差。

如果是写 redo log,一行记录可能就占几十 Byte,只包含表空间号、数据页号、磁盘文件偏移 量、更新值,再加上是顺序写,所以刷盘速度很快。

所以用 redo log 形式记录修改内容,性能会远远超过刷数据页的方式,这也让数据库的并发能力更强。

binlog

redo log是物理日志,记录内容是在某个数据页上做了什么修改,属于InnoDB存储引擎。

而binlog是逻辑日志,记录内容是语句的原始逻辑,类似于“给ID=2这一行的c字段加1”.属于MySQL server层。

不管用什么存储引擎,只要发生了表数据更新,都会产生 binlog 日志。MySQL数据库的数据备份、主备、主主、主从都离不开binlog,需要依靠binlog来同步数据,保证数据一致性。
13.png
binlog会记录所有涉及更新数据的逻辑操作,并且是顺序写。

记录格式

三种格式,可通过binlog_format参数指定

  • statement
  • row
  • mixed
    指定statement,记录的内容是SQL语句原文。比如执行一条update T set update_time=now() where id=1,记录的内容如下。
    14.png
    同步数据时,会执行的sql语句,update_time = now()会获取当前系统时间,直接执行会导致与原库的数据不一致。为了解决这个问题,需要指定为row,记录的内容不再是简单的sql语句,还包含操作的具体数据,记录如下:
    03.png
    row格式记录的内容看不到详细信息,要通过mysqlbinlog工具解析出来。update_time=now()变成了具体的时间update_time=1627112756247,条件后面的@1、@2、@3 都是该行数据第 1 个~3 个字段的原始值(假设这张表只有 3 个字段)。这样就能保证同步数据的一致性,通常情况下都是指定为row,这样可以为数据库的恢复与同步带来更好的可靠性。但是这种格式,需要更大的容量来记录,比较占用空间,恢复与同步时会更消耗IO资源,影响执行速度。所以就有了一种折中的方案,指定为mixed,记录的内容是前两者的混合。MySQL会判断这条SQL语句是否可能引起数据不一致,如果是,就用row格式,否则就用statement格式。

写入机制

binlog的写入时机很简单,事务执行过程中,先把日志写到binlog cache,事务提交的时候,再把binlog cache写到binlog文件中。因为一个事务的binlog不能被拆开,无论事务多大,也要确保一次性写入,所以系统会给每个线程分配一个块内存作为binlog cache。可以通过binlog_cache_size参数控制单个线程binlog cache大小,如果存储内容超过了这个参数,就要暂存到硬盘(swap)

binlog日志刷盘流程如下:
15.png

  • 上图的 write,是指把日志写入到文件系统的 page cache,并没有把数据持久化到磁盘,所以速度比较快
  • 上图的 fsync,才是将数据持久化到磁盘的操作

write和fsync的时机,可以由参数sync_binlog控制,默认是0。

为0的时候,表示每次提交事务都只write,由系统自行判断什么时候执行fsync。
16.png

虽然性能得到提升,但是机器宕机,page cache里面的 binglog 会丢失。为了安全起见,可以设置为1,表示每次提交事务都会执行fsync,就如同binlog 日志刷盘流程一样。最后还有一种折中方式,可以设置为N(N>1),表示每次提交事务都write,但累积N个事务后才fsync。
17.png

在出现IO瓶颈的场景里,将sync_binlog设置成一个比较大的值,可以提升性能。同样的,如果机器宕机,会丢失最近N个事务的binlog日志。

两阶段提交

redo log 重做日志让InnoDB存储引擎有了崩溃恢复的能力

binlog 归档日志 保证了MySQL集群架构的数据一致性

虽然都是持久化的保证,但重点不同

在执行更新语句过程,会记录redolog 和 binlog两块日志,以基本的事务为单位,redo log在事务执行过程中可以不断写入,而binlog只在提交事务时写入,所以redo log与binlog的写入时机不一样。
18.png

如果 redo log 和binlog两份日志的逻辑不一致,会出现什么问题?

以update语句为例,假设id=2的记录,字段c值是0,把字段c值更新成1,SQL语句为update T set c = 1 where id = 2.

假设执行过程中,写完redo log日志后,binlog日志写期间发生了异常,会出现什么情况?
19.png

由于binlog没写完就异常,所以binlog没有对应的修改记录,因此,之后用binlog日志恢复数据时,就会少一次更新,恢复出来的这一行c值为0,而原库因为redo log日志恢复,这一行c值为1,最终数据不一致。
20.png

为了解决两份日志之间的逻辑一致问题,InnoDB存储引擎使用两阶段提交方案。将redo log的写入拆成了两个步骤prepare和commit,这就是两阶段提交。
21.png

使用两阶段提交后,写入binlog时发生异常也不会有影响,因为MySQL根据redo log日志恢复数据时,发现redo log还处于prepare阶段,并且没有对应binlog日志,就会回滚该事务。
22.png

redo log设置commit阶段发生异常,那会不会回滚事务呢?

不会,会直接提交事务恢复数据。

undo log

要想保证事务的原子性,就需要在异常发生时,对已经执行的操作进行回滚,在MySQL中,恢复机制是通过回滚日志undo log实现的,所有事务进行的修改都会先记录到这个回滚日志中,然后再执行相关的操作,如果执行过程中遇到异常的话,直接利用回滚日志中的信息将数据回滚到修改之前的样子即可。并且,回滚日志会先于数据持久化到磁盘上,这样就保证即使数据库突然宕机,当用户再次启动数据库时,数据库还能够通过查询回滚日志来回滚将之前未完成的事务

MVCC 的实现依赖于:隐藏字段、Read View、undo log。在内部实现中,InnoDB 通过数据行的 DB_TRX_ID 和 Read View 来判断数据的可见性,如不可见,则通过数据行的 DB_ROLL_PTR 找到 undo log 中的历史版本。每个事务读到的数据版本可能是不一样的,在同一个事务中,用户只能看到该事务创建 Read View 之前已经提交的修改和该事务本身做的修改

总结

redo log 保证事务的持久性,undo log 保证事务的原子性,binlog保证数据库的数据的一致性,MySQL数据库的数据备份、主备、主主、主从都离不开binlog,需要依靠binlog来同步数据,保证数据一致性。