如果有人问你数据库的原理，叫他看这篇文章

一提到关系型数据库，我禁不住想：有些东西被忽视了。关系型数据库无处不在，而且种类繁多，从小巧实用的 SQLite 到强大的 Teradata 。但很少有文章讲解数据库是如何工作的。你可以自己谷歌/百度一下『关系型数据库原理』，看看结果多么的稀少 【译者注：百

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

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

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

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

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

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

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

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

• 底层和上层数据库组件概况
• 查询优化过程概况
• 事务和缓冲池管理概况

回到基础

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

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

O(1) vs O(n^2)

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

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

概念

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

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

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

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

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

例子

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

• O(1) 算法会消耗 1 次运算
• O(log(n)) 算法会消耗 7 次运算
• O(n) 算法会消耗 2000 次运算
• O(n*log(n)) 算法会消耗 14,000 次运算
• O(n^2) 算法会消耗 4,000,000 次运算

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

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

• O(1) 算法会消耗 1 次运算
• O(log(n)) 算法会消耗 14 次运算
• O(n) 算法会消耗 1,000,000 次运算
• O(n*log(n)) 算法会消耗 14,000,000 次运算
• O(n^2) 算法会消耗 1,000,000,000,000 次运算

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

继续深入

为了让你能明白

• 搜索一个好的哈希表会得到 O(1) 复杂度
  • 搜索一个均衡的树会得到 O(log(n)) 复杂度
  • 搜索一个阵列会得到 O(n) 复杂度
  • 最好的排序算法具有 O(n*log(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元素序列都已经排好序，你不需要再『回到』序列中查找比较。

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

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

C

1 2 3 4 5 6 7 8 9 10 11 12 13

arraymergeSort(arraya) if(length(a)==1) returna[0]; endif //recursive calls [left_array right_array]:=split_into_2_equally_sized_arrays(a); arraynew_left_array:=mergeSort(left_array); arraynew_right_array:=mergeSort(right_array); //merging the 2 small ordered arrays into a big one arrayresult:=merge(new_left_array,new_right_array); returnresult;

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

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

拆分阶段

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

我怎么知道这个的？

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

排序阶段

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

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

因为有 log(N) 个步骤，整体成本是 N*log(N) 次运算。

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

合并排序的强大之处

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

因为：

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

注：这种算法叫『原地算法』(in-place algorithm)

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

注：这种算法叫『外部排序』(external sorting)。

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

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

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

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

阵列，树和哈希表

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

阵列

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

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

• 每个行代表一个主体
• 列用来描述主体的特征
• 每个列保存某一种类型对数据（整数、字符串、日期……）

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

树和数据库索引

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

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

【译者注：binary search tree，二叉查找树/二叉搜索树，或称 Binary Sort Tree 二叉排序树。见百度百科 】

概念

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

• 我从键值为 136 的根开始，因为 136
• 398>208，所以我去找节点398的左子树
• 250>208，所以我去找节点250的左子树
• 200值不存在