> For the complete documentation index, see [llms.txt](https://yaojun.gitbook.io/cppinterview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yaojun.gitbook.io/cppinterview/di-ceng-xi-tong/shu-ju-ku-yuan-li.md).

# 数据库原理

* 事务（ACID、2PL、T/O、MVCC、2PC、raft）
* 索引（B+）
* 存储（LSM tree、redo log、bin log）
* 副本（CAP）
* 恢复
* 查询计划

## 索引

### 参考视频

* [数据存储与检索](https://www.bilibili.com/video/BV1Zv411G7ty?spm_id_from=333.999.0.0\&vd_source=e9f1ced96b267a4bc02ec41ca31d850a)
* [CMU15-445中文讲解版](https://www.bilibili.com/video/BV1eR4y1W7rW?spm_id_from=333.999.0.0\&vd_source=e9f1ced96b267a4bc02ec41ca31d850a)

### 索引

* 索引是数据表中对字段进行排序的一种数据结构。常用的索引有

1. B+
2. AVL
3. Hash
4. RBtree

* 哈希表不利于范围查找。
* 红黑树在数据量大的时候性能会下降。

### 联合索引

* 对多个字段同时建立的索引。Mysql从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分，跳跃索引查询就会导致索引失效。

### B树

* 关键字所有节点中只出现一次
* 查询可能在非叶子节点结束

### B+树

* [参考文档](https://zhuanlan.zhihu.com/p/98021010)

1. 非叶子节点只存索引。
2. 数据存储在叶节点，
3. 叶节点间使用双向指针相连。

* 优点

1. 查询时间复杂度固定，都在叶子节点结束查询。
2. 非叶子节点索引范围更大。
3. 叶子节点双向链表方便范围查询。
4. 树的高度更低，用在数据库中磁盘IO次数更少。

## 数据库三大范式

1. 数据库中的所有字段都是不可分割的原子值。原子字段。
2. 满足第一范式的前提下，除主键外的每一列都必须完全依赖于主键。如果不完全依赖，只能发生在联合主键下。仅依赖主键。
3. 满足第二范式的前提下，除开主键列的其他列之间不能有传递依赖关系。各列无传递依赖。

## 事务

### 事务的特性

1. 原子性（Atomicity）： 事务是最小的执行单位，不允许分割。事务的原子性确保动作要么全部完成，要么完全不起作用；
2. 一致性（Consistency）： 执行事务前后，数据保持一致，多个事务对同一个数据读取的结果是相同的；
3. 隔离性（Isolation）： 并发访问数据库时，一个用户的事务不被其他事务所干扰，各并发事务之间数据库是独立的
4. 持久性（Durability）： 一个事务被提交之后。它对数据库中数据的改变是持久的，即使数据库发生故障也不应该对其有任何影响。

### 隔离级别

1. READ-UNCOMMITTED(读取未提交)： 最低的隔离级别，允许读取尚未提交的数据变更，可能会导致脏读、幻读或不可重复读。
2. READ-COMMITTED(读取已提交)： 允许读取并发事务已经提交的数据，可以阻止脏读，但是幻读或不可重复读仍有可能发生
3. REPEATABLE-READ(可重复读)： 对同一字段的多次读取结果都是一致的，除非数据是被本身事务自己所修改，可以阻止脏读和不可重复读，但幻读仍有可能发生
4. SERIALIZABLE(可串行化)： 最高的隔离级别，完全服从ACID的隔离级别。所有的事务依次逐个执行，这样事务之间就完全不可能产生干扰，也就是说，该级别可以防止脏读、不可重复读以及幻读

### 不同隔离级别存在的问题

1. 脏读（Dirty read）: 当一个事务正在访问数据并且对数据进行了修改，而这种修改还没有提交到数据库中，这时另外一个事务也访问了这个数据，然后使用了这个数据。因为这个数据是还没有提交的数据，那么另外一个事务读到的这个数据是“脏数据”，依据“脏数据”所做的操作可能是不正确的
2. 不可重复读（Unrepeatable read）: 指在一个事务内多次读同一数据。在这个事务还没有结束时，另一个事务也访问该数据。那么，在第一个事务中的两次读数据之间，由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况，因此称为不可重复读
3. 幻读（Phantom read）: 幻读与不可重复读类似。它发生在一个事务（T1）读取了几行数据，接着另一个并发事务（T2）插入了一些数据时。在随后的查询中，第一个事务（T1）就会发现多了一些原本不存在的记录。

### 左右联接

* inner join： 只保留两表完全匹配的结果集
* left join: 返回左表所有的行，右表中没有返回为null
* full join: 全外联接，返回左表和右表中所有没有匹配的行。mysql不支持 full join，使用left join union right join来实现。

### 主键

* 唯一且非空。
* 一个表有且只能由一个主键约束。
* 创建主键会自动创建对应的索引，同样删除主键，对应的索引也会被删除。

### 外键

* 如果定义了外键约束，主表中没有的数据在子表中是不可以被使用的。
* 主表中的记录被子表引用，是不可以被删除的。

### 查询

* 分组查询：count() sum() max() min() avg()
* 聚合查询：7种 A B A∪B A∩B A - A∩B B - A∩B A∪B - A∩B
* 左连接： A - A∩B 右连接：B - A∩B 内连接：A∩B

## 悲观锁和乐观锁

1. 悲观锁： 每次去拿数据时都认为别人会修改，所以每次在拿数据的时候都会上锁。悲观锁由数据库自己实现，共享锁和排他锁是悲观锁的不同实现。悲观锁的缺点：效率低，并行差，增加死锁的概率。
2. 乐观锁：每次去拿数据都认为别人不会修改，所以不会上锁。乐观锁适用于读多，写少的场景。乐观锁常见的实现方式：版本号机制和CAS自旋算法。乐观锁的缺点：ABA问题，循环时间长开销大，只能保证一个共享变量的原子操作。

## 调优

### 什么时候不应该创建索引

1. where条件里用不到的字段
2. 频繁更新的字段
3. 表记录太少<300W
4. 重复且平均的表字段

### explain 查看执行计划

* 使用explain关键字可以模拟优化器执行sql查询语句，从而知道mysql是如何处理sql语句的。分析查询语句或表结构的性能瓶颈。

### 聚簇索引

* 聚簇索引的叶子节点都是数据节点。
* 非聚簇索引的叶子节点是索引节点，有指向对应数据块的指针。

## MySQL优化

* explain
  * extra中显示file sort进行了文件排序，提示建立索引。
  * using index condition使用了索引但是，进行了回表查询。
* show profile
* SQL语句优化
  * 模糊查询like%
  * 避免使用select \*
  * insert尽量使用批量查询
  * 字符串单引号
  * left join对右边的数据建立索引
  * 范围查询右边的列索引失效
  * 不等号全表查询
  * is null或者is not null都无法使用索引

## read view

* 快照读时产生的读视图
  * 在RC，每个快照读都生成最新的read view
  * 在RR，同一事务在第一个快照读时创建read view
  * RC读提交，可以读到最新的commit。
  * RR可重复读，读的是快照版。

## 行锁

* 记录锁 record lock
* 间隙锁 gap lock
* 临键锁 next-key lock

## SQL优化

* 对where和order by的列建立索引
* 避免在where子句中对空值进行不等于判断
* 避免在where子句中使用or连接，否则会使引擎放弃索引而进行全表扫描
* 少用in和not in
* 少用like查询
* 避免在where中使用函数操作
* 不要使用select
* 尽量避免大事务操作
* join字段提前加上索引

### MVCC

* [参考视频](https://www.bilibili.com/video/BV1f94y1Z7V7?spm_id_from=333.337.search-card.all.click\&vd_source=e9f1ced96b267a4bc02ec41ca31d850a)
* 通过版本号，避免同一数据在不同事务见的竞争，主要是提高数据库的并发读写性能，不用加锁就能让多个事务并发读写。
* 核心思想：只能查找事务id小于等于当前事务id的行。

### 快照读和当前读

* 快照读：读取的是记录数据的可见版本，可能是过期的数据，不用加锁。只要当前事务还未提交，读取的数据就是可见版本，不会受其他事务提交与否的影响。快照是在你开启事务后，第一次用select时生成的。
* 当前读：读取的是记录数据的最新版本，并且当前读返回的数据会加上锁，保证其他的事务不会再并发地修改这条记录。
* select 是快照读
* update insert delete 是当前读
* MVCC不能从根本上解决幻读
* 快照读是通过undo log + MVCC来实现的

## 平衡树和红黑树的区别

* 平衡树是严格的左右子树高度差不超过1
* 红黑树在平衡性上做了妥协，自定义了四条规则
  * 所有的根节点都是黑色
  * 红色的孩子是黑色
  * 任意节点到叶子节点的路径上黑色节点的数目相同
  * 所有叶子节点都是黑色
* 红黑树牺牲查找的效率，换取了插入和删除的效率，但是平均时间复杂度还是logN

## 共享锁和排它锁

[行锁和表锁讲解](https://www.bilibili.com/video/BV1AE411a7rv?from=search\&seid=6023900352334983316)

* 行锁和表锁是粒度概念，共享锁和排它锁是具体实现。
* 共享锁：读锁 能读不能写
* 排它锁：写锁 不能读也不能写
* 表锁
  * 意向锁
  * 自增锁
* 行锁
  * record lock
  * gap lock
  * next-key lock
* 无锁

```sql
select * from user;
```

* 共享锁

```sql
select ... lock in share mode;
select ... for share;  MySQL 8.0
```

* 排它锁

```sql
update ...
delete ...
insert ...
select ... for update
```

* 注意
  * 某个事务获取数据的排它锁，其他事务不能获取该数据的任何锁，并不代表其他事务不能无锁读取该数据。
  * 简单来说：加了排它锁的数据，其他事务还可以用无锁读取数据。

### 分库分表

* 读写分离：解决高并发。
* 分库分表：解决高可用。
* 分库：减少并发问题
* 分表：降低了分布式事务

垂直分表：一个表，列比较多，把不同的字段分到不同的表中，降低单表大小来提高性能。 水平分表：以某个字段按照一定的规则，将一个表的数据分到多个表中。特点是表结构一样。 分表策略

* hash取模
* range范围区分
* list预定义

### 左右联接

[学习视频](https://www.bilibili.com/video/BV1Vt411z7wy?p=55)

* inner join： 只保留两表完全匹配的结果集。
* left join: 返回左表所有的行，右表中没有返回为null
* full join: 全外联接 ，返回左表和右表中所有没有匹配的行。mysql不支持 full join，使用left join union right join来实现。

联接练习题

* 组合两个表
* 部门工资最高的员工
* 从不订购的客户

alter table 表名 alter column 字段名 set default 默认值;

开启事务

* set autocommit = 0
* begin
* start transaction

### 关键字

* group by 分组
* having作用于组
* order by对某一列进行排序
* where后不能有聚合
* limit row: offset
* 7个关键字执行顺序：
  * from
  * where
  * group by
  * having
  * select
  * order by
  * limit

### 数据库优化

* explain执行计划
* limit优化
* 性能监控show profile

### Mysql主从复制和读写分离

* 提高数据库的并发性能。
* 一个master负责写操作，两台slave负责读操作。
* 当主库进行增删改操作时，会按顺序写入到binlog中。
* 每个从库创建binlog dump线程连接到主库。
* 当master节点的binlog有变化时，binlog dump线程会通知所有slave节点，并将相应的binlog内容推送给slave节点。
* slave的IO线程收到binlog内容后，将内容写入到本地的relay log
* sql线程读取本地的relay-log重新在从库中复现主库的增删改的操作。

读写分离存在的问题：

* 数据不一致问题

## 最左前缀法则（理解成爬楼梯）

[视频辅助](https://www.bilibili.com/video/BV1zJ411M7TB?p=55)

* sql查询条件中需要包含复合索引中的最左列，不能跳跃索引，否则索引失效。查询条件在where中出现的顺序没关系，只要按照最左前缀原则出现了，就会走索引。如果跳跃了索引，查询条件中满足最左前缀的部分走索引，到跳跃的部分时索引失效。

## 索引失效

1. 范围查询后其右边的列，索引失效。即索引某个字段使用了范围查询，他右边的索引将不再走索引。
2. 在索引列上进行运算操作，索引失效。（子串匹配查询）
3. 字符串不加单引号，索引失效。
4. 用or分割的条件，如果or前的条件中的列有索引，而后面的列中没有索引，那么涉及的索引都不会被用到。
5. 以%开头的like模糊查询，索引失效。
6. 如果mysql评估全表扫描更快，索引失效。
7. is NULL, is NOT NULL, 有时索引失效。
8. in走索引，而not in索引失效。

## 优化

1. 使用索引。
2. 根据sql实际解析的顺序，调整索引的顺序。
3. 尽量使用覆盖索引，避免select。覆盖索引是指只出现在索引中的字段。
4. 尽量使用复合索引，而少使用单列索引。
5. 优化insert。一次插入多条数据。事务改为手动提交，分段提交。按主键顺序插入。
6. 优化order by尽量使用using index 而避免使用filesort

## 定位低效sql语句

1. explain分析执行计划（索引失效或者关联查询太多join）
2. 慢查询日志
3. show profiles

## mysql分库分表

[视频辅助](https://www.bilibili.com/video/BV1bE411d7FF?p=14)

主从集群也就是读写分离，读写分离只是分担了访问的压力，存储的压力并没有解决。数据库集群环境后都是多台slave，基本满足了读取操作，但是频繁写入堆master性能影响比较大，这个时候，单库并不能解决大规模并发写入的问题。

分库分表带来的问题：\*\*1. 联合查询问题，join不再适用。2.事务问题，变成了分布式事务。好处：减少大量数据写入时锁对查询的影响。\*\*按照存储类别分：用户库，业务库，内存库，图片库，日志库，统计库。

分表：垂直分表和水平分表。解决单张表记录太多的问题。切分策略和导航路由。单表的容量超过500W时建议水平拆分。不到最后一步，不要轻易进行水平分表。

开源方案：1. msyql fabric 2.atlas 3.TDDL 4.mysql proxy 小巧精干，能力有限。+ master/slave 构成一个简单版的读写分离和负载均衡。

主从复制，读写分离---> 垂直分库(每个库可以带slave)--->分区---->水平分表。中间各种通信，调度，维护和编码要求更高。

## 主从复制

一主多从。 mysql复制是异步并串行化的。原理：slave从master读取binlog进行数据同步。主要分为3步：

1. master将改变记录到二进制日志(binary log)。这些记录过程叫做二进制日志事件binary log events。
2. slave从master的binary log events拷贝到它的中继日志relay log
3. 重做中继日志中的事件，将改变应用到自己的数据库中。

## 锁机制

锁可以对有限的资源进行保护，解决隔离和并发的矛盾。通过锁机制可以实现事务的隔离性要求，使得事务可以并发地工作。

按操作分：读锁（共享锁） 写锁（排他锁）

按粒度分：行锁（偏写）表锁（偏读）

锁使用的考虑点：开销，加锁速度，死锁，粒度，并发性能。

行锁：innoDB 开销大，加锁慢，会出现死锁，粒度小，锁冲突概率低，并发高。

表锁：myisam 开销小，加锁快，无死锁，粒度大，锁冲突概率高，并发性低。

行锁的三种算法：1. record lock 2.gap lock 3. next-key lock

锁带来的三种问题：1. 脏读 2. 不可重复读 3. 丢失更新

**意向锁**是将锁定的对象分为多个层次，对最细粒度的对象进行上锁，首先需要对粗粒度的对象上锁。

## 触发器

触发器只能创建在永久表上，不能对临时表创建触发器。触发器是行触发的。

## 视图

视图的主要用途是被用作一个抽象装置，只需要按照视图定义来取数据或更新数据。视图是一种虚拟存在的表。

## 联合索引

* 联合索引是指对表上的多个列进行索引。

## 主键索引与唯一索引的区别

1. 主键是一种约束，唯一索引是一种索引。两者在本质上是不同的。
2. 主键创建后一定包含一个唯一索引，但是唯一索引不一定是主键。
3. 主键不允许为空，而唯一索引可以为空。
4. 一个表最多只能创建一个主键，但是可以创建多个唯一索引。

## 索引的优缺点

* 索引是帮助mysql高效获取数据的数据结构。
* 优点：提高数据查询的效率，降低数据库的IO成本。通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗。
* 缺点：实际上索引也是一张表，也需要占用空间。虽然索引大大提高了查询的速度，但是也降低了更新表的速度。索引是不断完善的，需要根据实际需求进行优化调整。

## 什么时候使用索引

1. 主键自动建立唯一索引
2. 频繁作为查询条件的字段应该作为索引
3. 查询中统计或分组字段
4. 排序字段

## 什么时候不能使用索引

1. 频繁更新的字段不适合创建索引
2. where条件里用不到的字段不适合创建索引
3. 表记录太少
4. 数据重复且分布平均的字段

## 数据库中join的类型与区别

1. inner join
2. cross join
3. left join
4. right join

## 分库分表

数据库的IO瓶颈和CPU瓶颈都会导致数据库活跃连接数增加，进而逼近数据库可承载连接数的最大值。 IO瓶颈：磁盘读IO瓶颈，**热点数据太多，数据库缓存放不下**，每次查询时产生大量的IO，降低查询数据。解决方案【分库和垂直分表】

CPU瓶颈：SQL问题，包含join，group by，order by，非索引字段查询等，增加CPU运算的操作。解决方案【**SQL优化，建立适当的索引，在业务Service层进行业务计算**】单表数据量太大，查询时扫描的行太多，SQL效率低，CPU率先出现瓶颈。解决方案【水平分表】

分库分表工具：

* mycat
* sharding-sphere
* TDDL

分库分表总结：

* 分库分表首先要知道瓶颈在哪儿，才能合理地拆分。
* 选key很重要，既要考虑到拆分均匀，也要考虑到非patition key的查询。

## 锁机制

* 页锁--->表锁--->行锁
* 页锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般。
* 行锁：InnoDB支持默认行锁，也支持表锁。开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度也最高。
* 表锁：MyISAM支持表锁。开销小，加锁快；不会出现死锁；锁的粒度大，发生锁冲突的概率最高,并发度最低。

另一种分类方式

* 悲观锁：共享锁（读锁），排他锁（写锁）。
* 乐观锁：通过version控制

行锁分为三级，粒度从小到大依次是

* 记录锁（Record Lock）：单行
* 间隔锁（Gap Lock）：一个开区间内的多行
* 防插入锁（Next-Key Lock）：一个前开后闭区间内的多行，实际上是记录锁和间隔锁的结合

### 分类

* 基于页结构存储引擎B+ tree（InnoDB, boltDB）
* 基于日志结构存储引擎LSM tree（bitcask, levelDB, rocksDB）

### B+树

* 树的高度低，所以磁盘IO次数少。
* 叶子节点存数据，所以请求时间复杂度较平均。

### 基于日志结构存储引擎

1. 写多读少

### 怎么解决大量写

1. 利用顺序IO

### LSM存在的问题

1. 写放大。解决方式：定时回收数据。

### 索引和数据分离

1. myisam
2. bitcask

### 索引和数据存一起

1. innoDB （index & data）
2. levelDB (SSTables)
3. boltDB（index & data）
4. moss（kvs & buf）