嘿哈布尔！ 我向您展示这篇文章的翻译
“关系数据库是如何工作的”.

当谈到关系数据库时，我情不自禁地认为缺少了一些东西。 它们随处可见。 有许多不同的数据库可用，从小型实用的 SQLite 到功能强大的 Teradata。 但只有几篇文章解释了数据库的工作原理。 您可以使用“howdoesarelationaldatabasework”自行搜索，看看结果有多少。 而且，这些文章都很短。 如果您正在寻找最新的热门技术（BigData、NoSQL 或 JavaScript），您会找到更多深入的文章来解释它们的工作原理。

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

作为一名开发人员，我讨厌使用我不理解的东西。 如果数据库已经使用了 40 多年，那一定是有原因的。 多年来，我花了数百个小时来真正理解我每天使用的这些奇怪的黑匣子。 关系数据库 很有趣，因为他们 基于有用且可重用的概念。 如果您有兴趣了解数据库，但从未有时间或意愿深入研究这个广泛的主题，那么您应该喜欢这篇文章。

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

我将从一些计算机科学基础知识开始，例如算法的时间复杂度 (BigO)。 我知道你们中的一些人讨厌这个概念，但如果没有它，您将无法理解数据库内部的复杂性。 由于这是一个很大的话题， 我将重点关注 我认为重要的事情: 数据库如何处理 SQL 要求。 我简单介绍一下 基本数据库概念这样在文章的最后您就可以了解幕后发生的事情。

由于这是一篇很长的技术性文章，涉及大量算法和数据结构，请花点时间阅读它。 有些概念可能很难理解； 您可以跳过它们，但仍能了解总体思路。

为了方便大家了解更多，本文分为 3 部分：

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

回归本源

几年前（在一个遥远的星系......），开发人员必须准确地知道他们正在编码的操作数量。 他们对算法和数据结构了如指掌，因为他们不能浪费慢速计算机的 CPU 和内存。

在这一部分中，我将提醒您其中一些概念，因为它们对于理解数据库至关重要。 我也来介绍一下这个概念 数据库索引.

O(1) 与 O(n2)

如今，许多开发人员并不关心算法的时间复杂度……他们是对的！

但是，当您处理大量数据（我不是说数千个）或者如果您在毫秒内挣扎时，理解这个概念就变得至关重要。 正如您可以想象的那样，数据库必须处理这两种情况！ 我不会让你花更多的时间来理解要点。 这将有助于我们稍后理解基于成本的优化的概念（成本 基于 优化).

概念

算法的时间复杂度 用于查看对于给定数据量执行算法需要多长时间。 为了描述这种复杂性，我们使用大 O 数学符号。该符号与一个函数一起使用，该函数描述了算法对于给定数量的输入需要多少次操作。

例如，当我说“这个算法的复杂度为 O(some_function())”时，这意味着该算法需要 some_function(a_certain_amount_of_data) 操作来处理一定量的数据。

在这种情况下， 重要的不是数据量**， 否则 ** 操作数量如何随着数据量的增加而增加。 时间复杂度不提供确切的操作数量，但它是估计执行时间的好方法。

在此图中，您可以看到不同类型算法时间复杂度的操作数量与输入数据量的关系。 我使用对数刻度来显示它们。 也就是说，数据量从1快速增长到1亿，我们可以看到：

• O(1) 或常数复杂度保持不变（否则就不会称为常数复杂度）。
• O(日志(n)) 即使有数十亿数据仍然很低.
• 最难的是—— O(n2)，操作数量快速增长.
• 另外两种并发症也同样迅速增加。

Примеры

对于少量数据，O(1) 和 O(n2) 之间的差异可以忽略不计。 例如，假设您有一个需要处理 2000 个元素的算法。

• O(1) 算法将花费您 1 次操作
• O(log(n)) 算法将花费您 7 次操作
• O(n) 算法将花费您 2 次操作
• O(n*log(n)) 算法将花费您 14 次操作
• O(n2) 算法将花费您 4 次操作

O(1) 和 O(n2) 之间的差异似乎很大（4 万次操作），但您最多会损失 2 毫秒，只是眨眼的时间。 事实上，现代处理器可以处理 每秒数亿次操作。 这就是为什么性能和优化在许多 IT 项目中不是问题。

正如我所说，在处理大量数据时了解这个概念仍然很重要。 如果这次算法必须处理 1 个元素（这对于数据库来说并不算多）：

• O(1) 算法将花费您 1 次操作
• O(log(n)) 算法将花费您 14 次操作
• O(n) 算法将花费您 1 次操作
• O(n*log(n)) 算法将花费您 14 次操作
• O(n2) 算法将花费您 1 次操作

我没有做过数学计算，但我想说，使用 O(n2) 算法，你有时间喝咖啡（甚至两杯！）。 如果数据量再加0，你就有时间小睡了。

让我们更深入地了解一下

为了您的信息：

• 良好的哈希表查找在 O(1) 中找到一个元素。
• 搜索平衡良好的树会产生 O(log(n)) 的结果。
• 搜索数组会在 O(n) 内产生结果。
• 最好的排序算法的复杂度为 O(n*log(n))。
• 糟糕的排序算法的复杂度为 O(n2)。

注意：在下面的部分中我们将看到这些算法和数据结构。

算法时间复杂度有以下几种类型：

• 平均情况
• 最好的情况
• 和最坏的情况

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

我只是谈论算法的时间复杂度，但复杂度也适用于：

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

当然，还有比n2更糟糕的并发症，例如：

• n4：这太可怕了！ 提到的一些算法具有这种复杂性。
• 3n：这更糟糕！ 我们将在本文中间看到的算法之一具有这种复杂性（并且它实际上在许多数据库中使用）。
• 阶乘 n：即使数据量很小，您也永远无法得到结果。
• nn：如果你遇到这种复杂性，你应该问问自己这是否真的是你的活动领域......

注意：我没有给你大 O 名称的实际定义，只是一个想法。 您可以在以下位置阅读这篇文章 维基百科 为实数（渐近）定义。

归并排序

当你需要对集合进行排序时你会做什么？ 什么？ 你调用 sort() 函数...好吧，很好的答案...但是对于数据库，你必须了解这个 sort() 函数是如何工作的。

有几种很好的排序算法，所以我将重点关注最重要的： 归并排序。 您现在可能不明白为什么对数据进行排序很有用，但是在查询优化部分之后您应该明白。 此外，理解归并排序将有助于我们以后理解常见的数据库连接操作，称为 合并 加入 （合并协会）.

合并

与许多有用的算法一样，合并排序依赖于一个技巧：将 2 个大小为 N/2 的排序数组组合成一个 N 元素排序数组只需要 N 次操作。 这个操作称为合并。

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

该图显示，要构建最终排序的 8 元素数组，您只需对 2 个 4 元素数组迭代一次。 由于两个 4 元素数组都已排序：

• 1）比较两个数组中的两个当前元素（在开始时当前=第一个）
• 2）然后取最小的一个放入8元素数组中
• 3) 并移动到数组中取出最小元素的下一个元素
• 并重复 1,2,3、XNUMX、XNUMX，直到到达其中一个数组的最后一个元素。
• 然后，将另一个数组的剩余元素放入 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。步数就是可以将原始数组一分为二的次数。 这是对数（以 2 为底）的精确定义。

排序阶段

在排序阶段，您从单一（单元素）数组开始。 在每个步骤中，您应用多个合并操作，总成本为 N = 8 个操作：

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

由于有 log(N) 个步骤， 总成本N * 记录 (N) 次操作.

归并排序的优点

为什么这个算法如此强大？

这是因为：

• 您可以更改它以减少内存占用，这样您就不会创建新数组而是直接修改输入数组。

注意：这种算法称为 in - 地方 （无需额外内存即可排序）。

• 您可以将其更改为同时使用磁盘空间和少量内存，而不会产生大量磁盘 I/O 开销。 这个想法是仅将当前正在处理的那些部分加载到内存中。 当您需要对仅具有 100 MB 内存缓冲区的多 GB 表进行排序时，这一点非常重要。

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

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

例如，分布式归并排序是关键组件之一 Hadoop的 （这是大数据中的一种结构）。

• 这个算法可以把铅变成金（真的！）。

大多数（如果不是全部）数据库都使用这种排序算法，但它并不是唯一的一种。 如果你想了解更多，你可以阅读这篇文章 研究工作，讨论了常见数据库排序算法的优缺点。

数组、树和哈希表

现在我们了解了时间复杂度和排序的思想，我应该告诉你3种数据结构。 这很重要，因为他们 是现代数据库的基础。 我也来介绍一下这个概念 数据库索引.

排列

二维数组是最简单的数据结构。 可以将表视为数组。 例如：

这个二维数组是一个包含行和列的表：

• 每行代表一个实体
• 列存储描述实体的属性。
• 每列存储特定类型的数据（整数、字符串、日期...）。

这对于存储和可视化数据很方便，但是，当您需要查找特定值时，这并不合适。

例如，如果您想查找在英国工作的所有人员，则需要查看每一行以确定该行是否属于英国。 这将花费你N笔交易哪里 N - 行数，这还不错，但是有没有更快的方法？ 现在是我们熟悉树木的时候了。

注意：大多数现代数据库都提供扩展数组来有效地存储表：堆组织表和索引组织表。 但这并不能改变在一组列中快速查找特定条件的问题。

数据库树和索引

二叉搜索树是一种具有特殊性质的二叉树，每个节点的键必须是：

• 大于左子树中存储的所有键
• 小于右子树中存储的所有键

让我们看看这在视觉上意味着什么

想法

这棵树有 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, 节点存在。 我检索节点内的行 ID（图中未显示）并在表中查找给定的行 ID。
• 知道行 ID 可以让我准确地知道数据在表中的位置，这样我就可以立即检索它。

最后，这两次搜索都会花费我树内的层数。 如果您仔细阅读有关合并排序的部分，您应该会看到有 log(N) 个级别。 事实证明， 搜索成本日志(N)， 不错！

让我们回到我们的问题

但这非常抽象，所以让我们回到我们的问题。 想象一个代表上表中某人所在国家/地区的字符串，而不是简单的整数。 假设您有一棵树，其中包含表的“国家/地区”字段（第 3 列）：

• 如果您想知道谁在英国工作
• 你查看树来获取代表英国的节点
• 在“UKnode”内，您将找到英国工人记录的位置。

如果直接使用数组，此搜索将花费 log(N) 次操作，而不是 N 次操作。 你刚才介绍的是 数据库索引.

您可以为任何字段组（字符串、数字、2 行、数字和字符串、日期...）构建索引树，只要您有一个比较键（即字段组）的函数，以便您可以设置 键之间的顺序 （数据库中的任何基本类型都是这种情况）。

B+树索引

虽然这棵树可以很好地获取特定值，但当您需要时就会出现一个大问题 获取两个值之间的多个元素。 这将花费 O(N)，因为您必须查看树中的每个节点并检查它是否在这两个值之间（例如，对树进行有序遍历）。 此外，此操作对磁盘 I/O 不友好，因为您必须读取整个树。 我们需要找到一种高效执行的方法 范围请求。 为了解决这个问题，现代数据库使用了先前树的修改版本，称为 B+Tree。 在 B+Tree 树中：

• 仅最低节点（叶子） 储存信息 （相关表中行的位置）
• 其余的节点都在这里 用于路由 到正确的节点 搜索期间.

正如您所看到的，这里有更多的节点（两次）。 事实上，您还有其他节点，即“决策节点”，它将帮助您找到正确的节点（它存储关联表中行的位置）。 但搜索复杂度仍然是O(log(N))（只多了一层）。 最大的区别在于 较低级别的节点与其后继节点相连.

使用这个 B+Tree，如果您要查找 40 到 100 之间的值：

• 您只需查找 40（如果 40 不存在，则查找 40 之后最接近的值），就像处理前一棵树一样。
• 然后使用直接继承人链接收集 40 个继承人，直到达到 100 个。

假设您找到 M 个后继者，并且树有 N 个节点。 与之前的树一样，查找特定节点的成本为 log(N)。 但是一旦你得到了这个节点，你就会在M次操作中得到M个后继者，并引用他们的后继者。 本次搜索仅需花费M+log(N) 与前一棵树上的 N 个操作进行比较。 此外，您不必读取完整的树（只需 M+log(N) 个节点），这意味着更少的磁盘使用量。 如果 M 很小（例如 200 行）而 N 很大（1 行），则会有很大的差异。

但这里又出现了新问题（再次！）。 如果您在数据库中（以及关联的 B+Tree 索引中）添加或删除一行：

• 您必须维护 B+Tree 内节点之间的顺序，否则您将无法找到未排序树内的节点。
• B+Tree 必须保持尽可能少的层数，否则 O(log(N)) 时间复杂度将变为 O(N)。

换句话说，B+Tree必须是自序且平衡的。 幸运的是，这可以通过智能删除和插入操作来实现。 但这是有代价的：B+ 树中的插入和删除成本为 O(log(N))。 这就是为什么你们中有些人听说过 使用太多索引不是一个好主意。 真的吗， 您正在减慢表中行的快速插入/更新/删除速度因为数据库需要对每个索引使用昂贵的 O(log(N)) 操作来更新表的索引。 而且，增加索引意味着更多的工作量 交易经理 （将在文末介绍）。

有关更多详细信息，您可以查看维基百科文章 B+树。 如果您想要在数据库中实现 B+Tree 的示例，请查看 本文 и 本文 来自领先的 MySQL 开发人员。 它们都关注 InnoDB（MySQL 引擎）如何处理索引。

注：一位读者告诉我，由于低级优化，B+树应该是完全平衡的。

哈希表

我们最后一个重要的数据结构是哈希表。 当您想要快速查找值时，这非常有用。 而且，理解哈希表将有助于我们以后理解一种常见的数据库连接操作，称为哈希连接（ 散列连接）。 数据库也使用此数据结构来存储一些内部内容（例如 锁表 или 缓冲池，我们稍后会看到这两个概念）。

哈希表是一种通过键快速查找元素的数据结构。 要构建哈希表，您需要定义：

• 关键 为你的元素
• 哈希函数 用于钥匙。 计算出的密钥哈希给出了元素的位置（称为 段 ).
• 比较按键的功能。 找到正确的段后，您必须使用此比较在该段中找到您要查找的元素。

简单的例子

让我们举一个明显的例子：

该哈希表有 10 个段。 因为我比较懒，所以只画了5段，但是我知道你很聪明，所以我就让你自己画另外5段。 我使用了密钥以 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 次操作.

良好的哈希函数

正如你所看到的，根据你所寻找的价值，成本是不一样的！

如果我现在更改密钥的哈希函数模 1（即取最后 000 位数字），则第二次查找只需要 000 次操作，因为段 6 中没有元素。 真正的挑战是找到一个好的哈希函数来创建包含极少数元素的存储桶.

在我的示例中，找到一个好的哈希函数很容易。 但这是一个简单的例子，当关键是：时找到一个好的哈希函数会更困难：

• 字符串（例如 - 姓氏）
• 2 行（例如 - 姓氏和名字）
• 2 行和日期（例如 - 姓氏、名字和出生日期）
• ...

有了好的哈希函数，哈希表查找的成本为 O(1).

数组与哈希表

为什么不使用数组呢？

嗯，好问题。

• 哈希表可以是 部分加载到内存中，其余段可以保留在磁盘上。
• 对于数组，您必须使用内存中的连续空间。 如果您正在加载一个大表 很难找到足够的连续空间.
• 对于哈希表，您可以选择所需的键（例如，国家/地区和人员的姓氏）。

欲了解更多信息，您可以阅读有关的文章 爪哇岛哈希图，这是哈希表的有效实现； 您无需了解 Java 即可理解本文中介绍的概念。

来源： habr.com