时间：2021-07-01 10:21:17 帮助过：23人阅读
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | 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，下文有说明】
我怎么知道这个的？
我是天才！一句话：数学。道理是每一步都把原序列的长度除以2，步骤数就是你能把原序列长度除以2的次数。这正好是对数的定义（在底数为2时）。
在排序阶段，你从一元序列开始。在每一个步骤中，你应用多次合并操作，成本一共是 N=8 次运算。
因为有 log(N) 个步骤，整体成本是 N*log(N) 次运算。
【译者注：这个完整的动图演示了拆分和排序的全过程，不动戳大。】
为什么这个算法如此强大？
因为：
注：这种算法叫『原地算法』(in-place algorithm)
注：这种算法叫『外部排序』(external sorting)。
比如，分布式合并排序是Hadoop（那个著名的大数据框架）的关键组件之一。
这个排序算法在大多数（如果不是全部的话）数据库中使用，但是它并不是唯一算法。如果你想多了解一些，你可以看看 这篇论文，探讨的是数据库中常用排序算法的优势和劣势。
既然我们已经了解了时间复杂度和排序背后的理念，我必须要向你介绍3种数据结构了。这个很重要，因为它们是现代数据库的支柱。我还会介绍数据库索引的概念。
二维阵列是最简单的数据结构。一个表可以看作是个阵列，比如：
这个二维阵列是带有行与列的表：
虽然用这个方法保存和视觉化数据很棒，但是当你要查找特定的值它就很糟糕了。 举个例子，如果你要找到所有在 UK 工作的人，你必须查看每一行以判断该行是否属于 UK 。这会造成 N 次运算的成本（N 等于行数），还不赖嘛，但是有没有更快的方法呢？这时候树就可以登场了（或开始起作用了）。
二叉查找树是带有特殊属性的二叉树，每个节点的关键字必须：
【译者注：binary search tree，二叉查找树/二叉搜索树，或称 Binary Sort Tree 二叉排序树。见百度百科 】
这个树有 N=15 个元素。比方说我要找208：
现在比方说我要找40
最后，两次查询的成本就是树内部的层数。如果你仔细阅读了合并排序的部分，你就应该明白一共有 log(N)层。所以这个查询的成本是 log(N)，不错啊！
上文说的很抽象，我们回来看看我们的问题。这次不用傻傻的数字了，想象一下前表中代表某人的国家的字符串。假设你有个树包含表中的列『country』：
这次搜索只需 log(N) 次运算，而如果你直接使用阵列则需要 N 次运算。你刚刚想象的就是一个数据库索引。
查找一个特定值这个树挺好用，但是当你需要查找两个值之间的多个元素时，就会有大麻烦了。你的成本将是 O(N)，因为你必须查找树的每一个节点，以判断它是否处于那 2 个值之间（例如，对树使用中序遍历）。而且这个操作不是磁盘I/O有利的，因为你必须读取整个树。我们需要找到高效的范围查询方法。为了解决这个问题，现代数据库使用了一种修订版的树，叫做B+树。在一个B+树里：
【译者注：参考 B+树 ， 二叉树遍历 维基百科】
你可以看到，节点更多了（多了两倍）。确实，你有了额外的节点，它们就是帮助你找到正确节点的『决策节点』（正确节点保存着相关表中行的位置）。但是搜索复杂度还是在 O(log(N))（只多了一层）。一个重要的不同点是，最底层的节点是跟后续节点相连接的。
用这个 B+树，假设你要找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(log(N)) 运算来更新表的索引。再者，增加索引意味着给事务管理器带来更多的工作负荷（在本文结尾我们会探讨这个管理器）。
想了解更多细节，你可以看看 Wikipedia 上这篇关于B+树的文章。如果你想要数据库中实现B+树的例子，看看MySQL核心开发人员写的这篇文章 和 这篇文章。两篇文章都致力于探讨 innoDB(MySQL引擎)如何处理索引。
我们最后一个重要的数据结构是哈希表。当你想快速查找值时，哈希表是非常有用的。而且，理解哈希表会帮助我们接下来理解一个数据库常见的联接操作，叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西（比如锁表或者缓冲池，我们在下文会研究这两个概念）。
哈希表这种数据结构可以用关键字来快速找到一个元素。为了构建一个哈希表，你需要定义：
我们来看一个形象化的例子：
这个哈希表有10个哈希桶。因为我懒，我只给出5个桶，但是我知道你很聪明，所以我让你想象其它的5个桶。我用的哈希函数是关键字对10取模，也就是我只保留元素关键字的最后一位，用来查找它的哈希桶：
【译者注：取模运算】
比方说你要找元素 78：
现在，比方说你要找元素 59：
你可以看到，根据你查找的值，成本并不相同。
如果我把哈希函数改为关键字对 1,000,000 取模（就是说取后6位数字），第二次搜索只消耗一次运算，因为哈希桶 00059 里面没有元素。真正的挑战是找到好的哈希函数，让哈希桶里包含非常少的元素。
在我的例子里，找到一个好的哈希函数很容易，但这是个简单的例子。当关键字是下列形式时，好的哈希函数就更难找了：
如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。
为什么不用阵列呢？
嗯，你问得好。
想要更详细的信息，你可以阅读我在Java HashMap 上的文章，是关于高效哈希表实现的。你不需要了解Java就能理解文章里的概念。
我们已经了解了数据库内部的基本组件，现在我们需要回来看看数据库的全貌了。
数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果。事实上，像SQLite这样最简单的数据库也只是一堆文件而已，但SQLite是精心设计的一堆文件，因为它允许你：
数据库一般可以用如下图形来理解：
撰写这部分之前，我读过很多书/论文，它们都以自己的方式描述数据库。所以，我不会特别关注如何组织数据库或者如何命名各种进程，因为我选择了自己的方式来描述这些概念以适应本文。区别就是不同的组件，总体思路为：数据库是由多种互相交互的组件构成的。
核心组件：
工具：
查询管理器：
数据管理器：
在本文剩余部分，我会集中探讨数据库如何通过如下进程管理SQL查询的：
客户端管理器是处理客户端通信的。客户端可以是一个（网站）服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式来访问数据库。
客户端管理器也提供专有的数据库访问API。
当你连接到数据库时：
这部分是数据库的威力所在，在这部分里，一个写得糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器。这个多步骤操作过程如下：
这里我不会过多探讨最后两步，因为它们不太重要。
看完这部分后，如果你需要更深入的知识，我建议你阅读：
每一条SQL语句都要送到解析器来检查语法，如果你的查询有错，解析器将拒绝该查询。比如，如果你写成”SLECT …” 而不是 “SELECT …”，那就没有下文了。
但这还不算完，解析器还会检查关键字是否使用正确的顺序，比如 WHERE 写在 SELECT 之前会被拒绝。
然后，解析器要分析查询中的表和字段，使用数据库元数据来检查：
接着，解析器检查在查询中你是否有权限来读取（或写入）表。再强调一次：这些权限由DBA分配。
在解析过程中，SQL 查询被转换为内部表示（通常是一个树）。
如果一切正常，内部表示被送到查询重写器。
在这一步，我们已经有了查询的内部表示，重写器的目标是：
重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：
例如：
MySQL| 1 2 3 4 5 6 | SELECT PERSON.* FROM PERSON WHERE PERSON.person_key IN (SELECT MAILS.person_key FROM MAILS WHERE MAILS.mail LIKE ‘christophe%‘); |
会转换为：
MySQL| 1 2 3 4 | SELECT PERSON.* FROM PERSON, MAILS WHERE PERSON.person_key = MAILS.person_key and MAILS.mail LIKE ‘christophe%‘; |
【译者注： 物化视图 。谓词，predicate，条件表达式的求值返回真或假的过程】
重写后的查询接着送到优化器，这时候好玩的就开始了。
研究数据库如何优化查询之前我们需要谈谈统计，因为没有统计的数据库是愚蠢的。除非你明确指示，数据库是不会分析自己的数据的。没有分析会导致数据库做出（非常）糟糕的假设。
但是，数据库需要什么类型的信息呢？
我必须（简要地）谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块（默认 4 或 8 KB）。这就是说如果你仅需要 1KB，也会占用一个页。要是页的大小为 8KB，你就浪费了 7KB。
回来继续讲统计！ 当你要求数据库收集统计信息，数据库会计算下列值：
这些统计信息会帮助优化器估计查询所需的磁盘 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 个字符就够了，这将大大减少比较的次数。
不过，这些只是基本的统计。你可以让数据库做一种高级统计，叫直方图。直方图是列值分布情况的统计信息。例如：
这些额外的统计会帮助数据库找到更佳的查询计划，尤其是对于等式谓词（例如： WHERE AGE = 18 ）或范围谓词（例如： WHERE AGE > 10 and AGE < 40），因为数据库可以更好的了解这些谓词相关的数字类型数据行（注：这个概念的技术名称叫选择率）。
统计信息保存在数据库元数据内，例如（非分区）表的统计信息位置：
统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行，没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算，这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级时统计会变得困难，这时候，你可以选择仅做基本统计或者在一个数据库样本上执行统计。
举个例子，我参与的一个项目需要处理每表上亿条数据的库，我选择只统计10%，结果造成了巨大的时间消耗。本例证明这是个糟糕的决定，因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 跟全部 100% 有很大不同（对于拥有一亿行数据的表，这种情况极少发生）。这次错误的统计导致了一个本应 30 秒完成的查询最后执行了 8 个小时，查找这个现象根源的过程简直是个噩梦。这个例子显示了统计的重要性。
注：当然了，每个数据库还有其特定的更高级的统计。如果你想了解更多信息，读读数据库的文档。话虽然这么说，我已经尽力理解统计是如何使用的了，而且我找到的最好的官方文档来自PostgreSQL。
所有的现代数据库都在用基于成本的优化（即CBO）来优化查询。道理是针对每个运算设置一个成本，通过应用成本最低廉的一系列运算，来找到最佳的降低查询成本的方法。
为了理解成本优化器的原理，我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法，我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后，我们会了解真正的优化器是怎么做的。
对于这些联接操作，我会专注于它们的时间复杂度，但是，数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的区别是，时间成本是个近似值（给我这样的懒家伙准备的）。而 CPU 成本，我这里包括了所有的运算，比如：加法、条件判断、乘法、迭代……还有呢：
使用时间复杂度就容易多了（至少对我来说），用它我也能了解到 CBO 的概念。由于磁盘 I/O 是个重要的概念，我偶尔也会提到它。请牢记，大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用。
在研究 B+树的时候我们谈到了索引，要记住一点，索引都是已经排了序的。
仅供参考：还有其他类型的索引，比如位图索引，在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同。
另外，很多现代数据库为了改善执行计划的成本，可以仅为当前查询动态地生成临时索引。
注：由于所有存取路径的真正问题是磁盘 I/O，我不会过多探讨时间复杂度。
【译者注：四种类型的Oracle索引扫描介绍 】
如果你读过执行计划，一定看到过『全扫描』（或只是『扫描』）一词。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂。
其他类型的扫描有索引范围扫描，比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。
当然，你需要在 AGE 字段上有索引才能用到索引范围扫描。
在第一部分我们已经知道，范围查询的时间成本大约是 log(N)+M，这里 N 是索引的数据量，M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值（注： M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率）。另外范围扫描时，你不需要读取整个索引，因此在磁盘 I/O 方面没有全扫描那么昂贵。
如果你只需要从索引中取一个值你可以用唯一扫描。
多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。
例如，假如你运行：
MySQL| 1 | SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28 |
如果 person 表的 age 列有索引，优化器会使用索引找到所有年龄为 28 的人，然后它会去表中读取相关的行，这是因为索引中只有 age 的信息而你要的是姓和名。
但是，假如你换个做法：
MySQL| 1 2 | SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE |
PERSON 表的索引会用来联接 TYPE_PERSON 表，但是 PERSON 表不会根据行ID 存取，因为你并没有要求这个表内的信息。
虽然这个方法在少量存取时表现很好，这个运算的真正问题其实是磁盘 I/O。假如需要大量的根据行ID存取，数据库也许会选择全扫描。
我没有列举所有的存取路径，如果你感兴趣可以读一读 Oracle文档。其它数据库里也许叫法不同但背后的概念是一样的。
那么，我们知道如何获取数据了，那现在就把它们联接起来！
我要展现的是3个个常用联接运算符：合并联接（Merge join），哈希联接（Hash Join）和嵌套循环联接（Nested Loop Join）。但是在此之前，我需要引入新词汇了：内关系和外关系（ inner relation and outer relation） 【译者注： “内关系和外关系” 这个说法来源不明，跟查询的“内联接（INNER JOIN） 、外联接（OUTER JOIN） ” 不是一个概念 。只查到百度百科词条：关系数据库 里提到“每个表格（有时被称为一个关系）……” 。 其他参考链接 “Merge Join” “Hash Join” “Nested Loop Join” 】 。 一个关系可以是：
当你联接两个关系时，联接算法对两个关系的处理是不同的。在本文剩余部分，我将假定：
比如， A JOIN B 是 A 和 B 的联接，这里 A 是外关系，B 是内关系。
多数情况下， A JOIN B 的成本跟 B JOIN A 的成本是不同的。
在这一部分，我还将假定外关系有 N 个元素，内关系有 M 个元素。要记住，真实的优化器通过统计知道 N 和 M 的值。
注：N 和 M 是关系的基数。【译者注： 基数 】
嵌套循环联接是最简单的。
道理如下：
下面是伪代码：
C| 1 2 3 4 5 6 7 8 | nested_loop_join(array outer, array inner) for each row a in outer for each row b in inner if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for |
由于这是个双迭代，时间复杂度是 O(N*M)。
在磁盘 I/O 方面， 针对 N 行外关系的每一行，内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N+ N*M 行。但是，如果内关系足够小，你可以把它读入内存，那么就只剩下 M + N 次读取。这样修改之后，内关系必须是最小的，因为它有更大机会装入内存。
在CPU成本方面没有什么区别，但是在磁盘 I/O 方面，最好最好的，是每个关系只读取一次。
当然，内关系可以由索引代替，对磁盘 I/O 更有利。
由于这个算法非常简单，下面这个版本在内关系太大无法装入内存时，对磁盘 I/O 更加有利。道理如下：
可能的算法如下：
C| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // improved version to reduce the disk I/O. nested_loop_join_v2(file outer, file inner) for each bunch ba in outer // ba is now in memory for each bunch bb in inner // bb is now in memory for each row a in ba for each row b in bb if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for end for end for |
使用这个版本，时间复杂度没有变化，但是磁盘访问降低了：
哈希联接更复杂，不过在很多场合比嵌套循环联接成本低。
哈希联接的道理是：
在时间复杂度方面我需要做些假设来简化问题：
时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。
如果哈希函数创建了足够小规模的哈希桶，那么复杂度就是 O(M+N)。
还有个哈希联接的版本，对内存有利但是对磁盘 I/O 不够有利。 这回是这样的：
合并联接是唯一产生排序的联接算法。
注：这个简化的合并联接不区分内表或外表；两个表扮演同样的角色。但是真实的实现方式是不同的，比如当处理重复值时。
1.（可选）排序联接运算：两个输入源都按照联接关键字排序。
2.合并联接运算：排序后的输入源合并到一起。
我们已经谈到过合并排序，在这里合并排序是个很好的算法（但是并非最好的，如果内存足够用的话，还是哈希联接更好）。
然而有时数据集已经排序了，比如：
这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢，我们不是从两个关系里挑选所有元素，而是只挑选相同的元素。道理如下：
因为两个关系都是已排序的，你不需要『回头去找』，所以这个方法是有效的。
该算法是个简化版，因为它没有处理两个序列中相同数据出现多次的情况（即多重匹配）。真实版本『仅仅』针对本例就更加复杂，所以我才选择简化版。
如果两个关系都已经排序，时间复杂度是 O(N+M)
如果两个关系需要排序，时间复杂度是对两个关系排序的成本：O(N*Log(N) + M*Log(M))
对于计算机极客，我给出下面这个可能的算法来处理多重匹配（注：对于这个算法我不保证100%正确）：
C| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | mergeJoin(relation a, relation b) relation output integer a_key:=0; integer b_key:=0; while (a[a_key]!=null and b[b_key]!=null) if (a[a_key] < b[b_key]) a_key++; else if (a[a_key] > b[b_key]) b_key++; else //Join predicate satisfied write_result_in_output(a[a_key],b[b_key]) //We need to be careful when we increase the pointers if (a[a_key+1] != b[b_key]) b_key++; end if if (b[b_key+1] != a[a_key]) a_key++; end if if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1]) b_key++; a_key++; end if end if end while |
如果有最好的，就没必要弄那么多种类型了。这个问题很难，因为很多因素都要考虑，比如：
想要更详细的信息，可以阅读DB2, ORACLE 或 SQL Server)的文档。
我们已经研究了 3 种类型的联接操作。
现在，比如说我们要联接 5 个表，来获得一个人的全部信息。一个人可以有：
换句话说，我们需要用下面的查询快速得<