关系型数据库是如何运作的（上）

一说到关系型数据库，我总感觉缺了点什么。如果你尝试透过“关系型数据库是如何运作的”的关键词句来进行搜索，其搜索结果是少量的而且内容是简短的。难道说是由于它已经太老旧而已经不再流行吗？

作为一名开发者，我讨厌使用我不明白的技术。此外，关系型数据库已经使用超40年，肯定有它过人的原因。因此，我花了大量时间来想真正弄懂它里面如同黑盒子那样的奥秘。关系型数据库实际上是非常有趣的，因为它是基于实用和复用的概念。但是限于篇幅，以下我将把重点放在数据库如何处理SQL查询的问题上。本文内容大致划分为以下三部分：

1.低阶数据库和高级数据库组成概述

2.查询优化流程的处理概述

3.事务和缓冲池管理概述

基本概念回顾

在编程年代早期，开发者是必须要理解清楚自己所进行操作的原理的。他们对于所使用的算法和数据结果是了然于胸的，因为他们很注重在计算机配置较低时于CPU和内存上的开销。在这一节，我首先要介绍的是数据库索引。

O(1) vs O(n2)

时间复杂度用于计算算法处理数据的用时。科学家使用大O表示法来进行时间复杂度描述，其定义是对于输入的数据算法需要进行多少步运算。这里要强调的是，它的核心是数据量增加对运算增加的影响而不是数据量的多少。时间复杂度不会直接给出精确的运算步数，而是以趋势的方式展示。

在上图中，你可以看到不同复杂度的发展趋势，我使用的方法是对数法。换言之，数据量将会从1快速地增加到10亿。我们可以得出以下结论：

• O(1)或常数复杂度是维持不变的
• O(log(n))在处理10亿数据量时也维持与一个较低复杂度水平
• O(n2)复杂度增长最快
• 其余两种复杂度位于中游

举例说明

如果是处理少量数据，O(1)和O(n2)的差别是不明显的。例如是2000个运算元素：

• O(1) 的运算量是1
• O(log(n)) 的运算量是7
• O(n) 的运算量是2000
• O(n*log(n)) 的运算量是14000
• O(n2) 的运算量是4 000 000

尽管O(1) 和 O(n2)的运算量的差距是4百万，但是这仅需2ms，也就是眨眼的功夫。此外，如果使用的是多核处理器，其运算速度会更快。所以性能和优化问题在现在的重视程度无法跟以往相比。

如果处理的数据量是1 000 000，其结果又会如何呢？

• O(1) 的运算量是1
• O(log(n)) 的运算量是14
• O(n) 的运算量是1 000 000
• O(n*log(n)) 的运算量是14 000 000
• O(n2) 的运算量是1 000 000 000 000

这样一来，你可以先喝杯咖啡休息下再回来看结果了！如果再加个0，你可以先进行午休了！

进一步说明

这里有几点提示：

在一个完整hash表中进行一次搜索会提交一个元素给O(1)

在一个全平衡树种进行一次搜索会提交一个结果给O(log(n))

在一个数组中进行一次搜索会提交一个结果给O(n)

最优排序算法的时间复杂度与O(n*log(n))相当

低效排序算法的时间复杂度与 O(n2)相当

注意：具体算法和数据结果会在本文稍后列示

时间复杂度的类型有：

• 平均事件场合
• 最佳时间场合
• 最差时间场合

时间复杂度通常是最差时间场合。除了时间复杂度，复杂度还可以用来表示内存使用和磁碟I/O占用情况等。诚然，比n2更复杂的计算有n4，3n，nn 。

合并排序

如果你要对一个集合进行排序该如何做呢？什么？使用sort()？听起来是个好的答案。

但如果排序对象是一个数据库，你就务必知道sort()的工作原理。这里我介绍排序算法中最重要的一种：合并排序。对合并排序理解透彻，一方面可以掌握如何进行查询优化，二来可以更好地理解本文稍后说到的合并join运算。

合并（Merge）

合并排序的运算过程是：合并两个已排序的N/2数组到一个已排序N个元素数组，例如下图所示：

以上是本系列文的上篇，更多内容请关注后续文章，后续内容简述：全局概念，客户管理器，查询管理器，数据管理器。

原文地址：http://coding-geek.com/how-databases-work/（译者/伍昆 责编/夏梦竹）