# 回归基础 很久很久以前（在遥远的银河系……），开发者必须知道他们代码的操作的准确数量。通过聆听算法和数据结构可以知道这个数目，因为他们不能浪费那慢得离谱的计算机的 CPU 和内存。 在本节，我会提醒你一些概念。这些概念对于理解数据库非常重要。我还会引入一个术语：**数据库索引（database index）**。 ## O(1) vs O($$n^{2}$$) 现在，很多开发者根本不关心时间复杂度。在一定程度上说，他们是正确的。 但是，当你处理大量数据（我说的不止几千）或者你必须要提高几毫秒时，就不得不理解这个概念了。猜猜怎么着？这两个情形都是数据库必须考虑的！我不会骚扰你很长时间，只要给我点时间来解释这个概念。这将有助于我们将来理解基于成本的优化（cost based optimization）这个概念。 ## 概念 **时间复杂度用来度量一个算法处理给定数量的数据的执行时间。**为了描述时间复杂度，计算机科学家设计了大 O 标记。大 O 标记使用一个函数描述一个算法对于给定数量的输入数据需要多少操作*（译注：这里所说的“操作”是一个抽象概念，可以理解为度量复杂度的一个单位）*。 例如，当我说“这个算法是 O( some_function() )”时，我的意思是，对于确定数量的数据，这个算法需要 some_function(给定数量的数据) 操作来完成其工作。 **重要的不是数据的数量，而是当数据的数量增加时，操作的数量是如何增加的。**时间复杂度并没有给出操作的具体数量，但不失为一个好的办法。 [](http://files.devbean.net/images/2016/03/TimeComplexity.png) 在上面图表中，你可以看到多种类型的复杂度。我使用了对数刻度去标记它们。换句话说，当数据量非常快地从一增加到十亿，我们可以发现： * 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)) 算法需要 14000 个操作 * O($$n^{2}$$) 算法需要 4 000 000 个操作 O(1) 和 O($$n^{2}$$) 的差别看起来很大（四百万）但实际上你只会损失 2 毫秒，也就是你眨巴眨巴眼镜的时间。事实上，现在的处理器[每秒能够处理几千万操作](https://en.wikipedia.org/wiki/Instructions_per_second)。这也就是为什么在很多 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 记号的准确定义，只给出了一个思想。你可以在[维基百科](https://en.wikipedia.org/wiki/Big_O_notation)阅读真正的定义。 ## 合并排序 如果你要对一个集合进行排序，你要怎么做？什么？你可以调用`sort()`函数……好主意……但是，对于数据库，你必须知道`sort()`函数是怎么工作的。 有很多很好的排序算法，我们会将精力放在最重要的那个上面：**合并排序**。现在你可能并不明白为什么对数据进行排序很有用，但是，当你读完查询优化部分后，你就应该能够回答这个问题。另外，了解合并排序可以帮助我们弄清楚一个通用数据库合并操作：**合并连接（merge join）**。 ### 合并 和很多有用的算法一样，合并排序也是基于一个小技巧：将两个已经排好序的长度为 N/2 的数组合并为一个排好序的长度为 N 的数组只需要 N 个操作。这个操作成为**合并**。 我们用一个简单的例子来看这是什么意思： [](http://files.devbean.net/images/2016/03/merge_sort.png) 上图最终获得一个排好序的具有 8 个元素的数组，你只需要遍历两个 4 元素的数组一次。由于两个 4 元素的数组都已经排好序了： * 1) 比较两个数组的当前元素（第一次比较时，当前元素就是第一个元素） * 2) 取出二者之间较小的放入 8 元素数组 * 3) 取出上一步较小元素所在的那个数组的下一个元素 * 重复上述三步，直到取出其中一个数组的最后一个元素 * 将另外一个数组的剩余元素全部追加到 8 元素数组中 由于 4 元素数组已经排好序，因此上述步骤可以正常工作。你不需要在这些数组中“后退”。 现在我们已经知道了思路，下面是合并排序的伪代码： ~~~ array mergeSort(array a) if(length(a)==1) return a[0]; end if // 递归调用 [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); // 将两个已经排好序的较短的数组合并到一个较长的数组中 array result := merge(new_left_array,new_right_array); return result; ~~~ 合并排序将一个较大的问题分解成多个较小的问题，找到较小问题的解，从而获得原始问题的解（注意：这种类型的算法被称为“分治法”）。如果你不明白这个算法，不要担心，我第一次看到它也不明白。为了帮助理解，我将这个算法看作一个具有两个步骤的算法： * 将数组分成较短的数组的分割阶段 * 将较短数组放在一次（使用合并）形成较长数组的排序阶段 ### 分割阶段 [](http://files.devbean.net/images/2016/03/merge_sort_1.png) 在分割阶段，使用 3 步，将原始数组分成只有一个元素的单元数组。这一步骤的计算公式是 log(N)（本例中，N=8，log(N) = 3）。 我是怎么知道这个的？ ~~我是个天才！~~简而言之：数学。这一阶段的思路是，每一步将原数组的长度分成二分之一。所需要的步数就是你能够将原始数组一分为二几次。这正式对数的定义（以 2 为底）。 ### 排序阶段 [](http://files.devbean.net/images/2016/03/merge_sort_2.png) 在排序阶段，你从单元数组开始。每一步都要应用多次合并，总的合并是 N=8 次： * 第一步，你需要 4 次合并，每一次合并需要 2 个操作 * 第二步，你需要 2 次合并，每一次合并需要 4 个操作 * 第三步，你需要 1 次合并，需要 8 个操作 因为一共有 log(N) 步，所以，**总的操作就是 N * log(N) 次**。 ### 合并排序的威力 为什么这个算法这么有用？ 原因是： * 你可以修改该算法，从而减少内存消耗。所需方法是，不要重新创建新的数组，而是直接修改输入的数组。注意：这种算法被称为[原地算法（in-place）](https://en.wikipedia.org/wiki/In-place_algorithm)。 * 你可以修改该算法，使用磁盘空间和少量内存，但是又不需要大量的磁盘 I/O 消耗。其思路是，只在内存中加载当前正在处理的部分。当你需要对几个 G 的数据表进行排序，但内存缓存只有 100M 的时候，这是一种很重要的方法。注意：这种算法被称为[外部排序（external sorting）](https://en.wikipedia.org/wiki/External_sorting)。 * 你可以修改该算法，以便在多个处理器/线程/服务器中运行。例如，分布式合并排序是 [Hadoop](https://hadoop.apache.org/docs/stable/api/org/apache/hadoop/mapreduce/Reducer.html)的核心组件之一（Hadoop 是处理大数据的重要框架之一）。 * 这个算法可以变成真金白银（真事儿！）。 这种排序算法被绝大多数（即便不能说全部）数据库采用，但它也并不是唯一的排序算法。如果你想知道得更多，你可以阅读这篇[研究论文](http://wwwlgis.informatik.uni-kl.de/archiv/wwwdvs.informatik.uni-kl.de/courses/DBSREAL/SS2005/Vorlesungsunterlagen/Implementing_Sorting.pdf)。该论文讨论了数据库中使用的各种通用排序算法的优缺点。 ## 数组，树和哈希表 现在我们已经明白了时间复杂度和排序的思想，接下来我要告诉你三个数据结构。这些数据结构都很重要，因为**它们是现代数据库的骨架**。我也会引入**数据库索引**这一概念。 ### 数组 二维数组是最简单的数据结构。表格可以被当成是一个数组。例如： [](http://files.devbean.net/images/2016/03/array.png) 这个二维数组就是带有行和列的表格： * 每一行表示一个对象 * 每一列描述对象的特征 * 每一列存储一种特定的数据类型（整型，字符串，日期等） 虽然这种数据结构非常适合与保存和数据可视化，但是当你需要查找一个特定值时，这种结构就玩不转了。 例如，**如果你想找到所有在英国工作的人**，你需要遍历每一行，去看看这一行是不是属于英国。**这需要消耗 N 个操作**（N 是行数），这看起来还不算很坏，但是有更快的吗？这就是引入树的目的。 注意，大多数现代数据库提供了改进数组，用于有效存储表，例如堆组织表（heap-organized tables）和索引组织表（index-organized tables）。但是，这些并不能改变快速检索符合特定条件的列组的问题。 ### 树和数据库索引 二叉搜索树是带有特殊属性的二叉树，其每个节点的键必须满足： * 大于所有左侧子树的键 * 小于所有右侧子树的键 下面我们来看看这是什么意思。 #### 思想 [](http://files.devbean.net/images/2016/03/BST.png) 这棵树有 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 个操作。这个你想象中的东西就是**数据库索引（database index）。** 你可以为列的任意组合构造树索引（字符串、整型、2 个字符串、一个整型和一个字符串、日期等等），只要你能够有一个可以比较键值（也就是这些列的组合）的函数。该函数可以用来计算**这些键值的顺序**（数据库中的基本类型就是这种情况）。 #### B+ 树索引 虽然二叉搜索树适合于查找特定值，但是当你需要**获取两个值之间的多个元素**时，会有一个很大的问题。因为你必须检查树中的所有节点，看它是不是落在两个值之间（例如，使用树的中序遍历），二叉搜索树的消耗会达到 O(N)。更要命的是，由于你必须读取整棵树，因此这一操作不是磁盘 I/O 友好的。我们需要找到一个执行**范围查询**的有效方法。为解决这一问题，现代数据库使用了一种改进了的二叉搜索树，被称为 B+ 树。在 B+ 树中： * 只有最低的节点（叶子节点）**保存信息**（相关表中的行的位置） * 其它节点仅仅用来**在检索中路由**到正确的节点。 [](http://files.devbean.net/images/2016/03/database_index1.png) 正如上图所示，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+ 树的文章](https://en.wikipedia.org/wiki/B%2B_tree)。如果你想要一个数据库中 B+ 树实现的例子，可以阅读 MySQL 的一位核心开发者的[这篇文章](http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/)和[这篇文章](http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/)。这两篇文章都关注于 innoDB（MySQL 的引擎之一）的索引处理。 注意：有位读者曾告诉我，考虑到数据库需要进行低层优化，B+ 树必须是完全平衡的。 ### 哈希表 我们最后一个重要的数据结构是哈希表。当你需要快速查找值是，哈希表是非常有帮助的。另外，了解哈希表可以帮助我们理解一个通用的数据库连接操作，被称为**哈希连接（hash join）**。这种数据结构还被用于存储一些内部信息（比如**锁表**或**缓冲池**，我们会在后面见到这些概念）。 哈希表是一种使用键快速查找元素的数据结构。构建哈希表需要定义： * 元素的**键**。 * 键的**哈希函数**。键通过哈希函数计算出来的哈希值给出了元素位置（称为**桶**）。 * **用于比较键的函数**。一旦找到正确的桶，你需要使用这个比较函数在这个桶中找到你要查找的元素。 #### 一个简单的例子 我们看一个可视化的例子： [](http://files.devbean.net/images/2016/03/hash_table.png) 这个哈希表有十个桶。因为我很懒，所以我只画出来其中的五个，但是我肯定你能够想像得到另外五个桶。我选择的哈希函数是键值模 10。换句话说，我只用了每个元素的键的最后一位数字去寻找它所在的桶： * 如果最后一位数字是 0，那么它就会在桶 0 * 如果最后一位数字是 1，那么它就会在桶 1 * 如果最后一位数字是 2，那么它就会在桶 2 * … 我使用的比较函数就是两个整型之间的比较。 假如你需要找到元素 78： * 哈希表计算出 78 的哈希值是 8； * 哈希表在桶 8 中寻找，发现它的第一个元素就是 78； * 哈希表返回元素 78。 * **这个检索只有 2 个操作**（第一个操作是计算哈希值，第二个操作是在桶中寻找元素）。 现在，加入要找到元素 59： * 哈希表计算出 59 的哈希值是 9； * 哈希表在桶 9 中寻找，找到的第一个元素是 99。由于 99 != 59，因此 99 不是所需要的元素； * 使用相同的逻辑，哈希表继续查看第二个元素（9），第三个元素（79），直到最后一个元素（29）； * 元素不存在。 * **这个检索需要 7 个操作。** #### 好的哈希函数 从上面的示例可以发现，检索所需要的操作数取决于你所要检索的值。 如果我将哈希函数改成键值模 1000000（也就是取最后 6 个数字），上面所说的第二个检索只会消耗 1 个操作，因为桶 000059 中没有元素。由此可见，**真正的挑战是找到一个好的哈希函数，让每个桶中的元素总数保持在一个很小的值。** 在我的例子中，很容易找到一个好的哈希函数。但这只是一个很简单的例子，当键属于下面的情况时，找到一个好的哈希函数就会复杂得多了： * 字符串（例如，一个人的姓） * 两个字符串（例如，一个人的姓和名） * 两个字符串和一个日期（例如，一个人的姓、名和这个人的出生日期） * … **结合一个好的哈希函数。哈希表检索的时间复杂度可以达到 ****O(1)。** #### 数组 vs 哈希表 为什么不使用数组？ 这是个好问题。 * 哈希表可以**在内存中只加载一半**，其余的桶依然保存在磁盘。 * 使用数组，你必须使用连续的内存空间。如果你需要加载一个很大的表，是**很难申请到连续内存空间的**。 * 使用哈希表，你可以**选择你想要使用的键**（例如，一个人的国籍和姓）。 更多的信息，你可以阅读 [Java HashMap](http://coding-geek.com/how-does-a-hashmap-work-in-java/)，这篇文章介绍了高性能哈希表的实现。即便不懂 Java，你也能够理解这篇文章中的概念。