2 关系型数据库是如何工作的

2 关系型数据库是如何工作的

很多人在学习数据库知识的时候，知识点都是比较分散的，本章旨在将数据库知识进行整合串联，使之可以达到知其所以然的地步。

一：从数据结构说起

(1)时间复杂度

对于数据库本身而言，重要不仅仅是数据量，而是在数据量增长之后如何增加相应的运算能力？
时间复杂度用来检验某个算法处理一定量的数据要花多长时间，时间复杂度不会给出确切的运算次数，但是给出的是一种理念。
(1) 绿：O(1)或者叫常数阶复杂度，保持为常数（要不人家就不会叫常数阶复杂度了）。
(2)红：O(log(n))对数阶复杂度，即使在十亿级数据量时也很低。
(3)粉：最糟糕的复杂度是 O(n^2)，平方阶复杂度，运算数快速膨胀。
(4)黑和蓝：另外两种复杂度（的运算数也是）快速增长。
如果要处理2000条元素?
O(1) 算法会消耗 1 次运算
O(log(n)) 算法会消耗 7 次运算
O(n) 算法会消耗 2000 次运算
O(n*log(n)) 算法会消耗 14,000 次运算
O(n^2) 算法会消耗 4,000,000 次运算

(2)归并排序

理解 sort() 函数的工作原理

(3)二叉搜索树

数据库中查询的时间复杂度，是我们无法使用矩阵，转而使用二叉搜索树
二叉搜索树只需 log(N) 次运算，而如果你直接使用阵列则需要 N 次运算

(4)B+树索引

查找一个特定值这个树挺好用，但是当你需要查找两个值之间的多个元素时，就会有大麻烦了。你的成本将是 O(N)，因为你必须查找树的每一个节点，以判断它是否处于那 2 个值之间（例如，对树使用中序遍历）。而且这个操作不是磁盘I/O有利的，因为你必须读取整个树。
这就是为什么引入B+树索引
如果你在数据库中增加或删除一行（从而在相关的 B+树索引里）：
(1)你必须在B+树中的节点之间保持顺序，否则节点会变得一团糟，你无法从中找到想要的节点.
(2)你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N).

(5)哈希表

当你想快速查找值时，哈希表是非常有用的。而且，理解哈希表会帮助我们接下来理解一个数据库常见的联接操作，叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西（比如锁表或者缓冲池，我们在下文会研究这两个概念）。

为什么不用阵列呢？
(1)如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。
(2)一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
(3)用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间.

二：全局概览

我们已经了解了数据库内部的部分重要算法，现在我们需要回来看看数据库的全貌了。
数据库一般可以用如下图形来理解：

核心组件

(1)进程管理器（process manager）：很多数据库具备一个需要妥善管理的进程/线程池。再者，为了实现纳秒级操作，一些现代数据库使用自己的线程而不是操作系统线程。
(2)网络管理器（network manager）：网路I/O是个大问题，尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。
(3)文件系统管理器（File system manager）：磁盘I/O是数据库的首要瓶颈。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统，是非常重要的。
(4)内存管理器（memory manager）：为了避免磁盘I/O带来的性能损失，需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器，尤其是你有很多查询同时使用内存的时候。
(5)安全管理器（Security Manager）：用于对用户的验证和授权。
(6)客户端管理器（Client manager）：用于管理客户端连接。
…

Tools

(1)备份管理器（Backup manager）：用于保存和恢复数据。
(2)恢复管理器（Recovery manager）：用于崩溃后重启数据库到一个一致状态。
(3)监控管理器（Monitor manager）：用于记录数据库活动信息和提供监控数据库的工具
(4)管理员管理器（Administration manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。
…

Query Manager

(1)查询解析器（Query parser）：用于检查查询是否合法
(2)查询重写器（Query rewriter）：用于预优化查询
(3)查询优化器（Query optimizer）：用于优化查询
(4)查询执行器（Query executor）：用于编译和执行查询

Data Manager

(1)事务管理器（Transaction manager）：用于处理事务
(2)缓存管理器（Cache manager）：数据被使用之前置于内存，或者数据写入磁盘之前置于内存.
(3)数据访问管理器（Data access manager）：访问磁盘中的数据

三：数据查询的流程(Client Manager)

客户端管理器是处理客户端通信的。客户端可以是一个（网站）服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式来访问数据库。客户端管理器也提供专有的数据库访问API。

当你连接到数据库时：

(1)管理器首先检查你的验证信息（用户名和密码），然后检查你是否有访问数据库的授权。这些权限由DBA分配。
(2)然后，管理器检查是否有空闲进程（或线程）来处理你对查询.
(3)管理器还会检查数据库是否负载很重.
(4)管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间，它会关闭连接并给出一个可读的错误信息。
(5)然后管理器会把你的查询送给查询管理器来处理.
(6)因为查询处理进程不是『不全则无』的，一旦它从查询管理器得到数据，它会把部分结果保存到一个缓冲区并且开始给你发送。
(7)如果遇到问题，管理器关闭连接，向你发送可读的解释信息，然后释放资源。

3.1查询管理器

这部分是数据库的威力所在，在这部分里，一个写得糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器。

这个多步骤操作过程如下：

(1)查询首先被解析并判断是否合法
(2)然后被重写，去除了无用的操作并且加入预优化部分
(3)接着被优化以便提升性能，并被转换为可执行代码和数据访问计划。
(4)然后计划被编译
(5)最后，被执行

查询解析器

每一条SQL语句都要送到解析器来检查语法，如果你的查询有错，解析器将拒绝该查询.
但这还不算完，解析器还会检查关键字是否使用正确的顺序，比如 WHERE 写在 SELECT 之前会被拒绝。

然后，解析器要分析查询中的表和字段，使用数据库元数据来检查：

(1)表是否存在
(2)表的字段是否存在
(3)对某类型字段的 运算 是否 可能（比如，你不能将整数和字符串进行比较，你不能对一个整数使用 substring() 函数）
a.接着，解析器检查在查询中你是否有权限来读取（或写入）表。这些权限由DBA分配。
b.在解析过程中，SQL 查询被转换为内部表示（通常是一个树）
c.如果一切正常，内部表示被送到查询重写器。

查询重写器

在这一步，我们已经有了查询的内部表示，重写器的目标是：

(1)预优化查询
(2)避免不必要的运算
(3)帮助优化器找到合理的最佳解决方案

重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：

1.视图合并：如果你在查询中使用视图，视图就会转换为它的 SQL 代码。
2.子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询

例如：

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');

会转换为：

SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE 'christophe%';

1.去除不必要的运算符：比如，如果你用了 DISTINCT，而其实你有 UNIQUE 约束（这本身就防止了数据出现重复），那么 DISTINCT 关键字就被去掉了。
2.排除冗余的联接：如果相同的 JOIN 条件出现两次，比如隐藏在视图中的 JOIN 条件，或者由于传递性产生的无用 JOIN，都会被消除。
3.常数计算赋值：如果你的查询需要计算，那么在重写过程中计算会执行一次。比如 WHERE AGE > 10+2 会转换为 WHERE AGE > 12 ， TODATE(“日期字符串”) 会转换为 datetime 格式的日期值。
4.（高级）分区裁剪（Partition Pruning）：如果你用了分区表，重写器能够找到需要使用的分区。
5.（高级）物化视图重写（Materialized view rewrite）：如果你有个物化视图匹配查询谓词的一个子集，重写器将检查视图是否最新并修改查询，令查询使用物化视图而不是原始表。
6.（高级）自定义规则：如果你有自定义规则来修改查询（就像 Oracle policy），重写器就会执行这些规则。
7.（高级）OLAP转换：分析/加窗 函数，星形联接，ROLLUP 函数……都会发生转换（但我不确定这是由重写器还是优化器来完成，因为两个进程联系很紧，必须看是什么数据库）

统计

数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块（默认 4 或 8 KB）。这就是说如果你仅需要 1KB，也会占用一个页。要是页的大小为 8KB，你就浪费了 7KB。

当你要求数据库收集统计信息，数据库会计算下列值：

1.表中行和页的数量
2.表中每个列中的：--唯一值--数据长度（最小，最大，平均）--数据范围（最小，最大，平均）
3.表的索引信息

这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用

对每个列的统计非常重要。比如，如果一个表 PERSON 需要联接 2 个列： LAST_NAME, FIRST_NAME。根据统计信息，数据库知道FIRST_NAME只有 1,000 个不同的值，LAST_NAME 有 1,000,000 个不同的值。因此，数据库就会按照 LAST_NAME, FIRST_NAME 联接。因为 LAST_NAME 不大可能重复，多数情况下比较 LAST_NAME 的头 2 、 3 个字符就够了，这将大大减少比较的次数。

不过，这些只是基本的统计。你可以让数据库做一种高级统计，叫直方图。直方图是列值分布情况的统计信息。例如：

1.出现最频繁的值
2.出现最频繁的值
......
这些额外的统计会帮助数据库找到更佳的查询计划，尤其是对于等式谓词（例如： WHERE AGE = 18 ）或范围谓词（例如： WHERE AGE > 10 and AGE < 40），因为数据库可以更好的了解这些谓词相关的数字类型数据行（注：这个概念的技术名称叫选择率）

统计信息保存在数据库元数据内，例如（非分区）表的统计信息位置：

1.Oracle： USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
2.DB2： SYSCAT.TABLES 和 SYSCAT.COLUMNS

统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行，没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算，这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级时统计会变得困难，这时候，你可以选择仅做基本统计或者在一个数据库样本上执行统计。

3.2查询优化器

所有的现代数据库都在用基于成本的优化（即CBO）来优化查询。道理是针对每个运算设置一个成本，通过应用成本最低廉的一系列运算，来找到最佳的降低查询成本的方法。

举例：即便一个简单的联接查询对于优化器来说都是个噩梦

索引

1. 要记住一点，索引都是已经排了序的
2. 另外，很多现代数据库为了改善执行计划的成本，可以仅为当前查询动态地生成临时索引

存取路径

在应用联接运算符（join operators）之前，你首先需要获得数据。以下就是获得数据的方法：

1.全扫描--简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂
2.范围扫描--其他类型的扫描有索引范围扫描，比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生(当然，你需要在 AGE 字段上有索引才能用到索引范围扫描)
3.唯一扫描--你只需要从索引中取一个值可以用唯一扫描
4.根据 ROW ID 存取--多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。例如，假如你运行：SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28如果 person 表的 age 列有索引，优化器会使用索引找到所有年龄为 28 的人，然后它会去表中读取相关的行，这是因为索引中只有 age 的信息而你要的是姓和名但是，假如你换个做法：SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSONWHERE PERSON.AGE = TYPE_PERSON.AGEPERSON 表的索引会用来联接 TYPE_PERSON 表，但是 PERSON 表不会根据行ID 存取，因为你并没有要求这个表内的信息。虽然这个方法在少量存取时表现很好，这个运算的真正问题其实是磁盘 I/O。假如需要大量的根据行ID存取，数据库也许会选择全扫描

联接运算符

知道如何获取数据了，那现在就把它们联接起来，这里展示3种连接
1.合并联接（Merge join）
2.哈希联接（Hash Join）
3.嵌套循环联接（Nested Loop Join）
但是在此之前，需要先引入"内关系"和"外关系",这里的关系可以是：
(1)一个表
(2)一个索引
(3)上一个运算的中间结果（比如上一个联接运算的结果）

嵌套循环联接

嵌套循环联接是最简单的

哈希联接

哈希联接更复杂，不过在很多场合比嵌套循环联接成本低

哈希联接的原理是:
1.读取内关系的所有元素
2.读取内关系的所有元素
3.逐条读取外关系的所有元素 +（用哈希表的哈希函数）计算每个元素的哈希值，来查找内关系里相关的哈希桶内
4.是否与外关系的元素匹配

合并联接

合并联接是唯一产生排序的联接算法

4查询计划缓存

由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。这个话题比较大，因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限，如果一个表的统计变化超过了上限，关于该表的查询计划就从缓存中清除。

5.查询执行器

在这个阶段，我们有了一个优化的执行计划，再编译为可执行代码。然后，如果有足够资源（内存，CPU），查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行，这取决于执行器。

四：数据管理器

在这一步，查询管理器执行了查询，需要从表和索引获取数据，于是向数据管理器提出请求。但是有 2 个问题：
1.关系型数据库使用事务模型，所以，当其他人在同一时刻使用或修改数据时，你无法得到这部分数据
2.数据提取是数据库中速度最慢的操作，所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。"看看关系型数据库是如何处理这两个问题的"?请看如下的缓存管理器

缓存管理器

数据库的主要瓶颈是磁盘 I/O。为了提高性能，现代数据库使用缓存管理器

查询执行器不会直接从文件系统拿数据，而是向缓存管理器要。缓存管理器有一个内存缓存区，叫做缓冲池，从内存读取数据显著地提升数据库性能。对此很难给出一个数量级，因为这取决于你需要的是哪种操作：
1.顺序访问（比如：全扫描） vs 随机访问（比如：按照row id访问）
2.读还是写
3.以及数据库使用的磁盘类型：--7.2k/10k/15k rpm的硬盘--SSD--RAID 1/5/…
"要我说，内存比磁盘要快100到10万倍。然而，这导致了另一个问题（数据库总是这样…)，缓存管理器需要在查询执行器使用数据之前得到数据，否则查询管理器不得不等待数据从缓慢的磁盘中读出来。"请看"预读"

预读

查询执行器知道它将需要什么数据，因为它了解整个查询流，而且通过统计也了解磁盘上的数据。过程是这样的：
1.当查询执行器处理它的第一批数据时，会告诉缓存管理器预先装载第二批数据
2.当开始处理第二批数据时，告诉缓存管理器预先装载第三批数据，并且告诉缓存管理器第一批可以从缓存里清掉了。
......
缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（叫闩锁）.
有时查询执行器不知道它需要什么数据，有的数据库也不提供这个功能。相反，它们使用一种推测预读法（比如：如果查询执行器想要数据1、3、5，它不久后很可能会要 7、9、11），或者顺序预读法（这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据）。
为了监控预读的工作状况，现代数据库引入了一个度量叫缓冲/缓存命中率，用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。
注：糟糕的缓存命中率不总是意味着缓存工作状态不佳。
"缓冲只是容量有限的内存空间"，因此，为了加载新的数据，它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本。如果你有个经常执行的查询，那么每次都把查询结果加载然后清除，效率就太低了。现代数据库用缓冲区置换策略来解决这个问题。

缓冲区置换策略

多数现代数据库(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法

LRU

LRU代表最近最少使用（Least Recently Used）算法，背后的原理是：在缓存里保留的数据是最近使用的，所以更有可能再次使用。

为了更好的理解，我假设缓冲区里的数据没有被闩锁锁住（就是说是可以被移除的）。在这个简单的例子里，缓冲区可以保存 3 个元素：

1：缓存管理器（简称CM）使用数据1，把它放入空的缓冲区
2：CM使用数据4，把它放入半载的缓冲区
3：CM使用数据3，把它放入半载的缓冲区
4：CM使用数据9，缓冲区满了，所以数据1被清除，因为它是最后一个最近使用的，数据9加入到缓冲区
5：CM使用数据4，数据4已经在缓冲区了，所以它再次成为第一个最近使用的。
6：CM使用数据1，缓冲区满了，所以数据9被清除，因为它是最后一个最近使用的，数据1加入到缓冲区
……
"这个算法效果很好，但是有些限制。如果对一个大表执行全表扫描怎么办？换句话说，当表/索引的大小超出缓冲区会发生什么？使用这个算法会清除之前缓存内所有的数据，而且全扫描的数据很可能只使用一次。"

改进

为了防止这个现象，有些数据库增加了特殊的规则，比如Oracle文档中的描述：

『对非常大的表来说，数据库通常使用直接路径来读取，即直接加载区块[……]，来避免填满缓冲区。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果选择缓存读取，数据库把区块置于LRU的尾部，防止清空当前缓冲区。』

还有一些可能，比如使用高级版本的LRU，叫做 LRU-K。例如，SQL Server 使用 LRU-2
这个算法的原理是把更多的历史记录考虑进来。简单LRU（也就是 LRU-1），只考虑最后一次使用的数据。LRU-K呢：

1.考虑数据最后第K次使用的情况
2.数据使用的次数加进了权重
3.一批新数据加载进入缓存，旧的但是经常使用的数据不会被清除（因为权重更高）
4.但是这个算法不会保留缓存中不再使用的数据
5.所以数据如果不再使用，权重值随着时间推移而降低
计算权重是需要成本的，所以SQL Server只是使用 K=2，这个值性能不错而且额外开销可以接受.

写缓冲区

探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单次磁盘访问
要记住，缓冲区保存的是页（最小的数据单位）而不是行（逻辑上/人类习惯的观察数据的方式）。缓冲池内的页如果被修改了但还没有写入磁盘，就是脏页。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联，下面我们就谈谈事务。

事务管理器

一个ACID事务是一个工作单元，它要保证4个属性：
1.原子性（Atomicity）: 事务『要么全部完成，要么全部取消』，即使它持续运行10个小时。如果事务崩溃，状态回到事务之前（事务回滚）
2.一致性（Consistency）: 只有合法的数据（依照关系约束和函数约束）能写入数据库，一致性与原子性和隔离性有关。
3.隔离性（Isolation）: 如果2个事务 A 和 B 同时运行，事务 A 和 B 最终的结果是相同的，不管 A 是结束于 B 之前/之后/运行期间
4.持久性（Durability）: 一旦事务提交（也就是成功执行）,不管发生什么（崩溃或者出错），数据要保存在数据库中。

在同一个事务内，你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据，麻烦就来了。经典的例子是从账户A到账户B的汇款。假设有2个事务：
1.事务1（T1）从账户A取出100美元给账户B
2.事务2（T2）从账户A取出50美元给账户B
我们回来看看ACID属性：
1..原子性确保不管 T1 期间发生什么（服务器崩溃、网络中断…），你不能出现账户A 取走了100美元但没有给账户B 的现象（这就是数据不一致状态）。
2.隔离性确保如果 T1 和 T2 同时发生，最终A将减少150美元，B将得到150美元，而不是其他结果
3.持久性确保如果 T1 刚刚提交，数据库就发生崩溃，T1 不会消失得无影无踪
4.一致性确保钱不会在系统内生成或灭失.

并发控制

确保隔离性、一致性和原子性的真正问题是对相同数据的写操作（增、更、删）：
1.如果所有事务只是读取数据，它们可以同时工作，不会更改另一个事务的行为。
2."如果（至少）有一个事务在修改其他事务读取的数据"，数据库需要找个办法对其它事务隐藏这种修改。而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。
这个问题叫"并发控制"。
最简单的解决办法是依次执行每个事务（即串行），但这样就完全没有伸缩性了，在一个多处理器/多核服务器上只有一个核心在工作，效率很低。"理想状态"
理想的办法是，每次一个事务创建或取消时：
1.监控所有事务的所有操作
2.检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突
3.检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突
4.按照一定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行）
5.考虑事务有可能被取消。
用更正规的说法，这是对冲突的调度问题。更具体点儿说，这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时，来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。

锁管理器

为了解决这个问题，多数数据库使用"锁"和/或"数据版本控制"

悲观锁

悲观锁的原理:
1.如果一个事务需要一条数据,就把数据锁住
2.如果另一个事务也需要这条数据, 它就必须要等第一个事务释放这条数据.

这个锁叫排他锁
但是对一个仅仅读取数据的事务使用排他锁非常昂贵，因为这会迫使其它只需要读取相同数据的事务等待。因此就有了另一种锁，共享锁

共享锁是这样的：
1.如果一个事务只需要读取数据A, 它会给数据A加上『共享锁』并读取
2.如果第二个事务也需要仅仅读取数据A, 它会给数据A加上『共享锁』并读取
3.如果第三个事务需要修改数据A, 它会给数据A加上『排他锁』，但是必须等待另外两个事务释放它们的共享锁。
同样的，如果一块数据被加上排他锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据），并且了解每一块数据是：
1.被哪个事务加的锁
2.哪个事务在等待数据解锁

死锁 2个事务永远在等待一块数据

在本图中：
事务A 给 数据1 加上排他锁并且等待获取数据2
事务B 给 数据2 加上排他锁并且等待获取数据1

在死锁发生时，锁管理器要选择取消（回滚）一个事务，以便消除死锁。这可是个艰难的决定：
1.杀死数据修改量最少的事务（这样能减少回滚的成本）？
2.杀死持续时间最短的事务，因为其它事务的用户等的时间更长？
3.杀死能用更少时间结束的事务（避免可能的资源饥荒）？
4.一旦发生回滚，有多少事务会受到回滚的影响？在作出选择之前，锁管理器需要检查是否有死锁存在。
锁管理器也可以在加锁之前检查该锁会不会变成死锁，但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。

两段锁

实现纯粹的隔离最简单的方法是：事务开始时获取锁，结束时释放锁。就是说，事务开始前必须等待确保自己能加上所有的锁，当事务结束时释放自己持有的锁。这是行得通的，但是为了等待所有的锁，大量的时间被浪费了

更快的方法是两段锁协议,将事务分为两个阶段：

1.成长阶段：事务可以获得锁，但不能释放锁。
2.收缩阶段：事务可以释放锁（对于已经处理完而且不会再次处理的数据），但不能获得新锁。
这两条简单规则背后的过程是：
1.释放不再使用的锁，来降低其它事务的等待时间
2.防止发生这类情况：事务最初获得的数据，在事务开始后被修改，当事务重新读取该数据时发生不一致。
这个规则可以很好地工作，但有个例外：如果修改了一条数据、释放了关联的锁后，事务被取消（回滚），而另一个事务读到了修改后的值，但最后这个值却被回滚。为了避免这个问题，所有独占锁必须在事务结束时释放。

数据版本控制是解决这个问题的另一个方法

版本控制是这样的：
1.每个事务可以在相同时刻修改相同的数据
2.每个事务有自己的数据拷贝（或者叫版本）
3.如果2个事务修改相同的数据，只接受一个修改，另一个将被拒绝，相关的事务回滚（或重新运行）
这将提高性能，因为：
1.读事务不会阻塞写事务
2.写事务不会阻塞读
3.没有『臃肿缓慢』的锁管理器带来的额外开销
除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好。只不过，你很快就会发现磁盘空间消耗巨大。
"数据版本控制和锁机制是两种不同的见解"：乐观锁和悲观锁。两者各有利弊，完全取决于使用场景（读多还是写多）.
一些数据库，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔离）仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。