面试之关系型数据库

数据库设计三范式

第一范式。任何一张表必须有主键，每一个字段具有原子性不可再分。
第二范式。所有非主键字段完全依赖主键字段，不存在部分依赖（复合主键可能存在此情况）。
第三范式。所有非主键字段直接依赖于主键字段，不存在传递依赖（比如员工表中存在部门编号和部门名）。

注：多对多时建三个表，用关系表存放一个主键和两个外键；一对多时建两个表，“多”表加外键；一对一时拆分表（字段太多），外键加unique约束，主键和外键一一对应。

几个语法使用细节

count(*)统计表数据总行数，count(字段)统计该字段下不为NULL的总数。
使用group by时，select后面的字段必须是分组的字段或者其他字段的聚合函数。
distinct必须在查询内容最前面，若后面跟多个内容则将组合后的内容去重。
sql92语法：表连接时用where条件直接过滤；sql99语法：表连接时用join关键字连接，将连接条件与其他过滤条件隔离，inner join和join等价，inner可省略。
union合并结果集时要求列和列类型都必须一致，效率比表连接更高，将笛卡尔积乘法变为加法。
mysql默认短日期（date）格式'%Y-%m-%d'，默认长日期（datetime）格式'%Y-%m-%d %h:%i:%s'，若存取时满足要求则默认会自动进行字符串和日期间的相互转换。
删除表所有数据时使用truncate比delete效率更高，但delete删除时硬盘中的空间不会被释放，故支持事务回滚。

七种连接

内连接，INNER JOIN。

SELECT *
FROM tableA a
INNER JOIN tableB b
ON a.key = b.key

左连接，LEFT JOIN

SELECT *
FROM tableA a
LEFT JOIN tableB b
ON a.key = b.key

右连接，RIGHT JOIN

SELECT *
FROM tableA a
RIGHT JOIN tableB b
ON a.key = b.key

左外连接，LEFT JOIN

SELECT *
FROM tableA a
LEFT JOIN tableB b
ON a.key = b.key
WHERE b.key IS NULL

右外连接，RIGHT JOIN

SELECT *
FROM tableA a
RIGHT JOIN tableB b
ON a.key = b.key
WHERE a.key IS NULL

全连接，FULL OUTER JOIN

SELECT *
FROM tableA a
FULL OUTER JOIN tableB b
ON a.key = b.key
//但mysql不支持FULL OUTER JOIN操作，可用下面语句实现
SELECT *
FROM tableA a
LEFT JOIN tableB b
ON a.key = b.key
UNION
SELECT *
FROM tableA a
RIGHT JOIN tableB b
ON a.key = b.key

全外连接，FULL OUTER JOIN

SELECT *
FROM tableA a
FULL OUTER JOIN tableB b
ON a.key = b.key
WHERE a.key IS NULL
OR b.key IS NULL
//但mysql不支持FULL OUTER JOIN操作，可用下面语句实现
SELECT *
FROM tableA a
LEFT JOIN tableB b
ON a.key = b.key
WHERE b.key IS NULL
UNION
SELECT *
FROM tableA a
RIGHT JOIN tableB b
ON a.key = b.key
WHERE a.key IS NULL

B树和B+树

这里仅大致记录B树和B+树的概念和由来，具体细节操作不细说。

平衡二叉树是二叉排序树的改进版，每个结点只有一个键，每个结点最多两个子树，左小右大且二者高度绝对值不超过1。但当数据量明显增多时，平衡二叉树的高度上升的很快，这会显著影响平衡二叉树的查询效率。

多路查找树

多路查找树的每个结点可以有多个键，每个结点的子树数量为键数+1，子树存在于键之间，依然是左小右大。这样的好处是当一个结点的键特别多的时候，可以进一步使用二分查找提高效率。但多路查找树并没有严格规定键的插入、删除方法，故丢失了“平衡”的理念，有着与二叉排序树一样的弊端。

B树

在多路查找树的基础上添加了一系列的规则，又名多路平衡查找树。引入阶的概念，m阶B树的每个结点最多有m个子树，最少有m/2向上取整个子树（根节点除外，最少有2个子树，1个键）。相应的，每个结点最多有m-1个键，最少有m/2向上取整-1个键。即阶与子树数量对应。插入键时，优先填充结点，直到结点的键数量溢出再执行分裂操作，发生溢出的结点一定是当前B树的叶子结点，于是挑出结点中第m/2向上取整个键（即中间靠右）向上融合。这样一来就让多路查找树尽可能保持高度平衡，维持了查询效率。

B+树

在B树的基础上改进。m阶B+树的每个结点最多有m个子树，最少有m/2向上取整个子树（根节点除外，最少有2个子树，1个键）。但子树不再是存在于键之间，而是由键直接引出，故每个结点最多有m个键，最少有m/2向上取整个键。且每个键存在于其引出的子结点中，并是最大（或最小，全局一致即可）的键。这使得所有的叶子结点的键加起来就是整个B+树的键，并将所有叶子结点链起来形成一个含有所有键的链表。这解决了上述所有查找树的一个弊端：无法高效实现全局查询和范围查询（需要回溯）。B+树可以直接在所有叶子结点形成的链表中向后遍历即可。

B树与B+树的区别

B+树中存在重复元素。
B+树只有叶子结点存放数据。
B+树所有叶子结点形成一个双向链表。

为什么用B+树不用B树

基本都是因为只有叶子结点存放数据这个特性所引出的优点：

B+树的非叶子结点可以存放更多的键，一次IO操作可以读进内存的键更多，从而减少IO次数。
B+树查询效率更稳定，因为数据都在叶子结点，故查询都得从根走到尾，而B树可能在非叶子结点就找到了。
B+树有效解决了全表查询和范围查询，直接找到特定叶子结点然后往前或后遍历即可。

一亿条1kb的数据走主键索引，mysql底层io次数多少？

MySql的存储单位为页，每页16kb，MySql的b+树中索引结点的大小等同于一个页。一般而言，绝大部分数据库主键都为自增bigint，大小8byte，此外还有一个指向子结点的指针，大小为6byte。那么一个非叶结点中可以存放约16kb / (8b + 6b) = 1170个键（即b+树的阶），一个叶子结点可以存放16kb / 1kb = 16条数据。那么一个二层b+树可以存放约1170 * 16 = 18720条数据，一个三层b+树可以存放约1170 * 1170 * 16 = 2190万条数据，一个四层b+树可以存放约1170 * 1170 * 1170 * 16kb = 256亿条数据。故存放一亿条1kb的数据需要一个四层b+树，而通常每个表的主键索引根节点都是常驻内存的，所有这里mysql底层需要3次io（通常都是1~3次）。

MyISAM 和 InnoDB

InnoDB支持行级锁、事务和外键，缓存索引及真实数据，存储内容多，适用于高并发读写操作场景。
MyISAM仅支持表级锁，不支持事务和外键，只缓存索引，适用于快速读操作场景。
MyISAM和InnoDB的索引都使用B+树，但MyISAM使用非聚簇索引（叶节点存放数据的指针），InnoDB使用聚簇索引（叶节点存放真实数据）。
MyISAM存储文件包括frm文件（表结构）、MYD文件（表数据）、MYI文件（表索引）；InnoDB存储文件包括frm文件、idb文件（表数据和索引）。

MySql索引

索引的定义：帮助MySql快速获取数据的数据结构。

mysql索引分类

普通索引，唯一索引（不允许值重复，可以为NULL），主键索引（特殊的唯一索引，不允许NULL），联合索引（组合不重复，不允许NULL），全文索引（类似搜索引擎）。

聚簇索引

每个表都有唯一的聚簇索引，默认创建表时指定主键就会创建主键聚簇索引（后面默认用主键索引作为聚簇索引）。聚簇索引的叶子结点存放的是完整的数据行，其他所有索引树的叶子结点存放的都是索引+主键。故当利用非主键索引查询时，需要先获得对应的主键值，再去主键索引树查询，这个过程称为“回表”。聚簇索引的数据物理存储顺序与索引顺序一致，故查询效率较高。但在插入数据时可能造成“页分裂”现象，即为了保证数据存放有序但空间有限时可能会将数据移动到另一个数据页，此时只需修改主键索引树，其他索引无需修改。

非聚簇索引

非聚簇索引的叶子结点存放的是完整数据行的指针，所有索引与数据都是分开存储，主键索引与非主键索引并无区别（叶子结点都是指针）。非聚簇索引下存放的数据逻辑连续但物理不连续，故查询效率较低。

最左匹配原则

当使用联合索引查询时会涉及到这个原则，联合索引即利用多个字段组合成为索引。最左针对的是联合索引而言，sql语句中where后面跟的条件的先后顺序并无任何影响。例：创建（b，c，d）索引，当查询条件为c=1 and d=1时，违背了最左匹配原则，无法走该索引。当查询条件为b=1 and d=1时，可以走该索引，但只会过滤掉b!=1的内容，因为后面紧跟的c字段没有指定无法比较，此时会从叶子结点依次往后遍历。查询条件出现比较符号时，会先查询等于的情况，然后从叶子结点后面依次遍历，此时跟在后面的查询条件也会无法利用索引。

覆盖索引

也叫索引覆盖，当要查询的内容（即select后跟的内容）全部包含在索引之中，这种情况称为覆盖索引。若非覆盖索引，则需要进行“回表”。

前缀索引

当要创建的索引字段内容过多（一般为字符串等），需要进行裁剪，取前面一部分作为前缀索引。前缀索引不能太短，因为要使该索引的选择性足够高（选择性指数据行对于索引的不重复度），这样才能充分利用索引实现高效查询；同时前缀索引不能太长，因为这样会有内存大小限制且会将大量时间花费在B+树中间结点的比较上，影响效率。

索引失效

不遵循最左匹配原则。where后面and条件的先后顺序不影响结果！！！
在索引列做任何操作：计算、函数、（自动或手动）类型转换等。
范围查询（不等于操作也属于范围查询）后面的索引全部失效。
like带前缀%。如何解决：使用覆盖索引，对索引进行全表扫描得到结果，当like前缀是常量时不会中断索引的使用。
使用or关键字。

索引优化

小表驱动大表。对INLJ而言，外层循环决定索引查询次数；对BNLJ而言，外层循环决定IO次数。故外层循环次数越少越好，即驱动表的大小越小越好，mysql优化器会自动选择小表驱动。
左连接给右表建索引，因为左表是驱动表，它的数据无论如何都会有，即使有索引最后查询行数还是和全表查询一样。
右连接给左表建索引。
内连接都可以建，但优先给大表。
假设语句1. select * from A where id in (select id from B)；语句2. select * from A where exists (select 1 from B where A.id = B.id)

两条语句的效果等价。但in会将后面的查询结果缓存起来后逐一比较，故当B的数据集较小时in的效率更高；而exists只会看后面的语句是否返回true或false，A中查询有多少行就会执行多少次exists查询判断，故当B的数据集较大时exists的效率更高。

Nested-Loop Join算法

Simple Nested-Loop Join，SNLJ算法（简单嵌套循环连接）。sql执行流程：1. 取出驱动表中一行数据；2. 全表扫描找出被驱动表中满足关联字段的数据；3. 合并数据；4. 重复执行上述三步直到驱动表遍历结束。也就是双重循环暴力大法，代价太大一般不用。
Index Nested-Loop Join，INLJ算法（索引嵌套循环连接）。sql执行流程：1. 取出驱动表中一行数据；2. 索引扫描找出被驱动表中满足关联字段的数据；3. 合并数据；4. 重复执行上述三步直到驱动表遍历结束。一般当被驱动表中的关联字段有索引时会采用此算法。
Block Nested-Loop Join，BNLJ算法（块嵌套循环连接）。sql执行流程：1. 把驱动表中的所有数据放进join_buffer中；2. 把被驱动表中数据逐行取出与join_buffer中的数据做对比；3. 合并数据。BNLJ算法可以有效减少IO次数，但数据比较次数和SNLJ算法一样。简单表述：SNLJ是对驱动表的每一行进行一次被驱动表的全表扫描，而BNLJ是对每一个join_buffer进行一次被驱动表的全表扫描。

总结：一般不采用SNLJ算法，当被驱动表的关联字段有索引时采用INLJ算法，否则采用BNLJ算法。

explain的type字段

以下常见的6种type从上至下效果越来越好，一般至少达到index，最好ref。

all，全表扫描。
index，另一种全表扫描，但扫描的是索引树，当找到B+树某个叶子结点后向后遍历所有结点。当extra列出现USING INDEX时说明出现覆盖索引，即要查找的字段均包含在索引中，当extra列仅有USING Where时表明需要回表，当extra列出现USING Filesort时说明mysql引擎进行了额外的文件排序，当extra列出现USING Tempory时说明出现了临时表保存中间结果。
range，基于索引的范围扫描。
ref，非唯一索引，当找到特定叶子结点后还要向后进行小范围遍历，因为索引字段或组合不唯一。
eq_ref，唯一索引，当找到特定叶子结点后即结束，因为索引字段或组合唯一。
const，常量，指最终查找结果只有一条记录匹配，索引唯一不代表实际数据唯一。
system，系统常量，指整个表中只有一行记录。

函数和存储过程

二者都可以看做是一组为了完成特定功能的SQL 语句集，区别是函数参数默认为IN且必须有返回值（必须是一个值），可以在sql语句中调用；而存储过程有三种类型参数IN、OUT（类似面向对象语言中的引用传递）、INOUT，没有返回值，只能直接调用。

定义函数的代码如下：

/*定义rand_string函数，返回一个长度为n的随机字符串*/
DELIMITER $$
CREATE FUNCTION rand_string(n INT) RETURNS VARCHAR(255)
BEGIN
DECLARE chars_str VARCHAR(100) DEFAULT 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
DECLARE return_str VARCHAR(255) DEFAULT '';
DECLARE i INT DEFAULT 0;
WHILE i < n DO
SET return_str = CONCAT(return_str, SUBSTRING(chars_str, FLOOR(1+RAND()*52), 1));
SET i = i + 1;
END WHILE;
RETURN return_str;
END
$$

函数可以在sql语句中或者存储过程中调用，如：select rand_num(1, 10);

定义存储过程的代码如下：

/*定义存储过程，批量插入部门表，部门编号从start开始，递增插入max_num条记录*/
DELIMITER $$
CREATE PROCEDURE insert_dept(IN start INT(10), IN max_num INT(10))
BEGIN
DECLARE i INT DEFAULT 0;
SET autocommit = 0;
REPEAT
SET i = i + 1;
INSERT INTO dept (deptNo, dName, location) VALUES ((start + i), rand_string(10), rand_string(8));
UNTIL i = max_num
END REPEAT;
COMMIT;
END
$$

存储过程只能直接调用，如：insert_dept(0, 100);

存储过程的优点有：重复使用；减少网络传输开销（只需传输过程名和参数）；防止用户对表的直接访问。

视图

理解为虚拟表，和普通表一样使用，只保存sql逻辑不保存结果，主要作用是简化sql语句，存储时也是以文件形式在硬盘上存放。视图和原表是有关联关系的，对视图增删改也会对原表产生影响。创建视图语句：create view xxx as 'select xxx'。

锁

按锁粒度分为表锁和行锁

表锁，Myisam只支持表锁，开销小，加锁快，不会出现死锁，但锁冲突概率高，并发效率低。语句：lock table xxx read/write。
行锁，Innodb支持行锁和表锁，通过给索引项加锁实现行锁，故查询时没有索引或索引失效会导致行级锁升级为表级锁。加行锁的开销大，加锁慢，会出现死锁，但锁冲突概率低，并发效率高。

按锁使用方式分为共享读锁和排它写锁

共享锁，也称读锁，S锁（share）。多个事务可以同时获取读锁以读取数据，但都不能写数据直到所有读锁被释放后有事务获取写锁，手动加读锁语句：select …… lock in share mode。
排它锁，也称写锁，X锁（exclusive）。同一时刻只能有一个事务拥有写锁，其他事务的读或写都会被阻塞，手动加写锁语句：select …… for update。

按设计思想分为悲观锁和乐观锁

悲观锁，认为每次操作都可能出现异常，对每次操作都加排它锁。
乐观锁，认为每次操作都不会出现异常，通过添加数据版本字段实现并发安全，当提交数据更新时与上一次获取的数据版本对比数据版本是否一致，不一致则认为出现冲突，即CAS（compare and swap）思想。

间隙锁

当使用索引的范围查询并请求加行锁时，Innodb会把范围的所有索引项加锁，即使这条记录并不存在，这种情况称为间隙锁。

事务

事务是由一步或几步数据库操作序列组成逻辑执行单元，这系列操作要么全部执行，要么全部放弃执行。

ACID特性

原子性（Atomicity），事务不可再分解。mysql使用undo log实现。
一致性（Consistency），事务执行后必须使数据库从一个一致性状态变到另一个一致性状态，同时成功或同时失败。
隔离性（Isolation），各个事务的执行互不干扰，任意一个事务的内部操作对其他并发的事务都是隔离的。
持久性（Durability），事务一旦提交，对数据所做的任何改变，都要记录到物理数据库中。mysql使用redo log实现。

注：mysql使用MVCC和锁实现事务的一致性与隔离性。

mysql如何支持事务

begin，开始一个事务
rollback，事务回滚
commit，事务确认

mysql默认是自动提交事务（即一个语句一个事务），需要执行set autocommit = 0（或者start transaction，二者有区别）语句来禁止自动提交。Innodb存储引擎会把开启事务后的所有执行语句记录到一个事务性日志文件中，用于提交或者回滚事务。

并发事务可能存在的问题

更新丢失。A和B事务都基于同一数据进行更新从而造成某个事务的更新丢失，类似两个线程都执行i++却只加了一次。
脏读。即A事务读取到了B事务尚未提交的更新数据。
不可重复读。即A事务读取了B事务已提交的修改/删除数据。
幻读。即A事务读取了B事务已提交的新增数据。

mysql提供的事务隔离级别

读未提交。最低的隔离级别，可能出现脏读。大多数数据库最低的隔离级别是读已提交。《没有提交就读到了》
读已提交。A事务只能读取到B事务已经提交的数据，解决了脏读，每次读取到的数据都是绝对真实的，故可能出现多次读数据结果不一样，即可能出现不可重复读。读已提交是Oracle数据库默认隔离级别。《提交之后才能读到》
可重复读。A事务开启后每次读取到的数据都是一致的，永远读取到的都是刚开启事务时的数据，解决了不可重复读，但可能出现幻读。可重复读是mysql数据库默认隔离级别。《提交之后也读不到，除了新增的》
序列化。最高的隔离级别，所有事务排队执行，解决了所有并发事务问题，但并发效率很低。

多版本并发控制MVCC

MVCC是mysql中基于乐观锁理论实现读已提交和可重复读隔离级别的方式，主要是为了实现不用加锁也能解决数据的读-写冲突问题（读-读无需处理、写-写通过加锁实现），换句话所MVCC是mysql实现快照读的方式。

参考链接：https://blog.csdn.net/SnailMann/article/details/94724197?utm_medium=distribute.pc_relevant.none-task-blog-2_defaultCTRLIST_{default-2.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2}default_CTRLISTdefault-2.no_search_link

快照读和当前读

快照读 (snapshot read)指读到的数据可能是历史数据，并不是数据库最新的数据。Innodb中的普通select语句都属于快照读，其中读已提交隔离级别下是每次执行select语句时都创建快照，可重复读隔离级别下是仅第一次执行select语句时创建快照。
当前读(current read)指读取到的数据是数据库最新版本。Innodb中的select xxx lock in share mode、select xxx for update、update、 insert、 delete都属于当前读，因为它们都用到了锁来保证并发安全。

undo log，redo log和binlog

redo log属于存储引擎层（innodb专属），是一种物理格式日志，记录的是事务中对磁盘中每一个数据页的物理修改，空间大小固定，当空间满了后就必须将redo log中的内容刷新到磁盘中，默认有2个redo log文件，可以循环写入。redo log的写入在事务进行过程中不断发生，不论事务是否提交都会被记录。
undo log保存了事务发生之前的数据的一个版本，可以用于回滚同时供MVCC实现非锁定读。undo log又分为两种：一是insert undo log，记录事务在insert新记录时产生的数据，只在事务回滚时需要，并且在事务提交后可以被立即丢弃；二是update undo log，事务在进行update和delete时产生的数据，不仅在事务回滚时需要，在快照读时也需要，所以不能随便删除，只有在不需要时统一清除。
binlog保存了事务的更新操作语句的二进制数据，属于Server层（不同存储引擎都会在binlog中写入），是一种逻辑格式日志，记录的是二进制更新操作语句，可用于数据同步（主从复制）。binlog的写入仅发生在事务提交后，即一次性写入。

每行记录的三个隐藏字段

行id，默认的隐藏主键。
事务id，表明这条记录最后是谁新增/修改的，全局递增。
回滚指针，指向undo log中存放的关于该记录的旧版本。

当有事务对一行记录修改/删除时会把即将被修改的数据cpoy到undo log中，同时往数据库中写入新的一行记录，新的记录除了被事务修改的显示字段外，对应隐藏字段的事务id会变为执行当前操作的事务id，同时回滚指针会指向刚才copy到undo log中的旧记录。如此一来，undo log则会存放关于该记录的一条版本链。

read view

读视图，可以理解为数据快照，是快照读的重要依据。read view中存放了三个内容：

创建该read view时活跃的事务id集合。
活跃的事务id集合中最小的事务id。
创建该read view时系统即将分配的下一个事务id。

MVCC实现快照读

当进行快照读时，首先会创建一个read view。在找到数据库中存放的对应记录后，获取该记录的隐藏字段事务id，并用事务id与read view中的数据比对，从而判断该记录是否属于该事务的可见版本，不可见则到undo log中继续沿链表向后寻找该事务可见的最新的旧记录。判断条件共三个：

记录的事务id是否小于read view中记录的最小事务id？是则说明最后操作该记录的事务先于我创建read view的时机，故对我是可见的，否则继续向下判断。
记录的事务id是否大于等于read view中记录的系统即将分配的下一个事务id？是则说明最后操作该记录的事务晚于我创建read view的时机，故对我是不可见的，否则继续向下判断。
记录的事务id是否存在于read view中记录的活跃的事务id集合中？是则说明我创建read view时操作该记录的事务还未commit，故对我是不可见的；否则说明最后操作该记录的事务已经在我创建read view前commit了，故对我是可见的。

读已提交和可重复读

读已提交隔离级别是在每一次执行快照读时都创建read view，故会出现不可重读问题。
可重复读隔离级别是在第一次执行快照读时创建read view，后续的快照读都依赖于该read view，故实现了可重复读。

根据幻读的定义以及mysql可重复读隔离级别的实现原理来看，个人认为其实是解决了幻读问题的，一个事务两次查询并不会出现结果集行数不一致的情况。但如果事务A开启后一直没有进行快照读，期间其他事务对数据进行了新增/修改/删除操作并提交了，那么这些操作对事务A都是可见的，此时事务A进行快照读会获取到最新的数据。再者如果事务A开启后进行了一次快照读，之后其他事务执行了写操作并提交，此时事务A如果执行范围性的写操作也会对事务A“看不见”的数据产生影响，因为在innodb中update和delete都属于当前读。

标签：关系,结点,索引,数据库,事务,面试,key,数据,主键
From： https://www.cnblogs.com/mqDliaolei/p/17734292.html