概述
数据库是存放数据的仓库。它的存储空间很大，可以存放百万条、千万条、上亿条数据。但是数据库并不是随意地将数据进行存放，是有一定的规则的，否则查询的效率会很低。这里主要介绍关系型数据库。关系型数据库，存储的格式可以直观地反映实体间的关系。关系型数据库和常见的表格比较相似，关系型数据库中表与表之间是有很多复杂的关联关系的。 常见的关系型数据库有Mysql，SqlServer等。在轻量或者小型的应用中，使用不同的关系型数据库对系统的性能影响不大，但是在构建大型应用时，则需要根据应用的业务需求和性能需求，选择合适的关系型数据库。数据库的设计主要分为存储系统和程序实例两部分，程序实例又分为存储管理、缓存实例、SQL解析、日志管理、权限划分、容灾机制、索引管理、锁管理等。
索引模块
为什么要使用索引
全表扫描，当只有小部分数据，全表扫描可能比根据索引查找还快。数据量比较大的时候，因为存储的最小单位为块或者页，会把所有块或者页遍历查找，然后找到我们所需要的数据并返回，这时候全表扫描就显得不是很合适。索引和字典有异曲同工之处，将一些关键信息组织起来，比如偏旁部首，查询的时候依据这些信息，就能够快速找到想要的数据。所以使用索引能够快速查找数据。
什么样的信息能成为索引
将数据能够限定在一定查找范围之内的字段可以成为索引，主键、唯一键以及普通键等都可以成为索引。
索引的数据结构
二叉树索引
生成索引，建立二叉查找树进行二分查找：
其中P*为索引，使用二叉树作为索引，因为是二分查找，所以查询的时间复杂度为O(log n)，但当二叉树变成线性二叉树的时候，查询的时间复杂度则降为O(n)。可以通过树的旋转解决查询效率退化的问题，但是因为每次进行深层的二分查询都会有IO，影响数据库的性能主要也是IO，所以减少不必要的IO才能进一步扩大性能。
B- 树索引
B-tree，即B树，而不要读成B减树，它是一种多路搜索树（并不是二叉的），运用B-tree可以让每个索引块尽可能存储更多的信息（不想二叉树每个节点只能存储二个关键信息）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.**除根结点以外的非叶子结点的儿子数为[M/2, M]**；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）
B+ 树索引
B+树是B树的变体，其定义基本与B树相同，一颗m阶的B+树和m阶的B树的差异在于：
- 有n棵子树的结点中含有n个关键字； (而B树是n棵子树有n-1个关键字)
- 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
B+-树更适合作为存储索引：
B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
B+-tree更有利于对数据库的扫描
Hash索引
Hash索引根据key的hash值来创建哈希表存储数据，当知道具体key时能够快速查找到该条记录。
Hash索引也有些缺点：
- 仅仅能满足“=”、“IN”，不能使用范围查询
- 无法被用来避免数据的排序操作
- 不能利用部分索引键查询
- 不能避免表扫描
- 遇到大量Hash值相等的情况后性能不一定就会比B-Tree索引高
BitMap索引
位图索引只适合某个字段的值是固定的几个，位图索引的锁的粒度比较大。
密集索引和稀疏索引的区别
主要区别：
- 密集索引文件中的每个搜索码值都对应一个索引值
- 稀疏索引文件只为索引码的某些值建立索引项
InnoDB
- 若一个主键被定义，该主键则作为密集索引
- 若没有主键被定义，该表的第一个唯一非空索引则作为密集索引
- 若不满足以上条件，innodb内部会生成一个隐藏主键（密集索引）
- 非主键索引存储相关键位和其对应的主键值，包含两次查找
联合索引
最左匹配原则：
- 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配，比如a=1 and b=4 and c>5 and d=6如果建立（a，b，c，d）顺序的索引，d是用不到索引的；如果建立的是（a，b，d，c）的索引则都可以用到，a，b，d的顺序可以任意调整
- =和in可以乱序，比如a=1 and b=2 and c=3建立（a,b,c） 索引可以任意顺序，mysql的查询优化器会帮助你优化成索引可以识别的形式
最左匹配原则的成因：
如图是根据（col3,col2）组成的联合索引，建立联合索引时会根据第一个索引进行排序，然后在此基础上再根据第二个索引进行排序，以此类推。那么第一个字段是绝对有序，直接使用第二个字段则无须。
聚集索引和非聚集索引
- 聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个
- 聚集索引存储记录是物理上连续存在，而非聚集索引是逻辑上的连续，物理存储并不连续
- 聚集索引：物理存储按照索引排序；聚集索引是一种索引组织形式，索引的键值逻辑顺序决定了表数据行的物理存储顺序
- 非聚集索引：物理存储不按照索引排序；非聚集索引则就是普通索引了，仅仅只是对数据列创建相应的索引，不影响整个表的物理存储顺序
- 索引是通过二叉树的数据结构来描述的，我们可以这么理解聚簇索引：索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点，只不过有一个指针指向对应的数据块
索引是建立的越多越好呢
- 数据量小的表不需要建立索引，建立会增加额外的索引开销
- 数据变更需要维护索引，因此更多的索引意味更多的维护成本
- 更多的索引意味着也需要更多的空间
锁模块
数据库锁的分类
- 按锁的粒度划分，可分为表级锁、行级锁、页级锁
- 按锁级别划分，可分为共享锁、排它锁
- 按加锁方式划分，可分为自动锁、显示锁
- 按操作划分，可分为DML锁、DDL锁
- 按使用方式划分，可分为乐观锁、悲观锁
MyISAM与InnoDB关于锁方面的区别
主要区别：
- MyISAM默认用的是表级锁，不支持行级锁；适用场景，频繁执行全表count语句、对数据增删改的频率不高，查询非常频繁、没有事务
- InnoDB默认用的是行级锁，也支持表级锁；数据增删改查都相当频繁、可靠性要求比较高，要求支持事务
数据库事务四大特性
ACID
- 原子性（Atomic）：事务包含的操作要么全做，要么全不做
- 一致性（Consistency）：事务应确保数据库的状态从一个一个一致性转变为另一个一致性
- 隔离性（Isolation）：多个事务并发执行时，一个事务的执行，不应该影响另一个事务的执行
- 持久性（Durability）：一个事务一旦提交，则应该永久保留在数据库中，故障前提交的事务，应该确保被执行
事务隔离级别以及各级别下的并发访问问题
更新丢失：mysql所有事务隔离级别在数据库层面上均可避免
取款事务 存款事务 开始事务 开始事务 查询账户余额为100元 查询转账余额为100元 存入20元，余额变成120元 提交事务 取出10元，余额改为90元 回滚事务，余额恢复为100元 更新丢失 脏读：脏读是读到了别的事务回滚前的脏数据，READ-COMMITTED事务隔离级别以上可避免
取款事务 存款事务 开始事务 开始事务 原来余额100，取出10元，变为90，未提交事务 查询余额为90 回滚事务 存20元，提交事务。 余额变成110（脏读） 不可重复读：是指在数据库访问中，一个事务范围内两个相同的查询却返回了不同数据。REPEATABLE-READ事务隔离级别以上可避免
取款事务 查询 开始事务 开始事务 查询余额100元 原来余额100，取出10元，变为90，提交事务 查询余额90元（同一事务两次读取不一致） 幻读：一个事务(同一个read view)在前后两次查询同一范围的时候，后一次查询看到了前一次查询没有看到的行。SERIALIZABLE事务隔离级别可避免
查询事务 插入事务 开始事务 开始事务 查询所有数据，假设一共有三条 插入一条数据 更新所有数据的某一字段，update时影响了四条数据（幻读）
| 事务隔离级别 | 更新丢失 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|---|
| 未提交读 | 避免 | 发生 | 发生 | 发生 |
| 已提交读 | 避免 | 避免 | 发生 | 发生 |
| 可重复读 | 避免 | 避免 | 避免 | 发生 |
| 串行化 | 避免 | 避免 | 避免 | 避免 |
InnoDB可重复读隔离级别下如何避免幻读
首先先介绍下什么是当前读和快照读：
- 当前读：加锁的增删改查语句，无论什么锁，因为读取的是当前最新版本，还要保证并发事务不能修改当前记录，对读取记录加锁。例如：select … lock in share mode、select … for update会加共享锁，update、delete、insert会加排它锁
- 快照读：可能读取到的数据不是最新版本而是历史版本
注意：已提交读（read committed）级别下。当前读与快照读读取的版本一样。可重复读（repeatable read） 级别下，当前读返回的是数据的最新版本，**快照读返回的可能数据未修改前的版本也可能是最新的数据版本。因为在RR级别下，事务调用快照读的时机很重要，创建快照的时机决定了读取的版本。
RC、RR级别下的InnoDB的快照读（非阻塞读）如何实现
数据行关键字段
- DB_TRX_ID：该字段标明最近一次对数据做修改事务的标识符
- DB_ROLL_PTR：回滚指针，写入回滚段的undo日志
- DB__ROW_ID ：行号，随着新行出现单调递增的id
undo日志
主要分为insert undo日志（事务回滚涉及）和update undo日志（事务回滚和快照读都涉及）。对事务变更就会产生undo记录，存储的是老版数据，事务回滚需要。
undo日志工作方式，举例来说，如下图：
当事务1，对于DB_ROW_ID某一个字段进行修改时，首先用排它锁锁定改行数据，然后会copy一份修改前的数据到undo log，然后修改当前行的数据，更新事务id字段，使用回滚指定指向undo log中修改前的行，以此类推。
ReadView
主要取出DB_TRX_ID和系统其它活跃的事务id相对比，大于或者等于事务id时，然后根据DB_ROLL_PTR指针从undo log中取出当前版本
MVCC
MVCC（ Multi-Version Concurrency Control ，多版本并发控制）指的就是在使用READ COMMITTD、REPEATABLE READ这两种隔离级别的事务在执行普通的SEELCT操作时访问记录的版本链的过程。可以使不同事务的读-写、写-读操作并发执行，从而提升系统性能。 READ COMMITTD、 REPEATABLE READ这两个隔离级别的一个很大不同就是：生成ReadView的时机不同， READ COMMITTD在每一次进行普通SELECT操作前都会生成一个ReadView，而REPEATABLE READ只在第一次进行普通SELECT操作前生成一个ReadView，之后的查询操作都重复使用这个ReadView就好了。
InnoDB可重复读隔离级别下如何避免幻读
- 表象：快照读（非阻塞读）—伪MVCC
- 内在：next-key锁，（行锁+gap锁）
next-key锁，由行锁和gap锁组成。行锁就是对行记录加的锁。通过Next-key锁，InnoDB读取数据时，会增加锁，以保证事务内读取数据的一致性
Gap锁
Gap是索引树种插入新纪录的空隙，Gap锁定一个范围但不包括本身。
目的是防止同一事务的两次当前读出现幻读的情况
Repeatable-read级别以上支持Gap锁
在RR级别下，对主键索引或者唯一索引会用Gap锁的情况：
- 如果where条件全部命中，则不会用Gap锁，只会加行锁，Select * from . where id=1,2,3 这三条记录都能查得到，则称为全部命中
- 如果where条件部分命中或者全不命中，则会加Gap锁
Gap锁会用在非唯一索引或者不走索引的当前读中
(非唯一索引为啥需要gap锁，因为不是唯一，所以可能存在多条一样有不确定性)
非唯一索引Gap锁，如下图，这里操作删除id为9的数时，(6,9]和(9,11]会上Gap锁
不走索引的Gap锁，如下图，会对所有记录都上锁，相当于锁表
