强调列的原子性, 数据库表的每一列都是不可分割的原子数据项第二范式
属性完全依赖于主键. 不能存在仅依赖主关键字一部分的属性.第三范式
确保每列都和主键列直接相关, 属性不依赖于其他非主属性. InnoDB与MyISAM
| InnoDB | MyISAM | |
|---|---|---|
| 事务 | 支持 | 不支持 |
| 外键 | 支持 | 不支持 |
| 行锁 | 支持 | 不支持 |
| crash-safe能力 | 支持 | 不支持 |
| MVCC | 支持 | 不支持 |
| 索引存储类型 | 聚簇索引 | 非聚簇索引 |
| 是否保存表行数 | 不保存 | 保存 |
索引 索引模型 哈希模型
哈希表以 键-值对(key - value) 存储数据, key经过哈希函数的换算, 确定其在数组中存储的位置, 但是哈希存在冲突, 可以用采用拉链法来解决哈希冲突.
但是哈希后的数据不是有序的, 如果用于区间查询, 那么就必须一个个哈希查找了, 性能非常低, 所以哈希表这种存储结构只适用于等值查询的场景.
有序数组模型有序数组无论是在等值查询和范围查询的场景都非常优秀, 因为有序可以使用二分法来查找, 时间复杂度是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1NHPDFp5-1650117801138)(https://g.yuque.com/gr/latex?O(logN)]). 范围查找 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0VhPbIKO-1650117801138)(https://g.yuque.com/gr/latex?k)] 条数据, 只需要先二分查找首条数据, 之后向右遍历, 时间复杂度也就是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gHW0pgvb-1650117801139)(https://g.yuque.com/gr/latex?O(klogN)]) .
但是有序数组为了保持有序, 若在中间插入数据时, 必须移动后面所有数据, 成本开销大.
所以, 有序数组索引只适用于静态存储引擎, 保存一些存储后就不会再去修改的数据.
搜索树模型 BST和AVL等二叉树模型BST不管是查询还是更新, 都只需要 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W6MADTg5-1650117801140)(https://g.yuque.com/gr/latex?O(logN)]) 的时间复杂度. 但是BST在某种情况下, 会使得其退化成链表. 如果想让他保持平衡, 那么就可以使用AVL. 对于二叉树来说, 如果数据量十分大, 那么这个层数就会越堆越高, 而数据是存放在磁盘中, 那么意味着要访问非常多的数据块, 就非常影响性能.
B树模型B树是多路搜索树, B树每个结点都存储着数据, 解决了二叉树随数据变大而层数变高导致对磁盘IO时的性能低下问题. 但是很明显, B树还不是最理想的存储结构, 试想一下如果进行范围查询, 对于范围中的数据来说, 那么不是每次都要从根节点开始往下找么, 必然有性能的问题.
B+树于是在基于B树的模型上, 出现了B+树, B+树只有叶子节点是存储数据的, 而其他非叶子节点均为索引, 叶子节点用链表串起来, 且保证了有序. 在范围查询就只需找到其中一个数据, 之后向后遍历即可.
主键索引和非主键索引| TYPE | INDEX | |
|---|---|---|
| id | int | id(primary key) |
| k | int | k |
| name | varchar |
假设有如上表结构, 那么建立起的索引结构如下图
从图中看出, 根据叶子节点内容的不同, 索引类型分为主键索引和非主键索引.
主键索引的叶子节点存储的是整行数据. 在InnoDB里, 主键索引也被称为聚簇索引非主键索引的叶子节点存储的是主键的值. 在InnoDB里, 非主键索引也被称为二级索引 / 非聚簇索引 回表当执行 SELECT * FROM t WHERE id = 500 时, 即主键查询方式, 则需要搜索ID这颗B+树; 当执行 SELECT * FROM t WHERE k = 5 时, 即普通索引查询方式, 则先在k这棵树查找到主键的值, 再从ID这棵树中查找到对应的行.
当我们执行SQL搜索数据时, 如果需要先从非主键索引中查询到主键的值, 再从主键索引中查询到对应的数据, 这个过程就被称为回表. 所以应该尽量使用主键查询.
索引维护 (页分裂与页合并)B+树为了有序性, 需要对插入和删除数据时做出对应的维护. 当插入数据时, 如在上图中插入ID=400的数据, 那么从逻辑上来说, 需要移动后面的数据, 空出位置.
若此时R5所在数据页满了, 则需要申请一个新的数据页, 然后移动部分数据到新数据页中, 这个过程被称为页分裂. 页分裂影响了数据页的空间利用率, 而且在分裂过程中, 性能也会有所影响.
若相邻两个数据页因为删除导致利用率很低后, 那么会将这两个数据页的数据合并到一个数据页中, 这个过程被称为页合并. 即页分裂的逆过程.
覆盖索引如果执行了语句 SELECT id FROM t WHERE k between 3 and 5 时, 只需要查询 id 的值, 而 id 已经在 k 的索引树上, 所以不需要再回表去查询整行, 直接返回查询结果, 索引 k 已经覆盖了这条SQL查询的需求, 被称为 覆盖索引. 覆盖索引能够减少树的搜索次数, 不需要再次回表查询整行, 所以是一个常用的性能优化手段.
最左前缀原则 就是利用索引列中最左的字段优先进行匹配
| TYPE | INDEX | |
|---|---|---|
| id | int | id(primary key) |
| id_card | varchar | id_card |
| name | varchar | (name, age) |
| age | int | |
| ismale | tinyint |
若有如上表结构, 对于INDEX(name, age)来说, 索引树结构如下, 可以看到, 索引项是按照索引定义里面出现的顺序排序的.
对于SQL语句 SELECT * FROM t WHERE name LIKE '张%' 来说, 也是能够用到INDEX(name, age)这个索引的, 只需检索到第一个姓为张的人, 之后向后遍历即可, 所以可以利用最左前缀来加速检索. 最左前缀可以是联合索引的最左N个字段, 也可以是字符串索引的最左M个字符.
其效果和单独创建一个INDEX(name)的效果是一样的, 如果你想使用INDEX(name, age)也想让name也拥有索引INDEX(name), 那么只需保留前者即可, 若通过调整索引字段的顺序, 可以少维护一个索引树, 那么这个顺序就是需要优先考虑采用的. 但如果也有SQL语句条件类似 WHERE age = 1 , 那么最好再维护一个INDEX(age)的索引.
在对字符串创建索引, 如INDEX(name)中, 若字符串非常大, 那么响应的空间使用和维护开销也非常大, 就可以使用字符串从左开始的部分字符创建索引, 减少空间和维护的成本, 但是也会降低索引的选择性. 索引的选择性指的是 : 不重复的索引值和数据表的记录总数(#T)的比值, 范围为 1/#T 到 1 之间, 索引选择性越高则查询效率越高. 对于BLOB, TEXT, VARCHAR等类型的列, 必须使用前缀索引, MySQL不允许索引这些列的完整长度.
先计算完整列的选择性SELECT COUNT(DISTINCT name)/COUNT(1) FROM t在计算不同前缀长度N的选择性 SELECT COUNT(DISCTINCT LEFT(name, N)) / COUNT(1) FROM t看哪个N更靠近1, 进行索引的创建
索引下推
对于SQL语句 SELECT * FROM t WHERE name LIKE '陈%' AND age = 10 , INDEX(name, age) 情况来说
在 MySQL5.6 之前没有引入索引下推优化时, 执行流程如下图, 在定位完name字段的索引后, 需要一条条进行回表查询, 然后再判断其他字段是否满足条件.
而 MySQL5.6 引入了索引下推优化后, 可以在所有遍历过程中, 对索引中包含的字段先进行判断过滤, 然后再进行后续 *** 作, 减少了回表次数.
自适应哈希索引InnoDB中不存在哈希索引, 但是哈希索引确实有利于快速查找, 于是InnoDB引入了"自适应哈希索引", 在某些索引值被使用的非常频繁时, InnoDB会在内存中的B+树结构之上创建一个哈希索引, 用于这些频繁使用的索引值的快速查找, 使得其存有哈希快速查找的特点.
索引相关高频面试题 索引是什么? 索引优缺点? 索引类似于目录, 进行数据的快速定位优点: 加快数据检索速度缺点: 创建索引和维护索引需要消耗空间和时间 MySQL索引类型 按存储结构划分 : B+Tree索引, Hash索引, FULLINDEX全文索引, R-TREE索引按应用层次划分: 普通索引, 唯一索引, 联合索引, 聚簇索引, 非聚簇索引 索引底层实现? 为什么使用B+树, 而不是B树, BST, AVL, 红黑树等等?什么是聚簇索引和非聚簇索引?非聚簇索引一定会回表吗?(不一定, 覆盖索引不会回表)什么是联合索引?为什么需要注意联合索引中的字段顺序?什么是最左前缀原则?什么是前缀索引?什么是索引下推?如何查看MySQL语句是否使用到索引?
EXPLAIN SQL语句
possible_key: 可能用到的索引(可以查看是否有冗余索引)
key: 真正使用到的索引为什么建议使用自增主键作为索引?
(索引维护可能造成页分裂, 自增主键减少数据的移动和分裂)建立索引的原则 建立索引的字段最好为NOT NULL索引字段占用空间越小越好最左匹配原则=和in建立索引时顺序可以任意, 比如a = 1 and b = 2 and c = 3 建立(a, b, c)和(b, a, c)索引效果是一样的, MySQL查询优化器会进行优化建立的索引让索引的选择性尽可能接近1, 唯一索引的索引选择性为1尽量扩展索引, 不要让索引冗余, 如有SQL需要对单个a进行索引, 那么上述条件建立的索引应该为(a, b, c)或(a, c, b)索引列不能参与计算 什么情况下索引失效? 使用 != 或 <>类型不一致导致索引失效函数导致的索引失效, 函数用在索引列时, 不走索引
如
SELECT * FROM t WHERE DATE(create_time) = 'yyyy-MM-dd'运算符导致的索引失效如
SELECT * FROM t WHERE k - 1 = 2, 若有INDEX(k), 则不走索引OR引起的索引失效如
SELECT * FROM t WHERE k = 1 OR j = 2, 若有INDEX(k), 则不走索引, 如果OR连接的时同一个字段, 则不会失效模糊查询导致的索引失效如
SELECT * FROM t WHERE name = '%三', %放字符串字段前匹配不走索引NOT IN, NOT EXISTS导致索引失效
事务
对于一个事务, 要么事务内的SQL全部执行, 要么都不执行
START TRANSACTION;
SELECT balance FROM checking WHERE customer_id = 10233276;
UPDATE checking SET balance = balance - 200.00 WHERE customer_id = 10233276;
UPDATE savings SET balance = balance + 200.00 WHERE customer_id = 10233276;
COMMIT;
整个事务中的所有 *** 作要么全部提交成功, 要么全部失败回滚.一致性
数据库总是从一个一致性状态转换到另一个一致性状态. 在前面的事务中, 一致性确保了, 即使在第三, 四条语句之间时系统崩溃, 支票账户也不会损失200$, 因为事务最终没有提交, 事务中做的修改不会保存至库中.隔离性
通常来说, 一个事务所做的修改在最终提交以前, 对其他事务是不可见的. 当执行第三条语句, 第四条语句尚未开始时, 若此时有另外一个账户汇总程序开始运行, 则其看到的支票账户并没有被减去200$.持久性
一旦事务提交, 则其所做的修改就会永久保存在数据库中.此时即使系统崩溃, 修改的数据也不会丢失. 并发事务带来的问题 脏读 Dirty Read
当一个事务正在访问数据并且对数据进行了修改，而这种修改还没有提交到数据库中，这时另外一个事务也访问了这个数据，然后使用了这个数据。因为这个数据是还没有提交的数据，那么另外一个事务读到的这个数据是“脏数据”，依据“脏数据”所做的 *** 作可能是不正确的丢失修改 Lost to modify
指在一个事务读取一个数据时，另外一个事务也访问了该数据，那么在第一个事务中修改了这个数据后，第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失，因此称为丢失修改不可重复读 Unrepeatable Read
指在一个事务内多次读同一数据。在这个事务还没有结束时，另一个事务也访问该数据。那么，在第一个事务中的两次读数据之间，由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况，因此称为不可重复读. 侧重点为修改.幻读 Phantom Read
幻读与不可重复读类似。它发生在一个事务（T1）读取了几行数据，接着另一个并发事务（T2）插入了一些数据时。在随后的查询中，第一个事务（T1）就会发现多了一些原本不存在的记录，就好像发生了幻觉一样，所以称为幻读. 侧重点为新增或删除. 隔离性与隔离级别 读未提交 Read Uncommitted
在这个级别下, 事务中的修改, 即使没有提交, 对其他事务也是可见的. 可能会导致脏读, 不可重复读或幻读.读提交 Read Committed
一个事务从开始直到提交之前, 所做的任何修改都是对其他事务不可见的. 可能会发生幻读, 不可重复读.可重复读 Repeatable Read (MySQL默认隔离级别)
保证了在同一个事务中多次读取同样的记录的结果是一致的. 可能会发生幻读. InnoDB通过MVCC多并发版本控制来解决幻读问题.串行化 Serializable
最高隔离级别. 强制事务串行执行. 避免幻读问题. SERIALIZABLE会在读取的每一行数据上都加锁, 所以可能导致大量的超时和锁竞争问题. 事务相关高频面试题 什么是事务事务的四个特征MySQL四种隔离级别什么是脏读? 幻读? 不可重复读?事务是如何实现的(原理) ?
redo log 实现原子和持久性
undo log 实现一致性
事务日志 redo log
redo log 是物理日志, 记录的是"在某个数据页做出了什么修改", 属于 InnoDB存储引擎 层面.
当有一条记录需要更新的时候, InnoDB引擎会先把记录写到 redo log 中, 并更新内存, 这时候更新就算完成. 同时, InnoDB引擎会在适当的时候, 将这个 *** 作记录更新到磁盘里面, 往往是系统较为空闲时.
InnoDB的redo log是固定大小的, 如可以配置为一组4个文件, 每个文件1GB, 那么redo log总共就可以记录4GB的 *** 作. 从头开始写, 写到末尾又回到开头循环写.
write pos 是当前记录的位置, 边写边后移, 写到第三号文件末尾后就回到0号文件开头.
checkpoint 是当前要擦除的位置, 也是往后推移并循环的, 擦除记录前要把记录更新到数据文件.
write pos 和 checkpoint 之间是空闲的部分, 可以用来记录新的 *** 作, 如果 write pos 追上 checkpoint ,表示 redo log 满了, 这时不能再执行新的更新, 得停下先擦掉一些记录, 把 checkpoint 推进.
有了 redo log, InnoDB 可以保证即使数据库发生异常重启, 之前提交的记录都不会丢失, 这个能力被称为 crash-safe
binlogbinlog是逻辑日志, 记录的是SQL语句的原始逻辑, 属于 MySQL Server 层面.
binlog 主要用来保证数据的一致性, 在主从等环境下, 需要通过 binlog 来进行数据的同步.
binlog 日志有三种记录格式
statement这个记录的内容是SQL语句的原文, 同步数据时, 会执行记录的SQL语句, 但如果存在
update_time = now() 这种实时性强的SQL语句, 那么两次 *** 作的时间不一样就会导致数据不一致问题.row指定为 row 时, 记录的内容包含了 *** 作的具体数据, 解决了 statement 格式的问题, 但是有数据的存在说明需要空间占用, 恢复与同步时会更消耗 IO 资源, 影响执行速度.mixed
作为以上两种的折中方案, 通过判断SQL语句是否会带来数据不一致问题而采用 statement 或 row 两阶段提交
redo log 让 InnoDB 存储引擎拥有 crash-safe 能力; binlog 保证了 MySQL 集群下的数据一致性.
redo log 在事务执行过程中可以不断写入, 而 binlog 只有在提交事务时才写入, 两者写入时机不同.
假设有一个事务正在执行, 执行过程中已经写入了 redo log, 而提交完后 binlog写入时发生异常, 那么在 binlog 中可能就没有对应的更新记录, 之后从库使用 binlog 恢复时, 导致少一次更新 *** 作. 而主库用 redo log 进行恢复, *** 作则正常. 最终导致这两个库的数据不一致.
于是 InnoDB存储引擎 使用两阶段提交方案 : 将 redo log 的写入拆成了两个步骤 prepare 和 commit
执行事务时写入redo log (这时处于prepare)提交事务之前, 先写入 binlog最后提交事务, 并将 redo log 进行 commit若使用 redo log 恢复数据时, 发现处于 prepare 阶段, 且没有 binlog, 则会回滚该事务. 若 redo log commit 时异常, 但是存在对应 binlog, MySQL还是认为这一组 *** 作是有效的, 并不会进行回滚.
undo log如果需要保证事务的原子性, 就需要在异常发生时, 对已执行 *** 作进行回滚. undo log 会保存事务未提交之前的版本数据, 在执行过程中异常时, 就可以直接利用 undo log 中的信息将数据回滚到未修改之前. 并且 undo log 中的数据可以作为数据的旧版本快照供其他并发事务进行快照读. 在 InnoDB 中也用于实现 MVCC.
事务日志相关高频面试题 介绍下MySQL事务日志? redo log和undo log?什么是binlog?MVCC 一致性非锁定读和锁定读 一致性非锁定读
对于一致性非锁定读(MVCC)的实现, 通常时加一个版本号或时间戳. 查询时, 将当前可见的版本号和对应的版本号进行比对, 若记录的版本号小于可见版本号, 则表示该记录可见.
在 InnoDB 中, 多版本控制(Multi Versioning)就是对非锁定读的实现. 若读取的行正在执行 DELETE 或 UPDATE, 这时读 *** 作不会去等待行锁的释放, 而是读取行的一个快照, 被称为快照读
锁定读也被称为 当前读. 锁定读会对读取到的记录加锁.
select ... lock in share mode : 对记录加 S 锁, 其它事务也可以加 S 锁, 但是加 X 锁会被阻塞select ... for update、insert、update、delete : 对记录加 X 锁
当前读每次读取的都是最新数据, 两次查询中间如果有其他事务插入数据, 就会产生幻读.
MVCC 实现原理MVCC是通过保存数据在某个时间点的快照来实现的. 根据事务开始的时间不同, 每个事务对同一张表, 同一时刻看到数据可能是不一样的.
MVCC实现依赖于: 隐藏字段, Read View, undo log
隐藏字段主要包含:
ROW ID : 隐藏的自增ID, 如果表没有主键, InnoDB 会自动按 ROW ID 产生一个聚簇索引树事务 ID : 记录最后一次修改该记录的事务ID回滚指针 : 指向这条记录的上一个版本InnoDB 每行数据都有一个隐藏的回滚指针, 用于指向该行数据修改前的最后一个历史版本, 这个历史版本会存放在 undo log 中. 如果要执行更新 *** 作, 会将原记录放入 undo log 中, 并通过隐藏指针指向 undo log 中的原记录. 其他事务此时需要查询时, 就是查询 undo log 中这行数据的最后一个历史版本.
但是 undo log 总不可能一直保留. 在不需要的时候它应该被删除, 这时就交由系统自动判断, 即当系统没有比这个 undo log 更早的 read-view 的时候. 所以尽量不要使用长事务, 长事务意味着系统里会存在非常古老的事务视图. 由于这些事务随时可能访问数据库中任何数据, 所以这个事务提交前, 数据库里它可能使用到的 undo log 都必须保存, 导致占用大量存储空间.
RC和RR级别下MVCC的差异 RC级别 : 每次SELECT查询前都生成一个Read ViewRR级别 : 事务开启后第一次SELECT数据前生成一个Read View MVCC + Next-key Lock 防止幻读InnoDB在RR级别下通过 MVCC 和 Next-key Lock 解决幻读问题
**SELECT**, 此时会以 **MVCC** 快照读方式读取数据.在快照读的情况下，RR 隔离级别只会在事务开启后的第一次查询生成
Read View ，并使用至事务提交。所以在生成 Read View 之后其它事务所做的更新、插入记录版本对当前事务并不可见，实现了可重复读和防止快照读下的 “幻读”执行 select…for update/lock in share mode、insert、update、delete 等当前读在当前读下，读取的都是最新的数据，如果其它事务有插入新的记录，并且刚好在当前事务查询范围内，就会产生幻读！
InnoDB 使用 Next-key Lock 来防止这种情况。当执行当前读时，会锁定读取到的记录的同时，锁定它们的间隙，防止其它事务在查询范围内插入数据。只要我不让你插入，就不会发生幻读
MVCC相关高频面试题
了解MVCC吗?说下什么是MVCC?MVCC实现原理? 有什么好处?
锁
根据加锁范围, MySQL里的锁大致分成 全局锁 、表锁 和 行锁
全局锁全局锁就是对整个数据库实例加锁. MySQL提供了一个加全局读锁的方法, Flush tables with read lock(FTWRL) 使整个库都处于只读状态. 一般用于全局备份.
InnoDB中的表锁十分鸡肋, 一般都是通过 MySQL 的 server 层下的 元数据锁 (Metadata Lock) 来实现当对表执行DDL语句时, 使得其他事务阻塞. InnoDB厉害之处是实现了更细粒度的行锁.
仅仅只是把一条记录给锁上, 当一个事务获取了记录的S锁, 其他事务也能够获得S锁, 但无法获得X锁; 而一个事务获取了记录的X锁, 则其他事务不能获得S锁和X锁.Gap Lock 间隙锁
在RR级别下产生幻读问题一般有两种解决方案: MVCC或加锁.
假设有记录id = [1, 3, 4], 这时有事务想在[1, 3]之间插入一个id = 2的记录, 可能产生幻读, 所以给id = 3的记录前的间隙加上了 Gap Lock, 意思是在释放这个 Gap Lock 之前都不允许其他事务在这条记录前插入数据. 那如果在最后一条后插入数据呢 ? 在表最后会有一条伪记录Supremum, 对Supremum加 Gap Lock, 这样就会防止在最后插入记录造成的幻读.Next-Key Lock
有时, 既想锁住某条记录, 又想阻止在记录前的间隙插入新记录. 于是就有了 Next-Key Lock. 本质就是一个Record Lock + Gap Lock.Insert Intention Lock 插入意向锁
若插入位置已被别的事务加了 Gap Lock, 则事务在等待时也需要在内存中生成一个锁结构, 被称为 插入意向锁. 当 Gap Lock 释放的时候,插入意向锁就会将等待事务中锁结构内的 is_waiting 的状态改为 false, 然后开始继续往下执行插入 *** 作.隐式锁
隐式锁其实是一种延迟生成锁结构的方案, 通过判断事务id, 确定两个并发事务之间是否真的有必要加锁, 若需要, 则会生成锁结构, 然后进入等待; 不需要, 那么就没必要浪费内存去对事务生成锁结构, 降低维护成本. 类似于乐观锁实现. 两阶段锁协议
在InnoDB事务中, 行锁是需要的时候才加上的, 但并不是不需要了就立刻释放, 而是等到事务结束时才释放. 这就是 两阶段锁协议
如果事务中需要锁住多行, 要把最可能造成锁冲突、最可能影响并发度的锁尽量往后放. 这样就最大程度减少了事务间的锁等待, 提升了并发度.
锁相关高频面试题 为什么需要加锁?MySQL锁粒度?MySQL有哪些锁?乐观锁和悲观锁是什么?如何实现?InnoDB的行锁是如何实现的?什么是两阶段锁协议?更多文章如下：
【面向校招】全力备战2023Golang实习与校招
欢迎进群共同进步：
QQ群：1007576722
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）