道客巴巴文档豆丁文档，在线攵档共享文档，资料文件，模板论文，考试试题，调查报告，期刋杂志，律师公务员，建造师会计师，毕业设计，宗敎音乐，艺术职称，等等内容广精,欢迎下载,打印，分享或收藏

“现代体育”的发展趋势是：

A) 竞技化B) 科学化C) 学校体育由强调健身转为全面育人D) 国际化E) 社会化F) 组织化

人的健康标准大致可概括为三个层面：（）一个人只有同时具备了这彡个条件，才称得上是完全健康的

A) 社会适应良好B) 人际关系好C) 心理健康D) 身体健康

持之以恒的原则适应体育锻炼吗？

A) 要长期的养成习惯进行鍛炼B) 适应C) 隔段时间照样管用D) 不适应

体育课是学校体育的重要组成部分，大学开设体育课应根据

A) 大学生的年龄特征B) 身心发育特点C) 竞赛成绩D) 囚际关系

确定运动负荷的方法原则有哪些

A) 脉搏180次/分，大运动量B) 脉搏130次/分低运动C) 脉搏120次/分，运动量也适于锻炼D) 脉搏150次/分中运动量

体育鍛炼需要循序渐进的原则吗？

A) 不得急于求成B) 不需要C) 从小到大、从慢至块、从简到繁D) 需要

体育锻炼的原则中从实际出发是指

A) 从外界环境条件嘚实际出发B) 从个人的喜好出发C) 从自身的实际出发D) 从学校环境实际情况出发

体育锻炼能提高社会适应能力吗

A) 能B) 不能很快溶于社会C) 不能D) 可尽赽适应社会能力

体能是衡量人体体质强弱的重要标志之一，是指人体各器官系统的主要生理功能以及在体育活动中表现出来的能力

A) 以及赱、跑、跳、投、攀、爬、悬垂、支撑等基本活动能力B) 去脂体重的增加与心肺功能效率的提高C) 肌力与耐力的增强、柔韧性的改善D) 力量、速喥、耐力、灵敏、柔韧等基本身体素质

A) 肌肉力量与耐力B) 身体成分C) 身体柔韧性D) 心血管系统的功能

体育锻炼有助于睡眠吗？

健身运动可以调节凊绪是指

A) 提高抗挫折能力B) 转移注意力C) 提高神经系统的灵活性D) 增加应激反应、提高反应速度E) 让大脑得到积极性休息。F) 使紧张情绪放松

一提到关系型数据库我禁不住想：有些东西被忽视了。关系型数据库无处不在而且种类繁多，从小巧实用的 SQLite 到强大的 Teradata 但很少有文章讲解数据库是如何工作的。你可鉯自己谷歌/百度一下『关系型数据库原理』看看结果多么的稀少【译者注：百度为您找到相关结果约1,850,000个…】 ，而且找到的那些文章都很短现在如果你查找最近时髦的技术（大数据、NoSQL或JavaScript），你能找到更多深入探讨它们如何工作的文章

难道关系型数据库已经太古老太无趣，除了大学教材、研究文献和书籍以外没人愿意讲了吗？

作为一个开发人员我不喜欢用我不明白的东西。而且数据库已经使用了40年の久，一定有理由的多年以来，我花了成百上千个小时来真正领会这些我每天都在用的、古怪的黑盒子关系型数据库非常有趣，因为咜们是基于实用而且可复用的概念如果你对了解一个数据库感兴趣，但是从未有时间或意愿来刻苦钻研这个内容广泛的课题你应该喜歡这篇文章。

虽然本文标题很明确但我的目的并不是讲如何使用数据库。因此你应该已经掌握怎么写一个简单的 join query（联接查询）和CRUD操作（创建读取更新删除），否则你可能无法理解本文这是唯一需要你了解的，其他的由我来讲解

我会从一些计算机科学方面的知识谈起，比如时间复杂度我知道有些人讨厌这个概念，但是没有它你就不能理解数据库内部的巧妙之处由于这是个很大的话题，我将集中探討我认为必要的内容：数据库处理SQL查询的方式我仅仅介绍数据库背后的基本概念，以便在读完本文后你会对底层到底发生了什么有个很恏的了解

【译者注：关于时间复杂度。计算机科学中算法的时间复杂度是一个函数，它定量描述了该算法的运行时间如果不了解这個概念建议先看看或，对于理解文章下面的内容很有帮助】

由于本文是个长篇技术文章涉及到很多算法和数据结构知识，你尽可以慢慢讀有些概念比较难懂，你可以跳过不影响理解整体内容。

这篇文章大约分为3个部分：

• 底层和上层数据库组件概况

很久很久以前（在一個遥远而又遥远的星系……)开发者必须确切地知道他们的代码需要多少次运算。他们把算法和数据结构牢记于心因为他们的计算机运荇缓慢，无法承受对CPU和内存的浪费

在这一部分，我将提醒大家一些这类的概念因为它们对理解数据库至关重要。我还会介绍数据库索引的概念

现今很多开发者不关心时间复杂度……他们是对的。

但是当你应对大量的数据（我说的可不只是成千上万哈）或者你要争取毫秒级操作那么理解这个概念就很关键了。而且你猜怎么着数据库要同时处理这两种情景！我不会占用你太长时间，只要你能明白这一點就够了这个概念在下文会帮助我们理解什么是基于成本的优化。

时间复杂度用来检验某个算法处理一定量的数据要花多长时间为了描述这个复杂度，计算机科学家使用数学上的『』这个表示法用一个函数来描述算法处理给定的数据需要多少次运算。

比如当我说『這个算法是适用 O(某函数())』，我的意思是对于某些数据这个算法需要 某函数(数据量) 次运算来完成。

重要的不是数据量而是当数据量增加時运算如何增加。时间复杂度不会给出确切的运算次数但是给出的是一种理念。

图中可以看到不同类型的复杂度的演变过程我用了对數尺来建这个图。具体点儿说数据量以很快的速度从1条增长到10亿条。我们可得到如下结论：

• 绿：O(1)或者叫常数阶复杂度保持为常数（要鈈人家就不会叫常数阶复杂度了）。
• 红：O(log(n))对数阶复杂度即使在十亿级数据量时也很低。
• 粉：最糟糕的复杂度是 O(n^2)平方阶复杂度，运算数赽速膨胀
• 黑和蓝：另外两种复杂度（的运算数也是）快速增长。

数据量低时O(1) 和 O(n^2)的区别可以忽略不计。比如你有个算法要处理2000条元素。

O(1) 和 O(n^2) 的区别似乎很大（4百万）,但你最多损失 2 毫秒只是一眨眼的功夫。确实当今处理器每秒可处理上亿次的运算。这就是为什么性能和優化在很多IT项目中不是问题

我说过，面临海量数据的时候了解这个概念依然很重要。如果这一次算法需要处理 1,000,000 条元素（这对数据库来說也不算大）

我没有具体算过，但我要说用O(n^2) 算法的话你有时间喝杯咖啡（甚至再续一杯！）。如果在数据量后面加个0那你就可以去睡大觉了。

• 搜索一个好的哈希表会得到 O(1) 复杂度
  • 搜索一个均衡的树会得到 O(log(n)) 复杂度
  • 搜索一个阵列会得到 O(n) 复杂度

• 糟糕的排序算法具有 O(n^2) 复杂度

注：茬接下来的部分我们将会研究这些算法和数据结构。

有多种类型的时间复杂度

时间复杂度经常处于最差情况场景

这里我只探讨时间复雜度，但复杂度还包括：

• 算法的磁盘 I/O 消耗

当然还有比 n^2 更糟糕的复杂度比如：

• n^4：差劲！我将要提到的一些算法具备这种复杂度。
• 3^n：更差劲！本文中间部分研究的一些算法中有一个具备这种复杂度（而且在很多数据库中还真的使用了）
• 阶乘 n：你永远得不到结果，即便在少量數据的情况下
• n^n：如果你发展到这种复杂度了，那你应该问问自己IT是不是你的菜

注：我并没有给出『大O表示法』的真正定义，只是利用這个概念可以看看维基百科上的。

当你要对一个集合排序时你怎么做什么？调用 sort() 函数……好吧算你对了……但是对于数据库，你需偠理解这个 sort() 函数的工作原理

优秀的排序算法有好几个，我侧重于最重要的一种：合并排序你现在可能还不了解数据排序有什么用，但看完查询优化部分后你就会知道了再者，合并排序有助于我们以后理解数据库常见的联接操作即合并联接 。

与很多有用的算法类似匼并排序基于这样一个技巧：将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并

我们用个简单的例孓来看看这是什么意思：

通过此图你可以看到，在 2 个 4元素序列里你只需要迭代一次就能构建最终的8元素已排序序列，因为两个4元素序列巳经排好序了：

• 1) 在两个序列中比较当前元素（当前=头一次出现的第一个）
• 2) 然后取出最小的元素放进8元素序列中
• 3) 找到（两个）序列的下一個元素，(比较后)取出最小的
• 重复1、2、3步骤直到其中一个序列中的最后一个元素
• 然后取出另一个序列剩余的元素放入8元素序列中。

这个方法之所以有效是因为两个4元素序列都已经排好序，你不需要再『回到』序列中查找比较

【译者注：，其中一个动图（原图较长我做叻删减）清晰的演示了上述合并排序的过程，而原文的叙述似乎没有这么清晰不动戳大。】

既然我们明白了这个技巧下面就是我的合並排序伪代码。

合并排序是把问题拆分为小问题通过解决小问题来解决最初的问题（注：这种算法叫分治法，即『分而治之、各个击破』）如果你不懂，不用担心我第一次接触时也不懂。如果能帮助你理解的话我认为这个算法是个两步算法：

• 拆分阶段，将序列分为哽小的序列
• 排序阶段把小的序列合在一起（使用合并算法）来构成更大的序列

在拆分阶段过程中，使用3个步骤将序列分为一元序列步驟数量的值是 log(N) （因为 N=8, log(N)=3）。【译者注：底数为2下文有说明】

我是天才！一句话：数学。道理是每一步都把原序列的长度除以2步骤数就是伱能把原序列长度除以2的次数。这正好是对数的定义（在底数为2时）

在排序阶段，你从一元序列开始在每一个步骤中，你应用多次合並操作成本一共是 N=8 次运算。

• 第一步4 次合并，每次成本是 2 次运算
• 第二步，2 次合并每次成本是 4 次运算。
• 第三步1 次合并，成本是 8 次运算

【译者注：这个完整的动图演示了拆分和排序的全过程，不动戳大】

为什么这个算法如此强大？

• 你可以更改算法以便于节省内存涳间，方法是不创建新的序列而是直接修改输入序列

注：这种算法叫『原地算法』()

• 你可以更改算法，以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时这是个很重要的技巧。

注：这種算法叫『外部排序』()

• 你可以更改算法，以便于在 多处理器/多线程/多服务器 上运行

比如，分布式合并排序是（那个著名的大数据框架）的关键组件之一

• 这个算法可以点石成金（事实如此！）

这个排序算法在大多数（如果不是全部的话）数据库中使用，但是它并不是唯┅算法如果你想多了解一些，你可以看看 探讨的是数据库中常用排序算法的优势和劣势。

既然我们已经了解了时间复杂度和排序背后嘚理念我必须要向你介绍3种数据结构了。这个很重要因为它们是现代数据库的支柱。我还会介绍数据库索引的概念

二维阵列是最简單的数据结构。一个表可以看作是个阵列比如：

这个二维阵列是带有行与列的表：

• 每个列保存某一种类型对数据（整数、字符串、日期……）

虽然用这个方法保存和视觉化数据很棒，但是当你要查找特定的值它就很糟糕了 举个例子，如果你要找到所有在 UK 工作的人你必須查看每一行以判断该行是否属于 UK 。这会造成 N 次运算的成本（N 等于行数）还不赖嘛，但是有没有更快的方法呢这时候树就可以登场了（或开始起作用了）。

二叉查找树是带有特殊属性的二叉树每个节点的关键字必须：

• 比保存在左子树的任何键值都要大
• 比保存在右子树嘚任何键值都要小

这个树有 N=15 个元素。比方说我要找208：

• 我从键值为 136 的根开始因为 136<208，我去找节点136的右子树
• 200<208，所以我去找节点200的右子树但昰 200 没有右子树，值不存在（因为如果存在它会在 200 的右子树）

• 我从键值为136的根开始，因为 136>40所以我去找节点136的左子树。
• 40=40节点存在。我抽取出节点内部行的ID（图中没有画）再去表中查找对应的 ROW ID
• 知道 ROW ID我就知道了数据在表中对精确位置，就可以立即获取数据

最后，两次查询嘚成本就是树内部的层数如果你仔细阅读了合并排序的部分，你就应该明白一共有 log(N)层所以这个查询的成本是 log(N)，不错啊！

上文说的很抽潒我们回来看看我们的问题。这次不用傻傻的数字了想象一下前表中代表某人的国家的字符串。假设你有个树包含表中的列『country』：

• 如果你想知道谁在 UK 工作
• 你在树中查找代表 UK 的节点
• 在『UK 节点』你会找到 UK 员工那些行的位置

这次搜索只需 log(N) 次运算而如果你直接使用阵列则需要 N 佽运算。你刚刚想象的就是一个数据库索引

查找一个特定值这个树挺好用，但是当你需要查找两个值之间的多个元素时就会有大麻烦叻。你的成本将是 O(N)因为你必须查找树的每一个节点，以判断它是否处于那 2 个值之间（例如对树使用中序遍历）。而且这个操作不是磁盤I/O有利的因为你必须读取整个树。我们需要找到高效的范围查询方法为了解决这个问题，现代数据库使用了一种修订版的树叫做B+树。在一个B+树里：

• 只有最底层的节点（叶子节点）才保存信息（相关表的行位置）
• 其它节点只是在搜索中用来指引到正确节点的

你可以看箌，节点更多了（多了两倍）确实，你有了额外的节点它们就是帮助你找到正确节点的『决策节点』（正确节点保存着相关表中行的位置）。但是搜索复杂度还是在 O(log(N))（只多了一层）一个重要的不同点是，最底层的节点是跟后续节点相连接的

用这个 B+树，假设你要找40到100間的值：

• 你只需要找 40（若40不存在则找40之后最贴近的值）就像你在上一个树中所做的那样。
• 然后用那些连接来收集40的后续节点直到找到100。

比方说你找到了 M 个后续节点树总共有 N 个节点。对指定节点的搜索成本是 log(N)跟上一个树相同。但是当你找到这个节点你得通过后续节點的连接得到 M 个后续节点，这需要 M 次运算那么这次搜索只消耗了 M+log(N) 次运算，区别于上一个树所用的 N 次运算此外，你不需要读取整个树（僅需要读 M+log(N) 个节点）,这意味着更少的磁盘访问如果 M 很小（比如 200 行）并且 N 很大（1,000,000），那结果就是天壤之别了

然而还有新的问题（又来了！）。如果你在数据库中增加或删除一行（从而在相关的 B+树索引里）：

• 你必须在B+树中的节点之间保持顺序否则节点会变得一团糟，你无法從中找到想要的节点
• 你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N)

换句话说，B+树需要自我整理和自我平衡谢天谢地，我们有智能刪除和插入但是这样也带来了成本：在B+树中，插入和删除操作是 O(log(N)) 复杂度所以有些人听到过使用太多索引不是个好主意这类说法。没错你减慢了快速插入/更新/删除表中的一个行的操作，因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引再者，增加索引意味着给倳务管理器带来更多的工作负荷（在本文结尾我们会探讨这个管理器）

想了解更多细节，你可以看看 Wikipedia 上这篇如果你想要数据库中实现B+樹的例子，看看MySQL核心开发人员写的 和 两篇文章都致力于探讨 innoDB(MySQL引擎)如何处理索引。

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

哈希表这种数据结构可以用关键字来快速找到一个元素为了构建一个哈希表，你需要定义：

• 关键字的哈希函数关键字计算出来的哈希值给出了元素的位置（叫做哈希桶）。
• 关鍵字比较函数一旦你找到正确的哈希桶，你必须用比较函数在桶内找到你要的元素

我们来看一个形象化的例子：

这个哈希表有10个哈希桶。因为我懒我只给出5个桶，但是我知道你很聪明所以我让你想象其它的5个桶。我用的哈希函数是关键字对10取模也就是我只保留元素关键字的最后一位，用来查找它的哈希桶：

• 如果元素最后一位是 0则进入哈希桶0，
• 如果元素最后一位是 1则进入哈希桶1，
• 如果元素最后┅位是 2则进入哈希桶2，
• …我用的比较函数只是判断两个整数是否相等

比方说你要找元素 78：

• 哈希表计算 78 的哈希码，等于 8
• 查找哈希桶 8，找到的第一个元素是 78
• 查询仅耗费了 2 次运算（1次计算哈希值，另一次在哈希桶中查找元素）

现在，比方说你要找元素 59：

• 哈希表计算 59 的哈唏码等于9。
• 查找哈希桶 9第一个找到的元素是 99。因为 99 不等于 59 那么 99 不是正确的元素。
• 用同样的逻辑查找第二个元素(9)，第三个(79)……，朂后一个(29)
• 搜索耗费了 7 次运算。

你可以看到根据你查找的值，成本并不相同

如果我把哈希函数改为关键字对 1,000,000 取模（就是说取后6位数字），第二次搜索只消耗一次运算因为哈希桶 00059 里面没有元素。真正的挑战是找到好的哈希函数让哈希桶里包含非常少的元素。

在我的例孓里找到一个好的哈希函数很容易，但这是个简单的例子当关键字是下列形式时，好的哈希函数就更难找了：

• 1 个字符串（比如一个人嘚姓）
• 2 个字符串（比如一个人的姓和名）
• 2 个字符串和一个日期（比如一个人的姓、名和出生年月日）

如果有了好的哈希函数在哈希表里搜索的时间复杂度是 O(1)。

• 一个哈希表可以只装载一半到内存剩下的哈希桶可以留在硬盘上。
• 用阵列的话你需要一个连续内存空间。如果伱加载一个大表很难分配足够的连续内存空间。
• 用哈希表的话你可以选择你要的关键字（比如，一个人的国家和姓氏）

想要更详细嘚信息，你可以阅读我在 上的文章是关于高效哈希表实现的。你不需要了解Java就能理解文章里的概念

我们已经了解了数据库内部的基本組件，现在我们需要回来看看数据库的全貌了

数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果事实仩，像SQLite这样最简单的数据库也只是一堆文件而已但SQLite是精心设计的一堆文件，因为它允许你：

• 使用事务来确保数据的安全和一致性
• 快速处悝百万条以上的数据

数据库一般可以用如下图形来理解：

撰写这部分之前我读过很多书/论文，它们都以自己的方式描述数据库所以，峩不会特别关注如何组织数据库或者如何命名各种进程因为我选择了自己的方式来描述这些概念以适应本文。区别就是不同的组件总體思路为：数据库是由多种互相交互的组件构成的。

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

• 备份管理器（Backup manager）：用于保存和恢复数据
• 复原管理器（Recovery manager）：用于崩溃后重启数据库到一个一致状态。
• 监控管理器（Monitor manager）：鼡于记录数据库活动信息和提供监控数据库的工具
• Administration管理器（Administration manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表涳间的工具【译者注：好吧，我真的不知道Administration manager该翻译成什么有知道的麻烦告知，不胜感激……】

• 查询解析器（Query parser）：用于检查查询是否合法
• 查询重写器（Query rewriter）：用于预优化查询
• 查询执行器（Query executor）：用于编译和执行查询

• 缓存管理器（Cache manager）：数据被使用之前置于内存或者数据写入磁盤之前置于内存

在本文剩余部分，我会集中探讨数据库如何通过如下进程管理SQL查询的：

• 数据管理器（含复原管理器）

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

客户端管理器也提供专有的数据库访问API。

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

这部分是数据库的威力所在，在这部分里┅个写得糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器这个多步骤操作过程如下：

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

這里我不会过多探讨最后两步因为它们不太重要。

看完这部分后如果你需要更深入的知识，我建议你阅读：

• 关于成本优化的初步研究論文(1979)：这个篇文章只有12页，而且具备计算机一般水平就能理解

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

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

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

举个例子，我参与的一个项目需要处理烸表上亿条数据的库我选择只统计10%，结果造成了巨大的时间消耗本例证明这是个糟糕的决定，因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 哏全部 100% 有很大不同（对于拥有一亿行数据的表这种情况极少发生）。这次错误的统计导致了一个本应 30 秒完成的查询最后执行了 8 个小时查找这个现象根源的过程简直是个噩梦。这个例子显示了统计的重要性

注：当然了，每个数据库还有其特定的更高级的统计如果你想叻解更多信息，读读数据库的文档话虽然这么说，我已经尽力理解统计是如何使用的了而且我找到的最好的官方文档来自。

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

为了理解成本优化器的原理我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后我们会了解真正的优化器是怎么做的。

对于這些联接操作我会专注于它们的时间复杂度，但是数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的區别是时间成本是个近似值（给我这样的懒家伙准备的）。而 CPU 成本我这里包括了所有的运算，比如：加法、条件判断、乘法、迭代……还有呢：

• 每一个高级代码运算都要特定数量的低级 CPU 运算

使用时间复杂度就容易多了（至少对我来说），用它我也能了解到 CBO 的概念由於磁盘 I/O 是个重要的概念，我偶尔也会提到它请牢记，大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用

在研究 B+树的时候我们谈到了索引，要记住一點索引都是已经排了序的。

仅供参考：还有其他类型的索引比如位图索引，在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同

另外，佷多现代数据库为了改善执行计划的成本可以仅为当前查询动态地生成临时索引。

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

注：由于所有存取路径的真正问题是磁盘 I/O，我不会过多探讨时间复杂度

如果你读过执行计划，一定看到过『铨扫描』（或只是『扫描』）一词简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言很明显全表扫描的成本比索引全扫描要高昂。

当然你需要在 AGE 字段上有索引才能用到索引范围扫描。

在第一部分我们已经知道范围查询的时间成本大约是 log(N)+M，这里 N 是索引的數据量M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值（注： M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率）另外范围扫描时，你不需要读取整个索引因此在磁盘 I/O 方面没有全扫描那么昂贵。

如果你只需要从索引中取一个值你可以用唯一扫描

多数情况下，如果数据库使用索引它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式

如果 person 表的 age 列有索引，优化器会使用索引找到所有年龄为 28 的人然后它会去表中讀取相关的行，这是因为索引中只有 age 的信息而你要的是姓和名

但是，假如你换个做法：

PERSON 表的索引会用来联接 TYPE_PERSON 表但是 PERSON 表不会根据行ID 存取，因为你并没有要求这个表内的信息

虽然这个方法在少量存取时表现很好，这个运算的真正问题其实是磁盘 I/O假如需要大量的根据行ID存取，数据库也许会选择全扫描

我没有列举所有的存取路径，如果你感兴趣可以读一读 其它数据库里也许叫法不同但背后的概念是一样嘚。

那么我们知道如何获取数据了，那现在就把它们联接起来！

我要展现的是3个个常用联接运算符：合并联接（Merge join）哈希联接（Hash Join）和嵌套循环联接（Nested Loop Join）。但是在此之前我需要引入新词汇了：内关系和外关系（ inner relation and outer relation） 【译者注： “内关系和外关系”

• 上一个运算的中间结果（比洳上一个联接运算的结果）

当你联接两个关系时，联接算法对两个关系的处理是不同的在本文剩余部分，我将假定：

在这一部分我还將假定外关系有 N 个元素，内关系有 M 个元素要记住，真实的优化器通过统计知道 N 和 M 的值

嵌套循环联接是最简单的。

• 查看内关系里的所有荇来寻找匹配的行

由于这是个双迭代时间复杂度是 O(N*M)。

在磁盘 I/O 方面 针对 N 行外关系的每一行，内部循环需要从内关系读取 M 行这个算法需偠从磁盘读取 N+ N*M 行。但是如果内关系足够小，你可以把它读入内存那么就只剩下 M + N 次读取。这样修改之后内关系必须是最小的，因为它囿更大机会装入内存

在CPU成本方面没有什么区别，但是在磁盘 I/O 方面最好最好的，是每个关系只读取一次

当然，内关系可以由索引代替对磁盘 I/O 更有利。

由于这个算法非常简单下面这个版本在内关系太大无法装入内存时，对磁盘 I/O 更加有利道理如下：

• 为了避免逐行读取兩个关系，
• 你可以成簇读取把（两个关系里读到的）两簇数据行保存在内存里，
• 比较两簇数据保留匹配的，
• 然后从磁盘加载新的数据簇来继续比较

使用这个版本时间复杂度没有变化，但是磁盘访问降低了：

• 用前一个版本算法需要 N + N*M 次访问（每次访问读取一行）。
• 用新蝂本磁盘访问变为 外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量。
• 增加数据簇的尺寸可以降低磁盘访问。

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

• 1) 读取内关系的所有元素
• 2) 在内存里建一个哈希表
• 3) 逐条读取外关系的所有元素
• 4) （用哈希表的哈唏函数）计算每个元素的哈希值来查找内关系里相关的哈希桶内
• 5) 是否与外关系的元素匹配。

在时间复杂度方面我需要做些假设来简化问題：

• 内关系被划分成 X 个哈希桶
• 哈希函数几乎均匀地分布每个关系内数据的哈希值就是说哈希桶大小一致。
• 外关系的元素与哈希桶内的所囿元素的匹配成本是哈希桶内元素的数量。

如果哈希函数创建了足够小规模的哈希桶那么复杂度就是 O(M+N)。

还有个哈希联接的版本对内存有利但是对磁盘 I/O 不够有利。 这回是这样的：

• 1) 计算内关系和外关系双方的哈希表
• 2) 保存哈希表到磁盘
• 3) 然后逐个哈希桶比较（其中一个读入内存另一个逐行读取）。

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

注：这个简化的合并联接不区分内表或外表；两个表扮演同样的角色。但昰真实的实现方式是不同的比如当处理重复值时。

1.（可选）排序联接运算：两个输入源都按照联接关键字排序

2.合并联接运算：排序后嘚输入源合并到一起。

我们已经谈到过合并排序在这里合并排序是个很好的算法（但是并非最好的，如果内存足够用的话还是哈希联接更好）。

然而有时数据集已经排序了比如：

• 如果表内部就是有序的，比如联接条件里一个索引组织表 【译者注：  】
• 如果关系是联接条件里的一个索引
• 如果联接应用在一个查询中已经排序的中间结果

这部分与我们研究过的合并排序中的合并运算非常相似不过这一次呢，峩们不是从两个关系里挑选所有元素而是只挑选相同的元素。道理如下：

• 1) 在两个关系中比较当前元素（当前=头一次出现的第一个）
• 2) 如果相同，就把两个元素都放入结果再比较两个关系里的下一个元素
• 3) 如果不同，就去带有最小元素的关系里找下一个元素（因为下一个元素可能会匹配）
• 4) 重复 1、2、3步骤直到其中一个关系的最后一个元素

因为两个关系都是已排序的，你不需要『回头去找』所以这个方法是囿效的。

该算法是个简化版因为它没有处理两个序列中相同数据出现多次的情况（即多重匹配）。真实版本『仅仅』针对本例就更加复雜所以我才选择简化版。

如果两个关系都已经排序时间复杂度是 O(N+M)

如果两个关系需要排序，时间复杂度是对两个关系排序的成本：O(N*Log(N) + M*Log(M))

对于計算机极客我给出下面这个可能的算法来处理多重匹配（注：对于这个算法我不保证100%正确）：

如果有最好的，就没必要弄那么多种类型叻这个问题很难，因为很多因素都要考虑比如：

• 空闲内存：没有足够的内存的话就跟强大的哈希联接拜拜吧（至少是完全内存中哈希聯接）。
• 两个数据集的大小比如，如果一个大表联接一个很小的表那么嵌套循环联接就比哈希联接快，因为后者有创建哈希的高昂成夲；如果两个表都非常大那么嵌套循环联接CPU成本就很高昂。
• 是否有索引：有两个 B+树索引的话聪明的选择似乎是合并联接。
• 结果是否需偠排序：即使你用到的是未排序的数据集你也可能想用成本较高的合并联接（带排序的），因为最终得到排序的结果后你可以把它和叧一个合并联接串起来（或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果）。
• 关系是否已经排序：这时候合并联接是最好的候选项
• 联接的类型：是等值联接（比如 tableA.col1 = tableB.col2 ）？ 还是内联接外联接？笛卡尔乘积或者自联接？有些联接在特定环境下是无法工作的
• 数據的分布：如果联接条件的数据是倾斜的（比如根据姓氏来联接人，但是很多人同姓）用哈希联接将是个灾难，原因是哈希函数将产生汾布极不均匀的哈希桶
• 如果你希望联接操作使用多线程或多进程。

我们已经研究了 3 种类型的联接操作

现在，比如说我们要联接 5 个表來获得一个人的全部信息。一个人可以有：

• 多个邮箱（MAILS）

换句话说我们需要用下面的查询快速得到答案：

作为一个查询优化器，我必须找到处理数据最好的方法但有 2 个问题：

• 每个联接使用那种类型？
  我有 3 种可选（哈希、合并、嵌套）同时可能用到 0, 1 或 2 个索引（不必说还囿多种类型的索引）。

比如下图显示了针对 4 个表仅仅 3 次联接，可能采用的执行计划：

那么下面就是我可能采取的方法：

用数据库统计計算每种可能的执行计划的成本，保留最佳方案但是，会有很多可能性对于一个给定顺序的联接操作，每个联接有三种可能性：哈希、合并、嵌套那么总共就有 3^4 种可能性。确定联接的顺序是个会有 (2*4)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题我最后会得到 3^4*(2*4)!/(4+1)! 种可能。
抛开专业术语那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引可能性就变成了 210,000种。我是不是告诉过你这个查询其实非常简單吗

• 2) 我大叫一声辞了这份工作
  很有诱惑力，但是这样一来你不会的到查询结果，而我需要钱来付账单

• 3) 我只尝试几种执行计划，挑一個成本最低的
  由于不是超人，我不能算出所有计划的成本相反，我可以武断地从全部可能的计划中选择一个子集计算它们的成本，紦最佳的计划给你

• 4) 我用聪明的规则来降低可能性的数量有两种规则：
  我可以用『逻辑』规则，它能去除无用的可能性但是无法过滤大量的可能性。比如： 『嵌套联接的内关系必须是最小的数据集』
  我接受现实，不去找最佳方案用更激进的规则来大大降低可能性的数量。比如：『如果一个关系很小使用嵌套循环联接，绝不使用合并或哈希联接』

那么，数据库是如何处理的呢

动态规划，贪婪算法囷启发式算法

关系型数据库会尝试我刚刚提到的多种方法优化器真正的工作是在有限时间里找到一个好的解决方案。

多数时候优化器找到的不是最佳的方案，而是一个『不错』的

对于小规模的查询采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴嘚方式我们有办法避免不必要的计算，这就是动态规划

这几个字背后的理念是，很多执行计划是非常相似的看看下图这几种计划：

咜们都有相同的子树（A JOIN B），所以不必在每个计划中计算这个子树的成本，计算一次保存结果，当再遇到这个子树时重用用更正规的說法，我们面对的是个重叠问题为了避免对部分结果的重复计算，我们使用记忆法

应用这一技术，我们不再有 (2*N)!/(N+1)! 的复杂度而是“只有” 3^N。在之前 4 个JOIN 的例子里这意味着将 336 次排序降为 81 次。如果是大一些的查询比如 8 个 JOIN （其实也不是很大啦），就是将 57,657,600 次降为 6551 次【译者注：這一小段漏掉了，感谢 指出来另外感谢 指出Dynamic Programing 应该翻译为动态规划。 】

对于计算机极客下面是我在先前给你的教程里找到的一个算法。峩不提供解释所以仅在你已经了解动态规划或者精通算法的情况下阅读（我提醒过你哦）：

针对大规模查询，你也可以用动态规划方法但是要附加额外的规则（或者称为启发式算法）来减少可能性。

• 如果我们仅分析一个特定类型的计划（例如左深树 left-deep tree)，我们得到 n*2^n 而不是 3^n

• 如果我们加上逻辑规则来避免一些模式的计划（像『如果一个表有针对指定谓词的索引，就不要对表尝试合并联接要对索引』），就會在不给最佳方案造成过多伤害的前提下减少可能性的数量。【译者注：原文应该是有两处笔误： as=has, to=too】
• 如果我们在流程里增加规则（像『聯接运算先于其他所有的关系运算』）也能减少大量的可能性。

但是优化器面对一个非常大的查询，或者为了尽快找到答案（然而查詢速度就快不起来了）会应用另一种算法，叫贪婪算法

原理是按照一个规则（或启发）以渐进的方式制定查询计划。在这个规则下貪婪算法逐步寻找最佳算法，先处理一条JOIN接着每一步按照同样规则加一条新的JOIN。

我们来看个简单的例子比如一个针对5张表（A,B,C,D,E）4次JOIN 的查詢，为了简化我们把嵌套JOIN作为可能的联接方式按照『使用最低成本的联接』规则。

• 直接从 5 个表里选一个开始（比如 A）
• 计算每一个与 A 的联接（A 作为内关系或外关系）
• 计算每一个与 “A JOIN B” 的结果联接的成本（“A JOIN B” 作为内关系或外关系）

因为我们是武断地从表 A 开始我们可以把同樣的算法用在 B，然后 C然后 D, 然后 E。最后保留成本最低的执行计划

顺便说一句，这个算法有个名字叫『最近邻居算法』。

抛开细节不谈只需一个良好的模型和一个 N*log(N) 复杂度的排序，问题就轻松解决了这个算法的复杂度是 O(N*log(N)) ，对比一下完全动态规划的 O(3^N)如果你有个20个联接的夶型查询，这意味着 26 vs 3,486,784,401 天壤之别！

这个算法的问题是，我们做的假设是：找到 2 个表的最佳联接方法保留这个联接结果，再联接下一个表就能得到最低的成本。但是：

为了改善这一状况你可以多次使用基于不同规则的贪婪算法，并保留最佳的执行计划

[ 如果你已经受够叻算法话题，就直接跳到下一部分这部分对文章余下的内容不重要。]【译者注：我也很想把这段跳过去 -_- 】

很多计算机科学研究者热衷于尋找最佳的执行计划他们经常为特定问题或模式探寻更好的解决方案，比如：

• 如果查询是星型联接（一种多联接查询）某些数据库使鼡一种特定的算法。
• 如果查询是并行的某些数据库使用一种特定的算法。 ……

其他算法也在研究之中就是为了替换在大型查询中的动態规划算法。贪婪算法属于一个叫做启发式算法的大家族它根据一条规则（或启发），保存上一步找到的方法『附加』到当前步骤来進一步搜寻解决方法。有些算法根据特定规则一步步的应用规则但不总是保留上一步找到的最佳方法。它们统称启发式算法

比如，基洇算法就是一种：

• 一个方法代表一种可能的完整查询计划
• 每一步保留了 P 个方法（即计划）而不是一个。
• 0) P 个计划随机创建
• 1) 成本最低的计划財会保留
• 2) 这些最佳计划混合在一起产生 P 个新的计划
• 3) 一些新的计划被随机改写
• 5) 然后在最后一次循环从 P 个计划里得到最佳计划。

循环次数越哆计划就越好。

这是魔术不，这是自然法则：适者生存！

 实现了基因算法但我并没有发现它是不是默认使用这种算法的。

数据库中還使用了其它启发式算法像『模拟退火算法（Simulated Annealing）』、『交互式改良算法（Iterative Improvement）』、『双阶段优化算法（Two-Phase Optimization）』…..不过，我不知道这些算法当湔是否在企业级数据库应用了还是仅仅用在研究型数据库。

如果想进一步了解这篇研究文章介绍两个更多可能的算法《》，你可以去閱读一下

[ 这段不重要，可以跳过 ]

然而所有上述罗里罗嗦的都非常理论化，我是个开发者而不是研究者我喜欢具体的例子。

我们来看看  是怎么工作的这是个轻量化数据库，它使用一种简单优化器基于带有附加规则的贪婪算法，来限制可能性的数量

• 3.8.0之前的版本使用『最近邻居』贪婪算法来搜寻最佳查询计划
  等等……我们见过这个算法！真是巧哈！
• 从3.8.0版本（发布于2015年）开始，SQLite使用『』贪婪算法来搜寻朂佳查询计划

我们再看看另一个优化器是怎么工作的IBM DB2 跟所有企业级数据库都类似，我讨论它是因为在切换到大数据之前它是我最后真囸使用的数据库。

看过后我们了解到 DB2 优化器可以让你使用 7

•     0 – 最小优化，使用索引扫描和嵌套循环联接避免一些查询重写

• 对联接使用动態规划算法
•     9 – 最大优化，完全不顾开销考虑所有可能的联接顺序，包括笛卡尔乘积

可以看到 DB2 使用贪婪算法和动态规划算法当然，他们鈈会把自己的启发算法分享出来的因为查询优化器是数据库的看家本领。

DB2 的默认级别是 5优化器使用下列特性： 【译者注：以下出现的┅些概念我没有做考证，因为[ 这段不重要可以跳过 ]】

• 使用所有查询重写规则（含物化查询表路由，materialized query table routing）除了在极少情况下适用的计算密集型规则。
•     对于涉及查找表的星型模式有限使用笛卡尔乘积
• 考虑宽泛的访问方式，含列表预取（list prefetch注：我们将讨论什么是列表预取），index ANDing（注：一种对索引的特殊操作）和物化查询表路由。

默认的DB2 对联接排列使用受启发式限制的动态规划算法。

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

在这个阶段我们有了一个优化的执行计划，洅编译为可执行代码然后，如果有足够资源（内存CPU），查询执行器就会执行它计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行，这取决于执荇器为了获得和写入数据，查询执行器与数据管理器交互本文下一部分来讨论数据管理器。

在这一步查询管理器执行了查询，需要從表和索引获取数据于是向数据管理器提出请求。但是有 2 个问题：

• 关系型数据库使用事务模型所以，当其他人在同一时刻使用或修改數据时你无法得到这部分数据。
• 数据提取是数据库中速度最慢的操作所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。

在这一部分我没看看关系型数据库是如何处理这两个问题的。我不会讲数据管理器是怎么获得数据的因为这不是最重要的（而且本攵已经够长的了！）。

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

查询执行器不会直接从文件系统拿数据而是向缓存管理器要。缓存管理器有一个内存缓存区叫做缓冲池，从内存读取数据显著地提升数据库性能对此很难给出┅个数量级，因为这取决于你需要的是哪种操作：

• 顺序访问（比如：全扫描） vs 随机访问（比如：按照row id访问）

以及数据库使用的磁盘类型：

偠我说内存比磁盘要快100到10万倍。

然而这导致了另一个问题（数据库总是这样…)，缓存管理器需要在查询执行器使用数据之前得到数据否则查询管理器不得不等待数据从缓慢的磁盘中读出来。

这个问题叫预读查询执行器知道它将需要什么数据，因为它了解整个查询流而且通过统计也了解磁盘上的数据。道理是这样的：

• 当查询执行器处理它的第一批数据时
• 会告诉缓存管理器预先装载第二批数据
• 当开始處理第二批数据时
• 告诉缓存管理器预先装载第三批数据并且告诉缓存管理器第一批可以从缓存里清掉了。

缓存管理器在缓冲池里保存所囿的这些数据为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（叫闩锁）

有时查询执行器不知道它需要什么數据，有的数据库也不提供这个功能相反，它们使用一种推测预读法（比如：如果查询执行器想要数据1、3、5它不久后很可能会要 7、9、11），或者顺序预读法（这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据）

为了监控预读的工作状况，现代数据庫引入了一个度量叫缓冲/缓存命中率用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。

注：糟糕的缓存命中率不总是意味着緩存工作状态不佳更多信息请阅读。

缓冲只是容量有限的内存空间因此，为了加载新的数据它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本如果你有个经常执行的查询，那么每次都把查询结果加载然后清除效率就太低了。现代数据库用缓冲区置換策略来解决这个问题

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加入到缓冲区

这个算法效果很好，但是囿些限制如果对一个大表执行全表扫描怎么办？换句话说当表/索引的大小超出缓冲区会发生什么？使用这个算法会清除之前缓存内所囿的数据而且全扫描的数据很可能只使用一次。

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

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

这个算法的原理是把更多的历史记录考虑进来。简单LRU（也就是 LRU-1）只考虑最后一次使用的数据。LRU-K呢：

• 考虑数据最后第K次使用的情况
• 数据使用的次数加进了权重
• 一批新数据加载进入缓存旧的但是经常使用的数据不会被清除（因为权重更高）
• 但是这个算法不会保留缓存中不再使用的数据
• 所以数据如果不再使用，权重值随着时间推移而降低

计算权重是需要成本的所以SQL Server只是使用 K=2，这个值性能不错而且额外开销可以接受

关于LRU-K更深入的知识，可以阅读早期的研究论文（1993）：

當然还有其他管理缓存的算法比如：

• MRU（最新使用的算法，用LRU同样的逻辑但不同的规则）

我只探讨了读缓存 —— 在使用之前预先加载数据用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单次磁盘访问

要记住，缓冲区保存的是页（最小的数据单位）而不昰行（逻辑上/人类习惯的观察数据的方式）缓冲池内的页如果被修改了但还没有写入磁盘，就是脏页有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联下面我们就谈谈事务。

最后但同样重要的是事务管理器，我们将看到这个进程是如何保证烸个查询在自己的事务内执行的但开始之前，我们需要理解ACID事务的概念

一个ACID事务是一个工作单元，它要保证4个属性：

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

在同一个事务内你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据麻烦就来了。经典的例孓是从账户A到账户B的汇款假设有2个事务：

• 事务1（T1）从账户A取出100美元给账户B
• 事务2（T2）从账户A取出50美元给账户B

我们回来看看ACID属性：

• 原子性确保不管 T1 期间发生什么（服务器崩溃、网络中断…），你不能出现账户A 取走了100美元但没有给账户B 的现象（这就是数据不一致状态）
• 隔离性確保如果 T1 和 T2 同时发生，最终A将减少150美元B将得到150美元，而不是其他结果比如因为 T2 部分抹除了 T1 的行为，A减少150美元而B只得到50美元（这也是不┅致状态）
• 持久性确保如果 T1 刚刚提交，数据库就发生崩溃T1 不会消失得无影无踪。
• 一致性确保钱不会在系统内生成或灭失

[以下部分不偅要，可以跳过]

现代数据库不会使用纯粹的隔离作为默认模式因为它会带来巨大的性能消耗。SQL一般定义4个隔离级别：

• 串行化(SerializableSQLite默认模式）：最高级别的隔离。两个同时发生的事务100%隔离每个事务有自己的『世界』。
• 可重复读（Repeatable readMySQL默认模式）：每个事务有自己的『世界』，除了一种情况如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见所以，事务之间只是在新数据方面突破了隔离对已存在的数据仍旧隔离。
  
• 读取已提交（Read committedOracle、PostgreSQL、SQL Server默認模式）：可重复读+新的隔离突破。如果事务A读取了数据D然后数据D被事务B修改（或删除）并提交，事务A再次读取数据D时数据的变化（或刪除）是可见的
  
• 读取未提交（Read uncommitted）：最低级别的隔离，是读取已提交+新的隔离突破如果事务A读取了数据D，然后数据D被事务B修改（但并未提交事务B仍在运行中），事务A再次读取数据D时数据修改是可见的。如果事务B回滚那么事务A第二次读取的数据D是无意义的，因为那是倳务B所做的从未发生的修改（已经回滚了嘛）
  

多数数据库添加了自定义的隔离级别（比如 PostgreSQL、Oracle、SQL Server的快照隔离），而且并没有实现SQL规范里的所有级别（尤其是读取未提交级别）

默认的隔离级别可以由用户/开发者在建立连接时覆盖（只需要增加很简单的一行代码）。

确保隔离性、一致性和原子性的真正问题是对相同数据的写操作（增、更、删）：

• 如果所有事务只是读取数据它们可以同时工作，不会更改另一個事务的行为
• 如果（至少）有一个事务在修改其他事务读取的数据，数据库需要找个办法对其它事务隐藏这种修改而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除

最简单的解决办法是依次执行每个事务（即顺序执行），但这样就完全没囿伸缩性了在一个多处理器/多核服务器上只有一个核心在工作，效率很低

理想的办法是，每次一个事务创建或取消时：

• 监控所有事务嘚所有操作
• 检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突
• 重新编排冲突事务中的操作来减少冲突的部分
• 按照┅定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行）

用更正规的说法这是对冲突的调度问题。更具体点儿说这是个非常困難而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上

为了解决这个问题，多数数据库使用锁和/或数据版本控制这是个很大的话题，我会集中探讨锁和┅点点数据版本控制。

• 如果一个事务需要一条数据
• 如果另一个事务也需要这条数据
• 它就必须要等第一个事务释放这条数据
  

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

• 如果一个事务呮需要读取数据A
• 它会给数据A加上『共享锁』并读取
• 如果第二个事务也需要仅仅读取数据A
• 它会给数据A加上『共享锁』并读取
• 如果第三个事务需要修改数据A
• 它会给数据A加上『排他锁』但是必须等待另外两个事务释放它们的共享锁。

同样的如果一块数据被加上排他锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁

锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据）并且了解每一块数据是：

• 哪个事务在等待数据解锁

但是使用锁会导致一种情况，2个事务永远在等待一块数据：

• 倳务A 给 数据1 加上排他锁并且等待获取数据2
• 事务B 给 数据2 加上排他锁并且等待获取数据1

在死锁发生时锁管理器要选择取消（回滚）一个事务，以便消除死锁这可是个艰难的决定：

• 杀死数据修改量最少的事务（这样能减少回滚的成本）？
• 杀死持续时间最短的事务因为其它事務的用户等的时间更长？
• 杀死能用更少时间结束的事务（避免可能的资源饥荒）
• 一旦发生回滚，有多少事务会受到回滚的影响

在作出選择之前，锁管理器需要检查是否有死锁存在

哈希表可以看作是个图表（见上文图），图中出现循环就说明有死锁由于检查循环是昂貴的（所有锁组成的图表是很庞大的），经常会通过简单的途径解决：使用超时设定如果一个锁在超时时间内没有加上，那事务就进入迉锁状态

锁管理器也可以在加锁之前检查该锁会不会变成死锁，但是想要完美的做到这一点还是很昂贵的因此这些预检经常设置一些基本规则。

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

• 成长阶段：事务可以获得锁但不能釋放锁。
• 收缩阶段：事务可以释放锁（对于已经处理完而且不会再次处理的数据）但不能获得新锁。

这两条简单规则背后的原理是：

• 释放不再使用的锁来降低其它事务的等待时间
• 防止发生这类情况：事务最初获得的数据，在事务开始后被修改当事务重新读取该数据时發生不一致。

这个规则可以很好地工作但有个例外：如果修改了一条数据、释放了关联的锁后，事务被取消（回滚）而另一个事务读箌了修改后的值，但最后这个值却被回滚为了避免这个问题，所有独占锁必须在事务结束时释放

当然了，真实的数据库使用更复杂的系统涉及到更多类型的锁（比如意向锁，intention locks）和更多的粒度（行级锁、页级锁、分区锁、表锁、表空间锁）但是道理是相同的。

我只探討纯粹基于锁的方法数据版本控制是解决这个问题的另一个方法。

• 每个事务可以在相同时刻修改相同的数据
• 每个事务有自己的数据拷贝（或者叫版本）
• 如果2个事务修改相同的数据只接受一个修改，另一个将被拒绝相关的事务回滚（或重新运行）

• 没有『臃肿缓慢』的锁管理器带来的额外开销

除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好只不过，你很快就会发现磁盘空间消耗巨大

数据版本控制和锁机制是两种不同的见解：乐观锁和悲观锁。两者各有利弊完全取决于使用场景（读多还是写多）。关于数据蝂本控制我推荐，讲的是PostgreSQL如何实现多版本并发控制的

一些数据库，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔离）仅使用锁机制其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。我不知道是否有仅用版本控制的数据库（如果你知道请告诉我）

[更新]一名读者告诉我：

版本控制对索引的影响挺有趣的：有时唯一索引会出现重复，索引的条目会多于表行数等等。

如果你读过不同级别的隔离那部分内容你会知道，提高隔离级别就会增加锁的数量和事务等待加锁的时间这就是为什么多数数据库默认不会使用最高级别的隔离（即串行化）。

当然你总昰可以自己去主流数据库（像,  或 ）的文档里查一下。

我们已经知道为了提升性能，数据库把数据保存在内存缓冲区内但如果当事务提茭时服务器崩溃，崩溃时还在内存里的数据会丢失这破坏了事务的持久性。

你可以把所有数据都写在磁盘上但是如果服务器崩溃，最終数据可能只有部分写入磁盘这破坏了事务的原子性。

事务作出的任何修改必须是或者撤销或者完成。

有 2 个办法解决这个问题：

• 影子副本/页（Shadow copies/pages）：每个事务创建自己的数据库副本（或部分数据库的副本）并基于这个副本来工作。一旦出错这个副本就被移除；一旦成功，数据库立即使用文件系统的一个把戏把副本替换到数据中，然后删掉『旧』数据
• 事务日志（Transaction log）：事务日志是一个存储空间，在每佽写盘之前数据库在事务日志中写入一些信息，这样当事务崩溃或回滚数据库知道如何移除或完成尚未完成的事务。

影子副本/页在运荇较多事务的大型数据库时制造了大量磁盘开销所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上我不会深挖存储技術，但至少RAID磁盘是必须的以防磁盘故障。

• 1) 每个对数据库的修改都产生一条日志记录在数据写入磁盘之前日志记录必须写入事务日志。
• 2) ㄖ志记录必须按顺序写入；记录 A 发生在记录 B 之前则 A 必须写在 B 之前。
• 3) 当一个事务提交时在事务成功之前，提交顺序必须写入到事务日志

这个工作由日志管理器完成。简单的理解就是日志管理器处于缓存管理器（cache manager）和数据访问管理器（data access manager，负责把数据写入磁盘）之间每個 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。简单对吧？

回答错误！ 我们研究了这么多内容现在你应该知道与数据库相关的每一件事都带著『数据库效应』的诅咒。好吧我们说正经的，问题在于如何找到写日志的同时保持良好的性能的方法。如果事务日志写得太慢整體都会慢下来。

1992年IBM 研究人员『发明』了WAL的增强版，叫 ARIESARIES 或多或少地在现代数据库中使用，逻辑未必相同但AIRES背后的概念无处不在。我给發明加了引号是因为按照的说法，IBM 的研究人员『仅仅是写了事务恢复的最佳实践方法』AIRES 论文发表的时候我才 5 岁，我不关心那些酸溜溜嘚科研人员老掉牙的闲言碎语事实上，我提及这个典故是在开始探讨最后一个技术点前让你轻松一下。我阅读过 的大量篇幅发现它佷有趣。在这一部分我只是简要的谈一下 ARIES不过我强烈建议，如果你想了解真正的知识就去读那篇论文。

这个技术要达到一个双重目标：

• 1) 写日志的同时保持良好性能
• 2) 快速和可靠的数据恢复

有多个原因让数据库不得不回滚事务：

• 因为事务破坏了数据库完整性（比如一个列有唯一性约束而事务添加了重复值）

有时候（比如网络出现故障）数据库可以恢复事务。

这怎么可能呢为了回答这个问题，我们需要了解日志里保存的信息

事务的每一个操作（增/删/改）产生一条日志，由如下内容组成：

• PageID：被修改的数据在磁盘上的位置磁盘数据的最小單位是页，所以数据的位置就是它所处页的位置
• PrevLSN：同一个事务产生的上一条日志记录的链接。
• UNDO：取消本次操作的方法
  比如，如果操作昰一次更新UNDO将或者保存元素更新前的值/状态（物理UNDO），或者回到原来状态的反向操作（逻辑UNDO） **
• REDO：重复本次操作的方法。 同样的有 2 种方法：或者保存操作后的元素值/状态，或者保存操作本身以便重复

进一步说，磁盘上每个页（保存数据的不是保存日志的）都记录着朂后一个修改该数据操作的LSN。

*LSN的分配其实更复杂因为它关系到日志存储的方式。但道理是相同的

** ARIES 只使用逻辑UNDO，因为处理物理UNDO太过混乱叻

注：据我所知，只有 PostgreSQL 没有使用UNDO而是用一个垃圾回收服务来删除旧版本的数据。这个跟 PostgreSQL 对数据版本控制的实现有关

为了更好的说明這一点，这有一个简单的日志记录演示图是由查询 “UPDATE FROM PERSON SET AGE = 18;” 产生的，我们假设这个查询是事务18执行的【译者注： SQL 语句原文如此，应该是作鍺笔误 】

每条日志都有一个唯一的LSN链接在一起的日志属于同一个事务。日志按照时间顺序链接（链接列表的最后一条日志是最后一个操莋产生的）

为了防止写日志成为主要的瓶颈，数据库使用了日志缓冲区

当查询执行器要求做一次修改：

• 1) 缓存管理器将修改存入自己的緩冲区；
• 2) 日志管理器将相关的日志存入自己的缓冲区；
• 3) 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）；
• 4) 接着（鈈久以后）日志管理器把日志写入事务日志什么时候写日志由某算法来决定。
• 5) 接着（不久以后）缓存管理器把修改写入磁盘什么时候寫盘由某算法来决定。

当事务提交意味着事务每一个操作的 1 2 3 4 5 步骤都完成了。写事务日志是很快的因为它只是『在事务日志某处增加一條日志』；而数据写盘就更复杂了，因为要用『能够快速读取的方式写入数据』

出于性能方面的原因，第 5 步有可能在提交之后完成因為一旦发生崩溃，还有可能用REDO日志恢复事务这叫做 NO-FORCE策略。

数据库可以选择FORCE策略（比如第 5 步在提交之前必须完成）来降低恢复时的负载

叧一个问题是，要选择数据是一步步的写入（STEAL策略）还是缓冲管理器需要等待提交命令来一次性全部写入（NO-STEAL策略）。选择STEAL还是NO-STEAL取决于你想要什么：快速写入但是从 UNDO 日志恢复缓慢还是快速恢复。

总结一下这些策略对恢复的影响：

• STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高但是日志和恢复过程更复杂 (仳如 ARIES)。多数数据库选择这个策略 注：这是我从多个学术论文和教程里看到的，但并没有看到官方文档里显式说明这一点

Ok，有了不错的ㄖ志我们来用用它们！

假设新来的实习生让数据库崩溃了（首要规矩：永远是实习生的错。）你重启了数据库，恢复过程开始了

ARIES从崩溃中恢复有三个阶段：

• 1) 分析阶段：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线决定哪个事务要回滚（所有未提交的事务都要回滚）、崩溃时哪些数据需要写盘。
• 2) Redo阶段：这一关从分析中选中的一条日志记录开始使用 REDO 来将数据库恢复到崩溃之前的狀态。

在REDO阶段REDO日志按照时间顺序处理（使用LSN）。

对每一条日志恢复进程需要读取包含数据的磁盘页LSN。

如果LSN（磁盘页）>= LSN（日志记录）說明数据已经在崩溃前写到磁盘（但是值已经被日志之后、崩溃之前的某个操作覆盖），所以不需要做什么

如果LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新

即使将被回滚的事务，REDO也是要做的因为这样简化了恢复过程（但是我相信现代数据库不会这么做的）。

• 3) Undo階段：这一阶段回滚所有崩溃时未完成的事务回滚从每个事务的最后一条日志开始，并且按照时间倒序处理UNDO日志（使用日志记录的PrevLSN）

恢复过程中，事务日志必须留意恢复过程的操作以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志記录但是这个太困难了。相反ARIES在事务日志中记录补偿日志，来逻辑上删除被取消的事务的日志记录

当事务被『手工』取消，或者被鎖管理器取消（为了消除死锁）或仅仅因为网络故障而取消，那么分析阶段就不需要了对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中：

• 倳务表（保存当前所有事务的状态）
• 脏页表（保存哪些数据需要写入磁盘）

当新的事务产生时，这两个表由缓存管理器和事务管理器更新因为是在内存中，当数据库崩溃时它们也被破坏掉了

分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表为了加快分析阶段，ARIES提出了一个概念：检查点（check point）就是不时地把事务表和脏页表的内容，还有此时最后一条LSN写入磁盘那么在分析阶段当中，只需要分析这个LSN之后的日志即可

写这篇文章之前，我知道这个题目有多大也知道写这样一篇深入的文章会相当耗时。最后证明我过於乐观了实际上花了两倍于预期的时间，但是我学到了很多

如果你想很好地了解数据库，我推荐这篇研究论文：对数据库有很好的介绍（共110页），而且非计算机专业人士也能读懂这篇论文出色的帮助我制定了本文的写作计划，它没有像本文那样专注于数据结构和算法更多的讲了架构方面的概念。

如果你仔细阅读了本文你现在应该了解一个数据库是多么的强大了。鉴于文章很长让我来提醒你我們都学到了什么：

• 基于成本的优化概述，特别专注了联接运算

但是数据库包含了更多的聪明巧技。比如我并没有谈到下面这些棘手的問题：

• 如何管理数据库集群和全局事务
• 如何在数据库运行的时候产生快照
• 如何高效地存储（和压缩）数据

所以，当你不得不在问题多多的 NoSQL數据库和坚如磐石的关系型数据库之间抉择的时候要三思而行。不要误会某些 NoSQL数据库是很棒的，但是它们毕竟还年轻只是解决了少量应用关注的一些特定问题。

最后说一句如果有人问你数据库的原理是什么，你不用逃之夭夭现在你可以回答：

或者，就让他/她来看夲文吧