说到关系数据库，我不禁觉得少了点什么。它们在任何地方都被使用。有许多不同的数据库:从小而有用的SQLite到强大的Teradata。但是，只有几篇文章解释了数据库是如何工作的。你可以自己谷歌一下“关系数据库是如何工作的”，看看结果有多少。而且，那些文章都很短。现在，如果你寻找最近流行的技术(大数据、NoSQL或JavaScript)，你会发现更多解释它们如何工作的深入文章。

关系数据库是否太老太枯燥，无法在大学课程、研究论文和书籍之外进行解释？

作为一个开发者，我讨厌用我不懂的东西。而且，如果数据库已经用了40年，一定有原因。这些年来，我花了几百个小时才真正理解这些我每天都在用的怪异黑匣子。关系数据库 是非常有趣，因为它们基于有用和可重用的概念。如果您对理解数据库感兴趣，但是您从来没有时间或意愿去钻研这个广泛的主题，那么您应该喜欢这篇文章。

虽然这篇文章的标题很明确，本文的目的不是理解如何使用数据库。因此，您应该已经知道如何编写简单的连接查询和基本的CRUD查询；否则你可能看不懂这篇文章。这是你唯一需要知道的，其他的我会解释的。

我将从一些计算机科学的东西开始，比如时间复杂性。我知道你们中的一些人讨厌这个概念，但是，没有它，你就无法理解数据库内部的巧妙之处。因为这是一个巨大的话题，我将重点介绍我认为最重要的是:数据库处理SQL查询的方式。我只会呈现数据库背后的基本概念所以在这篇文章的结尾，你会对幕后发生的事情有一个很好的了解。

由于这是一篇很长的技术性文章，涉及许多算法和数据结构，所以请慢慢阅读。有些概念更难理解；你可以跳过它们，仍然可以得到整体的想法。

对于更有见识的人来说，本文或多或少分为三个部分:

• 低级和高级数据库组件概述
• 查询优化过程概述
• 事务和缓冲池管理概述

回归基础

很久以前(在一个遥远的星系里…)，开发人员必须知道他们正在编码的操作的确切数量。他们对自己的算法和数据结构了如指掌，因为他们不能浪费速度缓慢的计算机的CPU和内存。

在这一部分，我将提醒您一些概念，因为它们对于理解数据库是必不可少的。我还会介绍数据库索引.

O(1)对O(n²)

现在，许多开发人员不关心时间复杂性…他们是对的！

但是当你处理大量数据(我不是在说成千上万)或者你在争分夺秒的时候，理解这个概念就变得至关重要了。你猜怎么着，数据库必须处理这两种情况！我不会让你厌烦很长时间，只是时间来得到这个想法。这将有助于我们以后理解的概念基于成本的优化.

这个概念

这时间复杂度用于查看一个算法对于给定的数据量需要多长时间。为了描述这种复杂性，计算机科学家使用数学上的大O符号。这种表示法用于描述给定输入数据量的算法需要多少运算的函数。

比如我说“这个算法在O( some_function())”就是说对于一定量的数据，算法需要some _ function(a _ certain _ amount _ of _ data)运算来完成它的工作。

重要的是不是数据量，而是当数据量增加时，操作数量增加的方式。时间复杂度没有给出确切的操作数，但给出了一个好主意。

在这个图中，你可以看到不同类型的复杂性的演变。我用对数标度来绘制它。换句话说，数据的数量正在从1迅速增加到10亿。我们可以看到:

• 这

  O(1)

  或者恒定复杂度保持不变(否则就不叫恒定复杂度)。
• 这

  O(log(n))即使有数十亿数据也保持低位.

• 最糟糕的复杂性是

  O(n²)手术数量迅速增加.

• 两个

  扭转操作her公司mp务实贸易(Labor Exchange)?低爆速炸药(Low Explosive)?职业介绍所(Labour Exchange)xiti

  es正在迅速增加。

例子

在数据量很少的情况下，O(1)和O(n²)可以忽略不计。例如，假设您有一个需要处理2000个元素的算法。

• 一个O(1)算法将花费你1次运算
• 一个O(log(n))算法将花费你7次运算
• 一个O(n)算法将花费你2 000次运算
• 一个O(n*log(n))算法需要14 000次运算
• 一个O(n

  ²

  )算法将花费你4 00万次运算

O(1)和O(n)的区别²)看起来很多(400万)但是你最多会损失2 ms，只是眨眼的时间。事实上，目前的处理器可以处理每秒数亿次运算。这就是为什么性能和优化在许多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

  ²

  )算法将花费你1 000 000 000 000次运算

我没有算过，但我会用O(n)表示²)算法你有时间喝一杯咖啡(哪怕是第二杯！).如果你在数据量上再加一个0，你就有时间小睡一会儿了。

更深入

给你一个想法:

• 在好的散列表中的搜索给出O(1)中的元素
• 在平衡良好的树中搜索的结果为O(log(n))
• 在数组中搜索的结果是O(n)
• 最佳排序算法的复杂度为O(n*log(n))。
• 一个坏的排序算法有一个O(n

  ²

  )复杂性

注意:在接下来的部分中，我们将看到这些算法和数据结构。

时间复杂性有多种类型:

• 一般情况下
• 最好的情况是
• 最坏的情况是

时间复杂度通常是最坏的情况。

我只谈了时间复杂性，但复杂性也适用于:

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

当然还有比n更复杂的情况²，比如:

• n⁴

  :太烂了！我将要提到的一些算法具有这种复杂性。

• 3ⁿ

  那就更糟了！我们将在本文中间看到的算法之一具有这种复杂性(并且它确实在许多数据库中使用)。
• 阶乘n:你永远不会得到你的结果，即使数据量很少。

• nⁿ

  :如果你以这种复杂性告终，你应该问问自己，这真的是你的领域吗…

注意:我没有给出大O符号的真正定义，只是给出了它的概念。您可以在上阅读这篇文章维基百科(一个基于wiki技术的多语言的百科全书协作计划?也是一部用不同语言写成的网络百科全书? 其目标及宗旨是为全人类提供自由的百科全书)?开放性的百科全书对于实(渐近)定义。

合并排序

当你需要对一个收藏进行排序时，你会怎么做？什么？你调用sort()函数…好，回答得好…但是对于一个数据库，你必须理解这个sort()函数是如何工作的。

有几种很好的排序算法，所以我将重点介绍最重要的一种:合并排序。您现在可能不理解为什么排序数据是有用的，但是在学习完查询优化的部分之后，您应该会明白了。此外，理解合并排序将有助于我们稍后理解一种常见的数据库连接操作，称为合并联接.

合并

像许多有用的算法一样，合并排序基于一个技巧:将两个大小为N/2的排序数组合并成一个N元素排序数组只需要N次操作。这种操作称为合并.

让我们通过一个简单的例子来看看这意味着什么:

从图中可以看出，要构建最终的8元素排序数组，只需在2个4元素数组中迭代一次。因为两个4元素数组都已经排序:

• 1)比较两个数组中的两个当前元素(第一次current=first)
• 2)然后取最低的一个放入8元素数组
• 3)并转到数组中的下一个元素，您取了最低的元素
• 重复1、2、3，直到到达其中一个数组的最后一个元素。
• 然后，将另一个数组的其余元素放入8元素数组中。

这样做是因为两个4元素的数组都被排序了，因此你不需要在这些数组中“返回”。

现在我们已经理解了这个技巧，下面是我的合并排序的伪代码。

合并排序将问题分解成更小的问题，然后找到更小问题的结果，以获得初始问题的结果(注意:这种算法称为分治算法)。如果你不懂这个算法，不用担心；第一次看的时候没看懂。如果能帮到你，我把这个算法看做两阶段算法:

• 分割阶段，将数组分割成更小的数组
• 排序阶段，将小数组放在一起(使用合并)形成一个更大的数组。

分裂阶段

在划分阶段，使用3个步骤将阵列划分为单位阵列。正规的步数是log(N)(因为N=8，所以log(N) = 3)。

我怎么知道？

我是天才！一个字:数学。其思想是每一步都将初始数组的大小除以2。步数是你可以将初始数组除以2的次数。这是对数(以2为底)的确切定义。

分类阶段

在排序阶段，从酉数组开始。在每个步骤中，您应用多个合并，总成本是N=8次操作:

• 在第一步中，有4个合并，每个合并需要2次操作
• 在第二步中，您有两个合并，每个合并需要4次操作
• 在第三步中，您有1个合并，需要8次操作

因为有log(N)个步骤，N * log(N)次操作的总成本.

合并排序的威力

为什么这个算法这么厉害？

因为:

• 您可以修改它以减少内存占用，方法是不创建新的数组，而是直接修改输入数组。

注:这种算法称为原状.

• 您可以修改它，以便同时使用磁盘空间和少量内存，而不会有巨大的磁盘I/O损失。这个想法是在内存中只加载当前正在处理的部分。当您需要对一个只有100兆内存缓冲区的数千兆字节的表进行排序时，这一点非常重要。

注:这种算法称为外部排序.

• 您可以将其修改为在多个进程/线程/服务器上运行。

例如，分布式合并排序是Hadoop(也就是大数据中的框架)。

• 这个算法可以点石成金(千真万确！).

这种排序算法在大多数(如果不是全部)数据库中使用，但不是唯一的一种。如果你想知道更多，你可以看看这个研究论文讨论了数据库中常见排序算法的优缺点。

本文由本站原创或投稿者首发,转载请注明来源！

本文链接：http://www.ziti66.com/net/html/162.html