面试总结之数据库原理基础

数据库操作是后端开发的基础，数据库的操作涉及到许多实际的细节，以及一些底层的原理，学的时候可能比较凌乱。这里就为大家总结一下常见的考点。总结的部分是结合了教科书、其他面经以及个人的面试经历，相信能够帮助到大家。如果有不足的地方，欢迎大家指出！

本博客长期更新，欢迎大家收藏、订阅！

索引

为什么要有索引

如果没有索引，在查询的时候我们就需要全表扫描。使用了index，通过缩小一张表中需要查询的记录、行的数目来加快搜索速度。举个例子，我们查字典很快是因为字典按照字母的顺序排好了，不然的话我们要查一个单词只能够从头一个一个单词看。

索引是什么

一个索引本身存储两样东西：一是index那一列的值，二是指向表中某一行的指针。这样我们找到这个索引就可以找到这条记录。所以索引是一种数据结构应用。一般会把索引建立在B-Tree上。

索引的分类

哈希索引（hash index）：建立在哈希表上的索引，只适用于等值查询，不适合范围查询。因为根据查询值直接哈希就能访问到索引的位置，然后找到表中对应的记录，但是索引本身是无序的，所以没有办法进行范围查询。
B-Tree索引：建立在B-Tree上的索引，因为查找、删除、插入操作的时间复杂度都是对数，所以效率很高。同时在B-Tree中的数据是有序的，所以很适合范围查询。
代价：占用空间，凡是插入删除操作都需要及时更新。

什么时候使用索引

比如我们使用SQL语句查询一个用户SELECT * FROM User WHERE Name = 'John'，这个时候数据库会检查Name这个列上是否有索引，如果有，数据库则会检查使用索引是否合理，若合理则使用索引再进行查询。

咦，这里有个问题，是否合理是如何理解呢？这里牵涉到索引基数和索引选择度问题，详情请移步到传送门

B树和B+树

两者都应用在数据库索引，可以认为是m叉的多路平衡查找树。数据库索引存储在磁盘上，搜索的时候逐一加载每一个磁盘页（对应索引树的一个结点）。对于树结构而言，IO的次数就是树的高度。

M阶B树
1. 定义任意非叶子结点最多只有M个叶子，且$M\gt2$；
2. 根结点的叶子数为$[2, M]$；
3. 除根结点外的非叶子结点的叶子数为$[\frac{M}{2}, M]$；
4. 非叶子结点的key个数=叶子数 - 1；
5. 所有叶子结点位于同一层；
6. $k$个key把结点拆成$k+1$段，分别指向$k+1$个儿子，同时满足查找树的大小关系。
B树的特点
1. key集合分布在整棵树中；
2. 任何一个key出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 其搜索性能等价于在key全集内做一次二分查找。
M阶B+树特征
1. 有$n$棵子树的非叶子结点中含有$n$个key（B树是$n-1$个）。这些key本身不存储数据，只用于索引，所有数据都保存在叶子结点。（B树是每个key都保存数据内容）；
2. 所有叶子结点中包含了全部的key，及指向这些key记录的指针。同时，叶子结点本身按照key的大小，从小到大顺序链接成链表；
3. 所有非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（最小）key；
4. 通常在B+树上有两个指针，一个指向树结构的根结点，另一个指向key最小的叶子结点，即链表头；
5. 同一个数字会在不同结点中重复出现，根节点的最大元素就是B+树的最大元素。
B+树比B树好在哪？
1. B+树的中间结点不保存数据本身的内容，所以磁盘页能够容纳更多的key；
2. B+树查询必须到叶子结点，更加稳定；
3. 对于范围查找而言，B+树只需要遍历叶子结点链表即可，B树则需要重复地进行遍历。

MyISAM和InnoDB区别

两者是指MySQL中表的类型。

区别
1. MyISAM不支持事务处理，InnoDB支持；
2. MyISAM强调性能，执行速度快；
3. InnoDB提供事务支持以及外部键等高级功能
Details
1. InnoDB不支持FULLTEXT类型的索引；
2. InnoDB不保存表的具体行数。执行select count(*) from table时，InnoDB要扫描一遍来计算整个表有多少行，但MyISAM只要读出保存好的行数。当执行count(*)语句时，如果包含where条件时，两种表的操作是一样的；
3. 对于AUTO_INCREMENT字段，InnoDB中必须包含只有该字段的索引，但是在MyISAM中，可以和其他字段一起建立联合索引；
4. delete from table时，InnoDB不会重新建表，而是逐行删除；
5. load table from master对InnoDB无效；
6. InnoDB表的行锁也不是绝对的。不确定扫描范围时，InnoDB同样会对整个表上锁。

乐观锁与悲观锁

悲观锁：认为数据被并发修改的概率较大，需要在修改之前先加锁。缺点是会产生额外的开销，增加死锁的机会，降低并行性。
- 基本思路：
  1. 对记录修改前，加上排它锁（exclusive lock）
  2. 若失败，等待或抛出异常
  3. 若成功，允许对记录进行修改，完成后释放锁
- 实际应用的时候需要关闭数据库的auto_commit
乐观锁：假设数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突进行检测。
- CAS（compare and swap）算法：无锁编程。多个线程使用CAS同时更新同一个变量，只有一个线程能完成更新，其余线程都失败。更新提交的时候，将数据库表对应的记录与第一次取出来的记录作比较。如果相同，则予以更新；否则认为是过期数据，更新失败。
- ABA问题：CAS算法存在的漏洞，即第一次取出来的记录（A）和当前记录（A）一致，并不能代表数据就是没有被修改过，中间可能存在B，只不过后面又给改回去A了。解决办法是：通过一个单独可顺序递增的version字段（或时间戳），提交时检查版本号和数据的版本号，如果一致才予以更新，version递增。

数据库的隔离级别

隔离级别/问题	脏读	不可重复读	幻读	级别
Read uncommitted	√	√	√
Read committed	×	√	√	语句级
Repeatable read	×	×	√	事务级
Serializable	×	×	×	事务级

数据库连接池

如果没有使用数据库做过应用开发的话，可能很多人不知道连接池的作用。但是公司的业务肯定会涉及到的，因此还是有必要了解一下。

为什么要用连接池？
- 简单应用$\rightarrow$数据库访问不频繁$\rightarrow$按需创建连接，用完后关闭
- 复杂应用$\rightarrow$频繁访问，建立、关闭连接$\rightarrow$减低系统性能（解决办法：连接复用！！）
基本原理：在内部对象池中维护一定数量的数据库连接，并对外暴露数据库连接获取和返回方法。如：
- 获取连接：getConnection()
- 释放连接：releaseConnection()
当释放连接的时候，连接并没有真正的关闭，而是由连接池管理器回收，并为下一次使用做好准备。
优点
1. 资源重用。减少系统开销，增加系统运行环境的平稳性（减少内存碎片、数据库临时进程和线程的数量）；
2. 更快的系统响应速度。因为连接已经初始化，缩短了访问时间；
3. 更好的资源分配手段。多应用共享同一个数据库，可以通过限制连接数，从而避免某一应用独占所有的数据库资源；
4. 统一管理：能够很好地避免连接泄漏问题。通过预先设定占用超市，强制收回被占用的连接。

Halo

实习面经-数据库基础