关系型数据库如何运行

当提到关系数据库，不由自主地认为缺少了些重要信息。这些数据库无所不在，发挥着他们的作用，他们包括了小巧的sqlite,强大的Teradat。但是少有文章去说明数据的运行原理。你可以搜索 “how does a relational database work”【关系数据库运行原理】来了解这样的文章有多么少。如果你去搜索现在这些流行技术（大数据，Nosql和javascript），你会找到大量深入的文章在说明这些技术的运行原理。关系数据库太不流行太没意思，以至于出了大学课堂，就找不到书和研究资料去阐明它的运行原理？

作为一个开发者，我非常不喜欢用一些我不理解的技术/组件。即使数据库已经经过了40年运用的检验，但是我依然不喜欢。这些年，我花费了上百小时的时间去研究这些每天都用的奇怪的黑匣子。关系型数据库的有趣也因为他门构建在有效和重用的理念上。如果你要了解数据库，而有没有时间或者没有毅力去了解这个宽泛的话题，那么你应该阅读这篇文章。

虽然文章标题已经足够明确，本文的目的不是让你学习怎么使用一个数据库.但是,你应该已经知道怎么写一个简单的连接查询和基本的增删改查的查询，否则，你就不能明白本文。这就是现在必须要知道，我将解释为什么需要这些提前的知识。

我将从时间复杂度开始开始这些计算机科学知识。当然当然，我晓得有些朋友不喜欢这些观点但是不了解这些，我们就不明白数据库中使用的技巧。这是一个庞大的话题，我将聚焦于非常必要的知识上，数据库处理SQL查询的方法。我将只涉及数据库背后的基本观念，让你在本文结束的时候了解水面下发生了什么。

这是一篇又长又有技术性的文章，涉及了很多算法和数据结构，总之不怎么好理解，慢慢看吧同学。其有一些观点确实不容易理解，你把它跳过去也能得到一个比较全面的理解（译者注：这篇博文对于学习过《数据结构》的同学，不算是很难，即使有一些难以理解的观点，要涉及技术的特性，这是使用这些许技的原因，对应能够明白使用技术要达成的结果）。

本文大体分为3个部分，为了方便理解：

• 底层技术和数据库模块
• 查询优化技术
• 事物和内存池管理

[TOC] 

回归基础

很久以前（估计有银河系诞生那么久远...），开发人员不得不精通非常多的编程操作。因为他们不能浪费他们龟速电脑上哪怕一丁点儿的CPU和内存，他们必须将这些算法和相应的数据结构深深的记在心里。

在这个部分，我将带你们回忆一些这样的概念，因为它们对于理解数据库是非常必要的。我也将会介绍数据库索引这个概念。 

O(1)) vs O(n2)

现在，许多开发者不再关心时间复杂度...他们是对的！ 
但是当你们正面临着一个大数据量（我谈论的并不是几千这个级别的数据）的处理问题时或者正努力为毫秒级的性能提升拼命时，理解这个概念就非常的重要了。可是你们猜怎么着？数据库不得不处理这两种极端情况！我不会占用你们太多时间，只需要将这个点子讲清楚就够了。这将会帮助我们以后理解成本导向最优化的概念。 

基本概念

时间复杂度时用来衡量一个算法处理给定量的数据所消耗时间多少的。为了描述这个复杂事物，计算机科学家们用数学上的大写字母O符号.这个符号用来描述了在方法中一个算法需要多少次操作才能处理完给定的输入数据量。 
例如，当我说”这个算法是在O(some_funtion())“时，这意味着这个算法为了处理确定量的数据需要执行some_function(a_certain_amount_of_data)操作. 
最重要的不是数据量，而是随着数据量的增加，操作步骤需要随之变化的方式。时间复杂度不是给出确切的操作数量而是一个概念。 

在上图中，你可以看到不同类型的复杂度演变的方式。我用了对数尺度来描绘。换句话讲，当数据的量从1到10亿，我们可以看到：

• O(1)即常数复杂度保持常数操作数（不然它就不叫常数复杂度了）。
• O(log(n)) 即使是上亿级的数据仍保持较低操作数。
• 最差的复杂度是O(n2) ,它的操作数是爆炸式增长。
• 另外两种复杂度增长快速。

举例

当小数据量时，O(1)与O(n2)之间的差距是微乎其微的。例如，假设你需要处理2000条数据的算法。

• O(1)算法需要1次操作
• O(log(n))算法需要7次操作
• O(n)算法需要2000次操作
• O(n*log(n))算法需要14000次操作
• O(n2)算法需要4000000次操作

O(1)与O(n2)之间的区别似乎非常大（4百万倍），但是你实际上最多多消耗2毫秒，和你眨眼的时间几乎相同。的确，现在的处理器能处理每秒数以百万计指令。这就是为什么在许多IT工程中性能和优化并不是主要问题的原因。 


正如我所说，当面对海量数据时，了解这个概念还是非常重要的。如果这时算法需要处理1000000条数据（对于数据库来说，这还不算大）：

• O(1)算法需要1次操作
• O(log(n))算法需要14次操作
• O(n)算法需要1000000次操作
• O(n*log(n))算法需要14000000次操作
• O(n2)算法需要1000000000000次操作

我没有详细算过，但是我想如果采用O(n2)算法，你可以有时间来杯咖啡了（甚至再来一杯！）。如果你又将数据数量级提升一个0，你可以有时间去打个盹儿了。 

继续深入

给你一个概念：

• 从一个哈希表中进行元素查找操作的复杂度是O(1)
• 从一个平衡树中进行查找操作的复杂度时O(log(n))
• 从数组中进行一次查找操作的复杂度O(n)
• 最优的排序算法的复杂度是O(n*log(n))。
• 差的排序算法的复杂度是O(n2)
  

注意：在之后的内容中，我们将会看到这些算法和数据结构。 

存在着多种种类的时间复杂度：

• 平均情况
• 最优情况
• 以及最差情况

时间复杂度经常是最差情况。 
我仅讨论时间复杂度，实际上复杂度还适用于：

• 算法的内存消耗
• 算法的磁盘I/O消耗

当然也有比n2还差的复杂度情况，例如：

• n4：糟糕透了！我将会提到一些如此复杂度的算法。
• 3n：不能再糟了! 我们在本文中间部分将会看到这样复杂度的一个算法(而且在许多数据中，它确实在被使用着)。
• n的阶乘 : 即使是很小数量级的数据，你也将永远得不到你想要的结果。
• nn: 如果你最终的结果是这个算法复杂度，你应该好好问问自己到底是不是做IT的…
  

注意：我并没有给你O符号的真正定义，而只是抛出这个概念。如果你想找到真正的定义，你可以阅读这篇WikiPedia材料。 

归并排序

如果你需要排序一个集合，你会怎么做？什么？你会调用sort()函数... 好吧，真是个好答案...但是对于数据库来说，你必须懂得sort()函数是如何工作的。

因为有太多好的排序算法，所以我将专注于最重要的一个：归并排序。此时此刻你可能不是很明白为什么数据排序会有用，但是当完成这个部分的查询优化后，你肯定会懂得。进一步来说，掌握归并排序将有助于后续我们对一般数据库中合并连接操作的理解。 

合并

如同许多有用的算法，归并排序是基础的技巧：合并2个长度为N/2的有序数组为一个有N个元素的有序数组仅消耗N次操作。这个操作称为一次合并。

让我们通过一个简单例子来看看其含义： 

你能从图中看到最终排序好8个元素的数组的结构，你仅需要重复访问一次2个4元素数组。因为这2个4元素数组已经排序好了：

• 1) 你需要比较两个数组当前的元素（第一次的时候current=first）
• 2) 接下来将最小的那个放进8元素数组中
• 3) 将你提取最小元素的那个数组指向下一个元素
• 重复1，2，3步骤，直到你到达任何一个数组的最后一个元素.
• 接下来，你需要将另外一个数组的剩余元素放进8元素数组中。

这个算法之所以生效是因为4元素数组都是已经排序好的，因此你不必在这些数组中进行"回退"。

现在我们懂得了这个技巧，如下所示是我的合并排序伪代码。

array mergeSort(array a) if(length(a)==1) return a[0]; end if //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a); array new_left_array := mergeSort(left_array); array new_right_array := mergeSort(right_array); //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array); return result;

归并排序将问题拆分为更小的问题，再求解这些小问题结果，从而获得最初的问题结果（注意：这类算法叫做分治法）。如果你不懂这个算法，不用担心；我最初看这个算法时也是不懂。我将这个算法看作两个阶段算法，希望对你们有所帮助：

• 将一个数组才分为更小的数组称为分解阶段
  
• 将小的数组组合在一起（使用合并）组成更大的数组称为排序阶段。

分解阶段

在分解阶段中，数组被拆分为单一的数组用了3步。步骤数量的表达式为log(N)(由于 N=8，log(N) ＝ 3)。

我是怎么知道的呢？

我是个天才！总之：数学。每一步的核心是将最初的数组长度对半拆分。步骤数量就是你能二分原始数组的次数。这就是对数的定义（以2为底）。 

排序阶段

在排序阶段中，你将从单一数组开始。在每一步中，你使用多重汇集。总共需要N=8次操作：

• 第一步，你将做4次合并，每次需要2步操作
• 第二步，你将进行2次合并，每次需要4步操作
• 第三步，你将做1次合并，每次需要8步操作

因为总共有log(N)个步骤，总共需要N * log(N)次操作。 

归并排序的威力

为什么这个算法有如此威力？

缘由如下：

• 你可以将它改造为低内存占用型，通过不再建立一个新的数组而是直接修改输入数组。 注意：这种算法称为原地算法
• 你可以将它改造为使用磁盘空间和更小的内存占用的同时，避免大量的磁盘I/O消耗。这个算法的理念是每次只加载当前处理的部分数据进入内存。当你只有100M内存空间却需要对数G大小的表进行排序时，这个算法将十分重要。 注意：这种算法称为外部排序。
• 你可以将这个算法改造为运行在多处理器/线程/服务器。 例如，分布式归并排序就是Hadoop的核心模块（一种大数据框架）。
• 这个算法能点石成金（真的！）。
  

这个排序算法应用于大多数（好吧，如果不是全部）数据库，但是它不是唯一的。如果你想了解更多，你可以阅读这个研究材料，这里面讨论了数据库中所使用到的通用排序算法的优缺点。 

数组，树以及哈希表

我们已经了解时间复杂度和排序背后的机理，我必须给你讲3种数据结构。它们十分重要，因为它们是现代数据库的支柱。同时我也会介绍数据库索引。 

数组

二维数组是最简单的数据结构。表格也能看成是一个数组。如下： 
二维数组就是一个行列表：

• 每行表示一个对象
• 列表示描述对象的特性
• 每列存储一种特定类型的数据(整型，字符串，日期 ...)。
  

尽管这样存储和数据可视化都非常好，但是当你面对特殊数据时，这个就很糟了。

例如，如果你想找到所有工作在英国的人，你将不得不查看每一行看这一行是否属于英国。这将消耗你N步操作（N是行数），这并不算太坏，但是否又有更好的方式呢？这就是为什么要引入tree。

注意：大多数现代数据库提供了增强型数组来高效的存储表单，例如：堆组织表或索引组织表。但是他并没有解决特殊值在列集合中的快速查找问题。 

树和数据库索引

二叉搜索树时一种带有特殊属性的二叉树，每个节点的键值必须满足：

• 大于所有左子树的键值
• 小于所有右子树的键值

让我们直观的看看上面的含义 

概念 

这棵树有 N=15 个节点构成。假设我们搜索208：

• 我将从根节点的键值136开始，因为136<208，所以我们查找136节点的右子树。
• 398>208 所以，我们查找398节点的左子树
• 250>208 所以，我们查找250节点的左子树
• 200<208 所以，我们查找200节点的右子树。但是200节点没有右子树，这个值不存在（如果它存在，那么它必定在200节点的右子树中)

接下来假设我们查找40

• 我将从根节点的键值136开始，因为136>40，所以我们查找136节点的左子树。
• 80>40 所以，我们查找80节点的右子树
• 40=40，节点存在。提取出节点的行号(这个没在图上)，然后根据行号查询数据表。
• 获得了行号，我们就可以知道数据在表上的精确位置，因此我们就能立即获取到数据。

最后，这两个查询都消耗树的层数次操作。如果你仔细地阅读了归并排序部分，那么就应该知道这里是log(N)层级。所以知道搜索算法的时间复杂度是log(N)，不错！ 

回到我们的问题上

但是这些东西还是比较抽象，我们回到我们具体的问题中。取代了前一张表中呆滞的整型，假想用字符串来表示某人的国籍。假设你又一棵包含了表格中“国籍”列的树：

• 如果你想知道谁在英国工作
• 你查找这棵树来获取代表英国的节点
• 在“英国节点”中，你将找到英国工人的行地址。
  

这个查找仅需要log(N)次操作而不是像使用数组一样需要N次操作。你们刚才猜想的就是数据库索引。

只要你有比较键值（例如 列组）的方法来建立键值顺序（这对于数据库中的任何一个基本类型都很重要），你可以建立任意列组的树形索引（字符串，整型，2个字符串，一个整型和一个字符串，日期...）。 

B+树索引

尽管树形对于获取特殊值表现良好，但是当你需要获取在两个值范围之间的多条数据时还是存在着一个大问题。因为你必须查询树种的每个节点看其是否在两值范围之间（例如，顺序遍历整棵树）。更糟的是这种操作很是占用磁盘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))次操作。更糟的是，添加索引意味着事务管理(我们将在本文最后看到这个管理)更多的工作量。

更多详情，可以查看维基百科B+树资料。如果你想知道数据库中B+树的实现细节，请查看来自MySQL核心开发者的博文和博文。这两个材料都是聚焦于innoDB(MySQL数据库引擎)如何处理索引。

注意：因为我被一个读者告知，由于低级优化，B+树需要完全平衡。 

哈希表

我们最后一个重要的数据结构是哈希表。当你想快速查找值的时候这会非常有用。更好的是了解哈希表有助于掌握数据库通用连接操作中的哈希连接。这个数据结构也用于数据库存储一些中间量（如我们稍后会提到的锁表或缓冲池概念）。

哈希表是一种利用其键值快速查找元素的数据结构。为了建立哈希表，你需要定义：

• 为元素建立的键
• 为键建立的哈希方法。为键算出的哈希值可以定位元素（称为哈希桶）。
• 键之间的比较方法。一旦你找到了目标桶，你必须使用这个比较方法来查找桶内的元素。

一个简单例子

让我们来看看图形示例： 

这个哈希表有10个哈希桶。换句话说，我只使用元素的最后一个数字来查找它的哈希桶：

• 如果元素的最后一个数字是0，那么就存在于0号哈希桶中，
• 如果元素的最后一个数字是1，那么就存在于1号哈希桶中，
• 如果元素的最后一个数字是2，那么就存在于2号哈希桶中，
• ...

我所使用的比较方法仅仅是简单的比较2个整型是否相等。
假设你想查找一个78的元素：

• 哈希表首先计算出78的哈希值是8。
• 接下来它查看8号哈希桶，并找到第一个元素就是78。
• 它就返回给你78的元素
• 这次查找仅需要2步操作（1步是计算哈希值而另一步则是查找哈希桶里面的元素）。

接下来，假设你想找到59的元素：

• 哈希表首先计算59的哈希值为9。
• 它查找9号哈希桶，第一个找到的元素是99。因为99!=59，99元素不是目标元素。
• 使用相同的逻辑，它找到第二个元素(9)，第三个(79)，...，直到最后一个(29)。
• 该元素不存在。
  

优秀的哈希方法

如你所见，根据你查找的值不同，消耗也是不同的！

如果现在我改用键值除以1 000 000的哈希方法（也就是取最后6位数字），第二个查找方法仅需要1步操作，因为不存在000059号的哈希桶。真正的挑战是找到一个创建能容纳足够小元素的哈希桶的哈希方法。

在我的例子中，找到一个好的哈希方法是非常容易的。但是由于这是个简单的例子，当面对如下键时，找到哈希方法就非常困难了：

• 字符串(例如人的姓氏)
• 2个字符串(例如人的姓氏和名字)
• 2个字符串和一个日期(例如人的姓氏，名字以及生日)
• ...
  

如果有一好的哈希方法，在哈希表中查找的复杂度将是O(1)。 

数组与哈希表的比较

为什么不使用数组?
嗯, 你问了一个好问题。

• 哈希表能一半在内存中加载，而其余的哈希桶保存在磁盘上。
• 如果使用数组，你必须使用内存中的连续内存。如果你正在加载一张较大的表，系统是很难分配出足够大的连续空间的。
• 如果使用哈希表，你可以任意选择你想要的键(例如：国家 AND 姓氏)。

想要更多的信息，你可以阅读我的博文一个高效哈希表的实现Java HashMap；你可以读懂这个文章内容而不必掌握Java。 

总体结构

我们已经理解了数据库使用的基本组件，我们需要回头看看这个总体结构图。
数据库就是一个文件集合，而这里信息可以被方便读写和修改。通过一些文件，也可以达成相同的目的（便于读写和修改）。事实上，一些简单的数据库比如SQLite就仅仅使用了一些文件。但是SQLite是一些经过了良好设计的文件,因为它提供了以下功能：

• 使用事务能够保证数据安全和一致性
• 即使处理百万计的数据也能高效处理

一般而言，数据库的结构如下图所示: 
 
在开始写之前，我曾经看过很多的书和论文，而这些资料都从自己的方式来说明数据库。所以，清不要太过关注我怎么组织数据库的结构和对这些过程的命名，因为我选择了这些来配置文章的规划。不管这些不同模块有多不一样，但是他们总体的观点是数据库被划分为多个相互交互的模块。

核心模块:

• 进程管理器: 很多的数据库都有进程/线程池需要管理，另外，为了达到纳秒级（切换），一些现代的数据库使用自己实现线程而不是系统线程。
• 网络管理器: 网络IO是一个大问题，尤其是分布式数据库。这就是一些数据库自己实现管理器的原因。
• 文件系统管理器: 磁盘IO是数据库的第一性能瓶颈。文件系统管理器太重要了，他要去完美使用OS文件系统，甚至自己取而代之。
• 内存管理器: 为了避免磁盘IO带来是惩罚，我们需要很大的内存。但是为了有效的使用这些内存，你需要一个有效率的内存管理器。尤其在多个耗内存的查询操作同时进行的时候。
• 安全管理器: 为了管理用户的验证和授权。
• 客户端管理器: 为了管理客户端连接..
• .......

工具类:

• 备份工具: 保存和恢复一个数据库。
• 恢复工具: 使据据库在崩溃重启之后，重新达到一致性的状态。
• 监控工具: 记录数据库所有的行为，需要提供一个监控工具去监控数据库。
• 管理工具: 保存元数据（比如表的结构和名字），并提供工具去管理数据库，模式，表空间等等。
• ......

查询管理器:

• 查询解析器: 确认查询是否合法
• 查询重写器: 优化查询的预处理
• 查询优化器: 优化查询语句
• 查询执行器: 编译执行一个查询
• ......

数据管理器:

• 事务管理器: 管理事务
• 缓存管理器: 在使用数据或者修改数据之前，将数据载入到内存，
• 数据访问: 访问磁盘上数据

本文剩下部分，我将关注于数据库如何处理SQL查询的过程：

• 客户端管理器
• 查询管理器
• 数据管理器（我也将在这里介绍恢复管理工具）

客户端管理器

 
客户端管理器是处理和客户端交互的部分。一个客户端可能是（网页）服务器或者终端用户或者终端程序。客户端管理器提供不同的方法（广为人知的API: JDBC, ODBC, OLE-DB）来访问数据库。 当然它也提供数据库特有的数据库APIs。 

当我们连接数据库：

• 管理器首先验证我们的身份（通过用户名和密码）接着确认我们是否有使用数据库的授权，这些访问授权是你们的DBA设置的。
• 接着，管理器确认是否有空闲的进程(或者线程)来处理你的这次请求。
• 管理器也要确认数据库是否过载。
• 管理器在得到请求的资源（进程/线程）的时候，当等待超时，他就关闭这个连接，并返回一个易读的出错信息。
• 得到进程/线程之后，就把这个请求传递给查询管理器，这次请求处理继续进行。

• 查询过程不是一个all or nothing的过程，当从查询管理器获取数据之后，就立刻将这些不完全的结果存到内存中，并开始传送数据。

• 当遇到失败，他就中断连接，返回给你一个易读的说明，并释放使用到的资源。

查询管理器

 
这部分是数据库的重点所在。在本节中，一个写的不怎么好的查询请求将转化成一个飞快执行指令代码。接着执行这个指令代码，并返回结果给客户端管理器。这是一个多步骤的操作。

• 查询语句将被解析，看它是否有效。
• 接着在它之上去除无用的操作语句，并添加预处理语句，重写出来。
• 为了优化这个查询，提供查询性能，将它转化成一个可执行的数据访问计划。
• 编译这个计划。
• 最后，执行它。 
  这部分，我不打算就爱那个很多在最后两点上，因为他们不是那么重要。 
  
  

阅读完这部分之后，你将容易理解我推荐你读的这些材料： 

• 最初的基于成本优化的研究论文： Access Path Selection in a Relational Database Management System. 这篇文章只有12页，在计算机科学领域是一片相对易懂的论文。

• 针对DB2 9.X查询优化的非常好，非常深深入的文档here

• 针对PostgreSQL查询优化的非常好的文档here。这是非常容易理解的文档，它更展示的是“PostgreSQL在不同场景下，使用相应的查询计划”，而不是“PostgreSQL使用的算法”。

• SQLite关于优化的官方SQLite documentation 文档。非常容易阅读，因为SQLite使用的非常简单的规则。此外，这是为唯一一个真正解释如何使用优化规则的文档。

• 针对SQL Server 2005查询优化的非常好的文档here

• Oracle 12c 优化白皮书 here

• “DATABASE SYSTEM CONCEPTS”作者写的两个关于查询优化的2个理论课程here and here. 关注于磁盘I/O一个很好的读物，但是需要一定的计算机科学功底。

• 另一个非常易于理解的，关注于联合操作符，磁盘IO的 理论课。