数据库管理系统体系结构

DBMS内核

内核自上而下
1.编译器，语法分析器：分析结果产生语法树
2.授权检查模块：看其是否有权限进行此类操作
3.语义分析和查询处理模块：调用具体函数，以及下层访问管理（即物理层提供的访问原语）对系统进行文件操作
4.访问管理

再往下就是操作系统，再往上就是各种接口。

DBMS运行状态下的进程结构

单进程结构
应用程序和DBMS捆绑连接成一个exe
多进程结构
当我们connect某个数据库时，为当前应用创建一个DBMS核心进程，构建pipe、socket
多线程结构（Multi threads）
线程的本质实际上是一种轻量级的进程，属于同一个进程的多个线程，可以共享这个进程的资源。
跟上面类似，只不过我们每次都是在一个进程里为其创建一个线程。从而大大减少进程数

访问管理

在关系型数据库中把对数据库的操作转化成对操作系统的操作。

访问类型

1. 涉及到的元组数超过15%，就认定为需要操作most的数据。（因为硬盘是以块为单位进行操作的，并非以字节为单位，所以我们在数据库中读写其实也是以块为单位。假设数据是均匀分布的，其只要超过15%基本上就可覆盖所有块）
2. 查找某个特定元组
3. 查找小部分特定元组
4. 范围查找
5. 更新操作

关系型数据库底层数据结构：

堆文件：查找的化只能顺序扫描。配合索引扫描。适合查找most
**哈希文件：**查找特定元组
堆文件+ B+树索引：最常用，可以提高数据访问效率。B+树是一种平衡树，且叶节点之间有双向链表。
大规模查找用堆文件顺序扫描，查找特定元组用B+树索引，范围查找可以用B+树的叶节点双向链表进行范围扫描。
动态哈希：动态调整哈希的范围以最大效率利用空间
栅格结构：多维数组
簇型结构cluster，常用，raw disk：文件管理更底层的机制，允许用户自己控制数据在磁盘上怎么放。因为我们所谓的数据结构是逻辑上的存储，其经过操作系统在物理磁盘上真正的存储位置并不一定按照我们的想法。如果我们可以在磁盘上按照物理顺序存储，在寻道查找的时候就很方便，raw disk就一次性申请需要大小的磁盘，可以自己实现一套文件管理，

查询优化

关系型数据库有一个很明显的缺点是查询效率低，因为关系的连接靠另一张表连接，所以这张表可能会特别特别大。
所以我们用查询优化来解决这个问题。主要解决的问题就是，把用户的需求重写成一个效率更高的形式。然后再怎么查找。
所以这里分两步走：

1. 第一步，重写，就是代数优化。即调整用户需求的操作顺序，使得效率提升。（这里解释一下什么意思，举个例子，如果我们要求x^2 +2xy+y^2的值，我们直接可能是代数进去一步一步算，但实际上我们的需求可以变成一个完全平方式再算，就很快。）
2. 操作优化。根据数据结构。索引等实现优化。

代数优化

假设有以下需求：

我们经过语法分析，可以将其简化，从而变成以下语法树：原理可以看出来，我们要避免先进行连接，而是先进行选择、增加一些投影操作再连接，（选择是为了删除不需要的行，投影是为了删除不需要的列）到这里你大概知道了什么叫做代数优化。

查询树
叶子节点为查询对象
中间节点为一元或二元操作，从树叶到树根的顺序即为操作执行顺序。

等价变换规则

• 连接或者笛卡尔乘积的左右子树可以交换，且满足结合律
• 投影操作：连续投影等价于直接投影到最小子集上
• 选择操作：连续的选择操作可以合并
• 选择与投影操作的交换律
• 选择操作如果只包含某个对象，可以压至其二元操作之下，即先进行选择再进行二元操作。同理并关系与差关系也可。
  
  基本原则
• 利用等价变换规则，尽可能将一元操作往下压
• 寻找并且合并公共表达式

操作优化

关键问题：怎样找到一个好的策略来进行查询计算
对效率影响最大的是连接运算，所以对其的操作优化最重要。

嵌套循环
一层外循环O，一层内循环I，对外循环的每一个元组比较整个内循环。
在内存中申请两个物理块大小的缓冲区，一块放外循环数据，一块放内循环数据，每次对两个物理块进行比较。从而大大减少了IO读盘次数，同样只要内存够大，就能成倍减少，我们最好能将所有的外循环数据放到内存，而内循环每次只放一块。

归并扫描
参与的两个关系事先按照连接属性的值排好序，利用双指针算法，只需各自扫描一遍循环即可。

B+树索引/hash
把没有索引的作为外循环，放入内存，每次按照内存中连接属性不同的值查找有索引的内循环，从而避免对内循环关系作顺序扫描。
（如果索引属性重复值超出20%，用索引就不合算）

hash连接
两个表中公共的属性值相等时，对他们进行相同的hash，那么他们散列到的hash值是必定相等的

恢复机制

恢复机制分为两大块：
1.prevention 即防止系统故障
2.solving 即从故障中恢复
这就要求我们的系统：

• 数据的备份时必要的
• 机制需要能够检测出所有可能的故障（不一定能解决）

常用恢复机制：

1. 周期性备份存储（periodical dumping）：发生故障恢复至最近一次备份即可，但这样上次备份至本次故障期间的就没了。所以我们提出I.D(incremental dumping)每次只备份一些系统的增量。我们可以每隔一长段时间进行备份，每隔一小段时间就进行一次ID。
2. 备份+日志（backip+log）:日志：从上一次备份以来，对数据库进行的所有操作都记录下来。要记录改变前后的两个值（before image B.I）&(after image A.I)。发生故障后，我们重演从上次备份以后的所有日志记录。
   
   当我们进行恢复时：
   如果某些事务发生了一半：我们用BI恢复，相当于此事务没有进行过。
   如果事务已经完成了但是还没有被写入数据库，我们用AI值恢复，相当于其已经完成了。

事务与日志

对数据库进行操作的基本单位是“事务”（transaction），事务就是对数据库进行一组操作的集合：具有以下性质：
ACID

• 原子性（atomic action）：即要么全部成功，要么一条也没做。
• 保持一致性（consistency preservation）：数据库从原来的一致状态，其数据全部是正确的，经过事务的运行，到现在的一致状态。
• 隔离性（isolation）保证不同事务同时发生的时候不能互相干扰，就好像他们彼此独立占有整个数据库。
• 持久性（durability）:一个成功完成的事务对数据库产生的影响应该永久反应在数据库中，哪怕将来发生了故障，其也应该是可恢复的。

如果我们不显式的定义一个事务，那么数据库中的每一条sql语句都是一个事务

重要的数据结构
首先这些数据结构必须存储在非挥发性存储中（nonvolatile storage,即掉电之后数据还在，硬盘就是ns，但内存ram就不是）

• 提交事务列表（commit list）:每用begin transation 创建一个新的事务，其都会有一个事务表示号TID，所有已经成功完成已经提交的事务编号（TID）组成的列表
• 正在运行列表（active list）:正在运行的事务列表
• 日志log：每个事务在log中都会有一条记录，其记录TID和两个链表/文件，一个链表记录B.I，一个记录A.I。

重要规则：

1. Commit rule(提交规则)：提交之前AI必须已经被写到NS里面
2. log ahead rule先记后写规则:在我们对数据库进行更新之前，BI必须先写到日志里
3. 恢复策略
   3.1redo &undo操作：用BI进行undo还原操作n次和一次等效，用AI进行redo重做n次和一次等效。

更新策略和故障恢复

第一种：AI在commite前写入DB：相当于直接改数据库。

1. 从begin transation 开始，第一步为事务分配TID，然后将TID写入active list
2. 每步操作BI先进log，然后AI写入DB
3. 一旦提交，不需要做什么事情，我们将TID写入commit list，再将TID从active list中删除即可。

重启动恢复模块，检查每个事务的commit list和active list，以判断发生事务的瞬间，其所处的状态是怎样，有以下可能：

——只在进行，没有提交：说明这个事务做到一半，我们要用BI还原。然后从active list中删除TID
——都有，说明完成且提交了，只差最后一步，只需要从active list中删除TID即可。
——只有已提交，说明事务已经完完全全的结束了，不需要进行任何操作。
检查完了打一个检查点，所以我们每次从上一个检查点开始检查即可。

第二种：AI在提交之后才写入DB
适用于一些事务不是很容易发生，且经常容易失败的情况，我们就需要先保证这个操作没有问题，再去更改数据库。其并发性较好。
当我们需要进行更新操作的时候，我们始终先将AI写入log，然后一直等到commit的时候，再把log里所有更新写入db。

这样的流程如下：

1. 从begin transation 开始，第一步为事务分配TID，然后将TID写入active list
2. 每步更新操作先把AI写入log
3. 提交时将TID写入commit list
4. 提交之后要将log中所有的AI覆盖到DB中的BI，再将TID从active list中删除即可。

重启动恢复模块，检查每个事务的commit list和active list，以判断发生事务的瞬间，其所处的状态是怎样，有以下可能：
——如果只在active list中，没有commit说明其还没提交，更别提对数据库更改了，只需将TID从active list中删除即可。
——如果两个表中都有，说明已经提交且正在覆盖BI，需要redo AI覆盖BI的操作。然后将TID从active list中删除即可。
——如果只在commit list中，说明已经将其从活动列表中删除了，说明这个事务彻底完成了，不需要做任何事。

第三种：AI并发写入DB
和2一样先将AI写入log，但其要充分利用计算机后台资源，相当于等硬盘有空时其帮忙搬运在log中的AI到数据库中去。

1. 从begin transation 开始，第一步为事务分配TID，然后将TID写入active list
2. 将AI和BI都记入log
3. 利用后台空闲周期将log中的AI写入DB
4. 提交阶段，将TID写入commit list
5. 将剩下log中的AI完全写入DB

重启动恢复模块，检查每个事务的commit list和active list，以判断发生事务的瞬间，其所处的状态是怎样，有以下可能：
——如果只在active list 中，说明其还没进入提交阶段，对数据库已经产生了部分影响，需要undo还原。然后将TID从active list中删除即可。
——如果两个表都在，已经提交，正在搬剩下的，需要redo保证所有的都被搬入db。然后删除两个表中的tid
——如果只在commit list,说明active list中的已经被删除了，完全完成了，不需要做任何事。

并发控制

允许多个事务同时访问一个数据库。
如果我们对事务不进行并发控制，可能出现如下情况：

• 丢失更新（写写冲突）：对数据库中同一个数据同时进行写操作，导致某些写操作事实上没有发生。
• 脏读（写读冲突）：一个A事务连续读一组数，在读的期间另一个事务B修改了这组数据（即B对数据进行了写操作），导致后面A读到的数据是由B修改过的值，这时我们称A读到的数据是脏数据。因为A读到的前一个数据是B修改前的，但其读到的另一个数据却是B修改后的。这个数据不满足一致性。脏读还会导致恢复时的“多米诺效应”：如果连续几个事务都在读上一个事务写的值，当第一个事务发生故障rollback回滚的时候，后续所有事务读的这个值都需要回滚。
• 不可重复读（读写冲突）：如果事务A在重复读一个数据x，但是某两次中间事务B对这个x进行了写操作，这导致我们A本应该读到相同x却得到了不同的值。影响到了隔离性。

可串行化serializable

n个事务同时交给系统进行随机调度并发运行所产生的结果，只要其和某一种顺序产生的结果一样（即其只要是n！里面的一种），其运行结果就是可串行化的，即正确的。所以可串行化运行的事务先后是没有关系的，对结果没有影响。

*法及其锁协议

事务进行读写之前必须申请锁，如果要锁同一个数据，后者必须等前者释放这个锁才能对其进行读写操作。

1.x锁 排他锁

只提供一种x锁，不管其读还是写都申请的是这种锁。
其相容情况如下表：横行为事务上已有的锁，列上为即将进行的事务。
其中标记为：
NL ——no lock
X ——x lock
Y——compatible 相容
N——incompatible 不相容

两段加锁协议（2pl，two phase locking）
一个事务中所有的加锁请求，都在锁释放之前，我们称这个事务是一个两阶段事务。对事务额这种限制称之为两端加锁协议。（意思就是释放锁之后就不再申请新的锁了）在申请锁的阶段我们称之为增长阶段，释放锁的阶段叫做衰减阶段。

well-formed协议
事务遵守规则，在访问数据前先申请锁再对其进行操作，其就是well-formed

定理
1、如果所有的事务都是2pl+well-formed的，其一定可串行化。
2、如果所有事务都是2pl+well-formed+更新操作的锁推迟到EOT（事务结束之前）才释放，其一定可串行化，且可恢复。（不会出现多米诺效应，因为如果释放锁释放的太早了仍然可能被下一个事务读走，而我们推迟到EOT的时候再释放，就保证了后一个事务想读前一个事务的数据的时候，前一个事务必须已经结束了，前一个事务就不可能滚回了）
3、如果所有事务都是2pl+well-formed+推迟所有锁在EOT前释放，称其为严格的2pl协议。

2.S-Xlocks，读写锁

读操作申请s锁，shared -locking共享锁，不冲突
只有写操作时才申请x锁，排他锁

这样就保证了如果一个数据已经被其他事务申请了写操作x锁，你就不可能脏读，即不能再申请s锁。
同理，别人正在读，申请了s锁，你也不能申请x锁对其进行写操作。

3.s-u-x锁，更新锁

我们提出了u锁，即update lock，我们在更新数据的时候第一步得读这个数据，但是我们可能需要一段时间来处理我们想要得到的值再给他写进去，所以我们可以先申请u锁，在我们需要写的时候再将u锁升级成为x锁。
所以我们可以尽量推迟申请排他锁的时间，以保证我在只读不写的时候别的事务可以读到这个事务（这里我们可以发现u锁的设计就是为了u-s并发），提高系统运行的并发效率。

注意u锁和u锁不相容，x与其他所有锁都不相容。
所以u锁的设计和我们上一节里讲到的AI在commit之后再写入db可以一起使用，即我们要对数据进行更新就先申请u锁，更新完写入日志，等其进入提交阶段，将u锁升级为x锁，再将AI从日志中搬入DB。

死锁与活锁

死锁：多个并发运行的事务在竞争锁的时候出现了循环等待，导致没有事务可以拿到所需的资源。
如A事务先申请资源1，拿到1的x锁，B事务先申请资源2。现在A需要2，而B需要1，他俩就一直等待。

活锁：尽管其他事务在有限的时间都释放了资源，但是由于系统的调度问题，导致某个事务等待相当长的时间都拿不到锁。
如一个资源一直挨个有事务申请s锁进行读操作，这样的话如果事务B想对其进行写操作就一直拿不到x锁，导致事务B“饿死”。活锁方便解决，只需要我们按申请次序依次处理就可。

死锁的解决办法：

一 防止法

1. 要求事务在运行之前一次性申请所有锁
2. 给资源排序，让事务在申请各种资源时从权值最大的资源开始申请
3. 一旦发生冲突就都释放
4. 以上三个在数据库系统中并没有操作系统中效果好，事务重试（transation retry）
   其给每个事务安排一个唯一时间戳（time stamp），功能一作为TID来标识事务，功能二用来比较两个事务的年龄，当AB冲突时，有两种办法解决：
   1）等待老的死亡法（wait die）：比较年龄，如果A年龄比B大，就等待运行，如果A年轻，就把自己释放掉，过一会儿以之前相同的时间戳来运行。这样总是年纪大的等年纪小的，单方向等待不会有死锁。且因为他每次重试都以之前的时间戳运行，媳妇熬成婆，等老的都结束之后，他总会变成最老的，这个时候不会有年轻的事务跟他叫板，所以这个方法也不会有活锁。
   2）击伤等待法（wound wait）：同样比较年龄，相反的是，如果年轻就等待运行，如果年纪大了就让年纪小的释放，占有其资源，让他过会儿以先前的时间戳运行。这样就总是年轻的等待年老的事务，单向等待不会死锁。活锁同理，他总会变成最老的，那个时候就可以杀掉所有别的事务，就可以运行，不会活锁。
   上面两种方法如果乍一看感觉一样，其实逻辑是一样的，但是仔细想。第一种是打不过就zs法，第二种是他杀法。只要保证单向等待即可。

二 检测并解决法

1. 设置TIMEOUT，规定事务等待时间，如果超时，就认为发生死锁（不一定真的发生了死锁），将其释放，过一会儿再重新运行这个事务即可。
2. 构造有向等待图：只需定期在等待图中查找是否有环路就意味着出现死锁。（也可每个事务加入都检查一遍，但大多数系统都是每隔一段时间定期检查）一旦发现环路，就选择一个牺牲者（最年轻的事务，或者目前锁最少的事务，选择滚回代价最小的事务即可），释放掉其资源和锁，整个系统就可以接着运行，此时我们重启被牺牲的事务即可。