数据库面试基础知识

一、数据库基础

1.关系型非关系型数据的区别

关系型数据库的优点：
容易理解。因为它采用了关系模型来组织数据。
可以保持数据的一致性。
数据更新的开销比较小。
支持复杂查询（带where子句的查询）

非关系数据库的优点
不需要经过sql层的解析，读写效率高；
基于键值对，数据的扩展性好；
可以支持多种类型数据的存储，如图片，文档等。

2.什么是非关型数据库

非关系型的数据库也叫nosql，采用键值对的形式进行存储。读写性能很高，易于扩展。如：Redis,Mongodb，hbase等等。
适合非关系型数据库的场景：
日志系统；
地理位置存储；
数据量大；
高可用

3.数据库的索引类型

数据库的索引类型可以分为逻辑分类 和 物理分类
逻辑分类：
主键索引：当关系表中定义主键时会自主创建主键索引。每张表的主键索引只能有一个，要求主键中的每一个值都唯一，即不可重复，也不能有空值。
唯一索引：数据列不能有重复，可以有空值。一张表可以有多个唯一索引，但每个唯一索引只能有一列。如身份证号，卡号。
普通索引：一张表可以有多个普通索引，可以重复可以为空值。
全文索引：可以加快模糊查询，不常用。

物理分类
聚集索引（聚簇索引）：数据在物理存储中的顺序跟索引中数据的逻辑顺序相同，比如以ID建立聚集索引，数据库中id从小到大排列，那么物理存储中该数据的内存地址值也按照从小到大存储。一般是表中的主键索引，如果没有主键索引就会以第一个非空的唯一索引作为聚集索引。一张表只能有一个聚集索引。
非聚集索引：数据在物理存储中的顺序跟索引中数据的逻辑顺序不同。非聚集索引因为无法定位数据所在的行，所以需要扫描两遍索引树。第一遍扫描非聚集索引的索引树，确定该数据的主键ID，然后到主键索引（聚集索引）中寻找相应的数据。

4.数据库的事务是怎么实现的？

事务是一组逻辑操作的集合。实现事务就是要保证可靠性和并发隔离(ACID)。这些主要靠日志恢复和并发控制完成的。

日志恢复：数据库里有两个日志，一个是redo log，一个是undo log。redo log记录的是已经成功提交的事务操作信息，用来恢复数据，保证事务的持久性。undo log记录的是事务修改之前的数据信息，用来回滚数据，保证事务的原子性。

并发控制：并发控制主要靠读写锁和MVCC（多版本并发控制）来实现。读写锁包括共享锁和排他锁，保证事务的隔离性。MVCC通过为数据添加时间戳来实现。

5.数据库中事务的ACID（四大特性都要能够举例说明，理解透彻，比如原子性和一致性的关联，隔离性不好会出现的问题）

数据库事务是指逻辑上对数据的一种操作，这个事务要么全部成功，要么全部失败
A：atom 原子性
事务是一个不可分割的工作单位，这组操作要么全部发生，要么全部不发生。
C：consistency 一致性
数据库事务的一致性是指：在事务开始以前，数据库的数据有一个一致的状态。在事务完成以后，数据库中的事务也应该保持这种一致性。事务应该将数据从一个一致性状态转移到另一个一致性状态。如：在银行转账操作前后两个账户的总额应当不变。
I：isolation 隔离性
数据库事务的隔离性要求数据库中的事务不会受另一个开发执行的事务的影响，对于数据库中同时执行的每个事务来说，其他事务要么还没开始执行，要么已经执行结束。
D：durability 持久性
数据库事务的持久性要求书屋对数据库的改变时永久的，哪怕数据库发生损坏都不会影响到已发生的事务。
如果事务没有完成，数据库因故断电了，那么重启后也应该是没有执行事务的状态，如果事务已经完成后数据库断电了，那么重启后就应该是事务执行完成后的状态。

6.脏读、不可重复读、幻读

脏读： 一个事务在处理过程中读取了另外一个还没提交的事务的数据。
不可重复读：对于数据库的某一个字段，一个事务多次拆线呢却返回了不同的值，只是由于早查询的间隔中，该字段被其他事务修改并提交了。
幻读：事务多次读取同一个范围的时候，查询结果的记录数不一样，这是由于在查询的间隔中，另一个事务新增或删除了数据。
避免不可重复读需要锁行，避免幻读则需要锁表。

7.数据库的隔离级别，mysql和Oracle的隔离级别分别是什么（重点）

为了保证数据库事务一致性，解决脏读，不可重复读和幻读的问题，数据库的隔离级别一共有四种隔离级别：
读未提交 Read Uncommitted: 最低级别的隔离，不能解决以上问题
读已提交 Read committed: 可以避免脏读的发生
可重复读 Reapeatable read: 确保事务可以多次从一个字段中读取相同的值，在该事务执行期间，禁止其他事务对此字段的更新，可以避免脏读和不可重复读。 通过锁行来实现
串行化 Serializaion 最严格的事务隔离机制，要求所有事务被串行执行，可以避免以上所有问题。 通过锁表来实现
Oracle的默认隔离级别是读已提交，实现了四种隔离级别中的读已提交和串行化隔离级别
MySQL的默认隔离级别是可重复读，并且实现了所有四种隔离级别

8.数据库的三大范式

第一范式(确保每列保持原子性)
第一范式是最基本的范式。如果数据库表中的所有字段值都是不可分解的原子值，就说明该数据库表满足了第一范式。
第二范式(确保表中的每列都和主键相关)
在满足第一范式的前提下，（主要针对联合主键而言）第二范式需要确保数据库表中的每一列都和主键的所有成员直接相关，由整个主键才能唯一确定，而不能只与主键的某一部分相关或者不相关。
第三范式(确保非主键的列没有传递依赖)
在满足第二范式的前提下，第三范式需要确保数据表中的每一列数据都和主键直接相关，而不能间接相关。非主键的列不能确定其他列，列与列之间不能出现传递依赖。
BCNF范式（确保主键之间没有传递依赖）
主键有可能是由多个属性组合成的复合主键，那么多个主键之间不能有传递依赖。也就是复合主键之间谁也不能决定谁，相互之间没有关系。

9.数据库的锁的种类，加锁的方式

以MySQL为例
按照类型来分有乐观锁和悲观锁
根据粒度来分有行级锁，页级锁，表级锁（粒度一个比一个大） （仅BDB，Berkeley Database支持页级锁）
根据作用来分有共享锁（读锁）和排他锁（写锁）

10.什么是共享锁和排他锁

共享锁是读操作的时候创建的锁，一个事务对数据加上共享锁之后，其他事务只能对数据再加共享锁，不能进行写操作直到释放所有共享锁。
排他锁是写操作时创建的锁，事务对数据加上排他锁之后其他任何事务都不能对数据加任何的锁（即其他事务不能再访问该数据）

11.乐观锁与悲观锁

一般的数据库都会支持并发操作，在并发操作中为了避免数据冲突，所以需要对数据上锁，乐观锁和悲观锁就是两种不同的上锁方式。

悲观锁假设数据在并发操作中一定会发生冲突，所以在数据开始读取的时候就把数据锁住。而乐观锁则假设数据一般情况下不会发生冲突，所以在数据提交更新的时候，才会检测数据是否有冲突。

悲观锁的实现：悲观锁有行级锁和页级锁两种形式。行级锁对正在使用的单条数据进行锁定，事务完成后释放该行数据，而页级锁则对整张表进行锁定，事务正在对该表进行访问的时候不允许其他事务并行访问。
悲观锁要求在整个过程中一直与数据库有一条连接，因为上一个事务完成后才能让下一个事务执行，这个过程是串行的。

乐观锁有三种常用的实现形式：
一种是在执行事务时把整个数据都拷贝到应用中，在数据更新提交的时候比较数据库中的数据与新数据，如果两个数据一摸一样则表示没有冲突可以直接提交，如果有冲突就要交给业务逻辑去解决。
一种是使用版本戳来对数据进行标记，数据每发生一次修改，版本号就增加1。某条数据在提交的时候，如果数据库中的版本号与自己的一致，就说明数据没有发生修改，否则就认为是过期数据需要处理。
最后一种采用时间戳对数据最后修改的时间进行标记。

二、MySQL

1.说一下MySQL执行一条查询语句的内部执行过程？

连接器：客户端首先通过连接器连接到MySQL服务器。
缓存：连接器经过权限验证后，先查询之前是否有执行过此语句（有缓存），若有则，直接返回缓存数据，若无，进入分析器。
分析器：分析器会对查询语句进行语法分析和词法分析，判断 SQL 语法是否正确，如果查询语法错误会直接返回给客户端错误信息，如果语法正确则进入优化器。
优化器：优化器是对查询语句进行优化处理，例如一个表里面有多个索引，优化器会判别哪个索引性能更好。
执行器：优化器执行完就进入执行器，执行器就开始执行语句进行查询比对了，直到查询到满足条件的所有数据，然后进行返回。

2.MySQL的优化（高频）

高频访问：
分表分库：将数据库表进行水平拆分，减少表的长度
增加缓存： 在web和DB之间加上一层缓存层
增加数据库的索引：在合适的字段加上索引，解决高频访问的问题

并发优化：
主从读写分离：只在主服务器上写，从服务器上读
负载均衡集群：通过集群或者分布式的方式解决并发压力

3.MySQL数据库引擎介绍，innodb和myisam的特点和区别

InnoDB ： InnoDB是mysql的默认引擎，支持事务和外键，支持容灾恢复。适合更新频繁和多并发的表 行级锁
MyISAM ： 插入和查询速度比较高，支持大文件，但是不支持事务，适合在web和数据仓库场景下使用 表级锁
MEMORY ： memory将表中的数据保存在内存里，适合数据比较小而且频繁访问的场景
CSV
blackhole

三、索引

1.索引的优缺点，什么时候使用索引，什么时候不能使用索引（重点）

什么时候适合使用索引：
经常搜索的列上建索引；
作为主键的列上需要建索引
经常需要连接（where）的列上
经常需要排序的列
进场需要范围插着列

那些列不适合建索引：
很少查询的列
更新很频繁的列
数据的可取值比较少的列

2.索引的低层实现（重点）

数据库的索引是用B+树实现的；
B+树是一种特殊的平衡多路树，是B树的优化改进版本，它把所有的数据都存放在叶节点上，中间节点保存的是索引。这样一来相对于B树来说，减少了数据对中间节点的空间占用，使得中间节点可以存放更多的指针，使得树变得更矮，深度更小，从而减少查询的磁盘IO次数，提高查询效率。另一个是由于叶节点之间有指针连接，所以可以进行范围查询，方便区间访问。
而红黑树是二叉的，他的深度相对于B+树来说更大，更大的深度意味着查找的次数更多，更频繁的磁盘IO，所以红黑树更适合在内存中进行查找。

3.B树和B+树二点区别（重点）

1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。
2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

B+树优点：由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引，而B树则常用于文件索引。

4.索引最左前缀/最左匹配

假如我们对a b c三个字段建立了联合索引，在联合索引中，从最左边的字段开始，任何连续的索引都能匹配上，当遇到范围查询的时候停止。比如对于联合索引index(a,b,c),能匹配a,ab,abc三组索引。并且对查询时字段的顺序没有限制，也就是a,b,c; b,a,c; c,a,b; c,b,a都可以匹配。

5.各种树形结构

AVL树（平衡二叉树）
红黑树是在AVL树的基础上提出来的。
平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。
AVL树中所有结点为根的树的左右子树高度之差的绝对值不超过1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
红黑树
对红黑树的理解：通过特殊的要求实现了比较奇怪的结构（数据存放方式），这种结构（存放方式）可以让查找数据变得特别有效，查找方式和常规的二叉查找树查找同。
红黑树是在AVL树的基础上发展而来的。红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。

红黑树较AVL树的优点：
AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。

红黑树旋转：
旋转：红黑树的旋转是一种能保持二叉搜索树性质的搜索树局部操作。有左旋和右旋两种旋转，通过改变树中某些结点的颜色以及指针结构来保持对红黑树进行插入和删除操作后的红黑性质。
左旋：对某个结点x做左旋操作时，假设其右孩子为y而不是T.nil：以x到y的链为“支轴”进行。使y成为该子树新的根结点，x成为y的左孩子，y的左孩子成为x的右孩子。
右旋：对某个结点x做右旋操作时，假设其左孩子为y而不是T.nil：以x到y的链为“支轴”进行。使y成为该子树新的根结点，x成为y的右孩子，y的右孩子成为x的左孩子。

B+树
B+是一种多路搜索树，主要为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，每个节点的可以有多个孩子，并且按照关键字大小有序排列。所有记录节点都是按照键值的大小顺序存放在同一层的叶节点中。相比B树，其具有以下几个特点：

每个节点上的指针上限为2d而不是2d+1（d为节点的出度）
内节点不存储data,只存储key
叶子节点不存储指针