大数据中数据库是如何工作的（一）

　　当涉及到关系数据库时，我不禁会以为有些东西丢失了。它们无处不在。有许多不同的数据库：从小型且有用的SQLite到功能强大的Teradata。但是，只有少数几篇文章解释了数据库的工作方式。你可以自己在Google上搜索“关系数据库的工作原理”，可以查看结果很少，而且文章简短。现在介绍它们的工作原理，看看大数据中数据库是如何工作的。
 

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

　　作为开发人员，肯定不会使用自己不了解的东西。而且，如果数据库已经使用了很多年，则一定有原因。有必要花时间来真正了解每天使用的这些奇怪的黑匣子。 关系型数据库是非常有趣的，因为他们是基于有用的和可重复使用的概念。
 

　　首先，你要知道如何编写一个简单的联接查询和基本的CRUD查询。开发人员必须确切地知道他们正在编码的操作数。他们完全知道自己的算法和数据结构，因为他们负担不起浪费速度较慢的计算机的CPU和内存。
 

　　O(1)对O(n 2)
 

　　如今，许多开发人员都不在乎时间的复杂性……他们是对的!
 

　　但是，当你处理大量数据时，或者如果你要争夺毫秒级的时间，那么了解此概念就变得至关重要。这个概念的时间复杂度是用来看看的算法需要多长时间为给定的数据量。为了描述这种复杂性，计算机科学家使用了数学上的大O符号。该符号与描述了算法针对给定数量的输入数据需要进行多少次操作的函数一起使用。
 

　　例如，当“此算法在O(some_function())中”时，它意味着对于一定数量的数据，该算法需要some_function(a_certain_amount_of_data)操作才能完成其工作。
 

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

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

　　在O(1)或恒定的复杂性保持不变(否则就不叫常复杂)。
 

　　即使有数十亿个数据，O(log(n))仍保持较低水平。
 

　　复杂度最差的是O(n 2)，其中操作数量迅速激增
 

　　这两个OT ^ h铒共米p乐喜牛逼我ES正在迅速增加
 

　　例子
 

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

　　O(1)算法将花费你1次操作
 

　　O(log(n))算法将花费你7次操作
 

　　O(n)算法将花费你2000次操作
 

　　O(n * log(n))算法将花费你14000次操作
 

　　O(n 2)算法将花费你4000000次操作
 

　　O(1)和O(n 2)之间的差异似乎很大(400万)，但是你最多会在2毫秒内迷失方向，只是眨眼的时间。实际上，当前的处理器每秒可以处理数亿个操作。这就是为什么性能和优化在许多IT项目中都不是问题的原因。
 

　　正如前面所说，面对大量数据时，了解这一概念仍然很重要。如果这一次该算法需要处理1 000 000个元素(对于数据库来说这不是那么大)：
 

　　O(1)算法将花费你1次操作
 

　　O(log(n))算法将花费你14次操作
 

　　O(n)算法将花费你1000000次操作
 

　　O(n * log(n))算法将花费你14000000次操作
 

　　O(n 2)算法将花费你1000000000000次操作
 

　　没有做数学运算，但是用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是否真的是你的领域……
 

　　合并排序
 

　　当你需要对集合进行排序时，你会怎么做?你可以调用sort()函数，但是对于数据库，你必须了解sort()函数的工作方式。
 

　　有几种不错的排序算法，重点介绍一种：合并排序。你可能现在不明白为什么排序数据很有用，但是你应该在查询优化部分之后进行。
 

　　合并：像许多有用的算法一样，合并排序基于一个技巧：将2个大小为N / 2的排序数组合并为N个元素的排序数组仅需要N次操作。此操作称为合并。
 

　　你可以在该图上看到，要构造最终的8个元素的排序数组，只需要在2个4元素数组中进行一次迭代即可。由于两个4元素数组均已排序：
 

　　1)比较两个数组中的两个当前元素(current =第一次，第一次)
 

　　2)然后将最低的一个放入8个元素的数组中
 

　　3)并转到数组中的下一个元素，你选择了最低元素
 

　　并重复1,2,3，直到到达数组之一的最后一个元素。
 

　　然后，将另一个数组的其余元素放入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的次数。这是对数的精确定义(以2为底)。
 

　　分选阶段
 

　　在排序阶段，从单一数组开始。在每个步骤中，你将应用多个合并，并且总成本为N = 8次操作：
 

　　第一步，你有4个合并，每个合并需要2个操作
 

　　在第二步中，你有2个合并，每个合并花费4个操作
 

　　在第三步中，你有1个合并需要8次操作
 

　　由于存在log(N)个步骤，因此总成本为N * log(N)个操作。
 

　　合并排序的力量
 

　　为什么此算法如此强大?
 

　　因为：
 

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

　　注意：这种算法称为就地。
 

　　你可以对其进行修改，以便同时使用磁盘空间和少量内存，而不会产生巨大的磁盘I / O损失。这个想法是只将当前正在处理的零件加载到内存中。当你需要对仅具有100 MB内存缓冲区的多GB表进行排序时，这一点很重要。
 

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

　　你可以修改它以在多个进程/线程/服务器上运行。
 

　　例如，分布式合并排序是Hadoop(这是大数据中的THE框架)的关键组件之一。

　　该算法可以将铅变成金(真实的事实!)。
 

　　这种排序算法已在大多数(如果不是全部)数据库中使用，但并不是唯一的一种。如果你想了解更多信息，可以阅读这份研究论文，其中讨论了数据库中常见排序算法的优缺点。
 

　　数组，树和哈希表
 

　　既然我们了解了时间复杂度和排序背后的思想，那么我必须向你介绍3种数据结构。这很重要，因为它们是现代数据库的骨干。我还将介绍数据库索引的概念。
 

　　大批
 

　　二维数组是最简单的数据结构。一个表可以看作是一个数组。例如：
 

 

　　此二维数组是具有行和列的表：
 

　　每行代表一个主题
 

　　这些列描述主题的功能。
 

　　每列存储某种类型的数据(整数，字符串，日期…)。
 

　　尽管存储和可视化数据很棒，但是当你需要查找特定值时，它很糟糕。
 

　　树和数据库索引
 

　　二进制搜索树是具有特殊属性的二进制树，每个节点中的关键字必须为：
 

　　大于存储在左侧子树中的所有键
 

　　小于存储在右侧子树中的所有键
 

　　让我们看一下视觉上的含义
 

 

　　这棵树有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)级别。因此搜索的成本为log(N)，还不错!
 

　　回到我们的问题
 

　　但是，这些内容非常抽象，让我们回到我们的问题上来。想象一个代表上表中某人所在国家的字符串，而不是一个愚蠢的整数。假设你有一棵包含表的“国家”列的树：
 

　　如果你想知道谁在英国工作
 

　　你看树得到代表英国的节点
 

　　在“英国节点”内，你将找到英国工人行的位置。
 

　　如果你直接使用数组，则此搜索仅花费你log(N)个操作，而不是N个操作。你刚刚想象的是一个数据库索引。
 

　　你可以为任何一组列(一个字符串，一个整数，2个字符串，一个整数和一个字符串，一个日期……)构建树索引，只要你具有比较键(即列组)的功能即可，你可以在键之间建立顺序 (数据库中的任何基本类型都是这种情况)。
 

　　B +树索引
 

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

　　只有最低的节点(叶子)存储信息(相关表中行的位置)
 

　　其他节点只是在搜索过程中路由到正确的节点。
 

 

　　如你所见，有更多的节点(更多的节点)。实际上，你还有其他节点，即“决策节点”，可以帮助你找到合适的节点(该节点将行的位置存储在关联表中)。但是搜索的复杂度仍然在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 000万行)，则会产生很大的差异。
 

　　但是又有新的问题!如果你在数据库中(因此在关联的B + Tree索引中)添加或删除行：
 

　　你必须保持B + Tree内部节点之间的顺序，否则你将无法在混乱中找到节点。
 

　　你必须在B + Tree中保持尽可能少的级别数，否则O(log(N))中的时间复杂度将变为O(N)。
 

　　换句话说，B +树需要自我排序和自我平衡。幸运的是，这可以通过智能删除和插入操作实现。但这要付出代价：B +树中的插入和删除在O(log(N))中。这就是为什么有些人听说使用太多索引不是一个好主意的原因。确实，你正在减慢表中行的快速插入/更新/删除的速度，因为数据库需要使用每个索引的昂贵O(log(N))操作来更新表的索引。而且，添加索引意味着事务管理器会增加工作量(我们将在本文结尾看到该管理器)。
 

　　哈希表
 

　　我们最后一个重要的数据结构是哈希表。当你想快速寻找价值时，这非常有用。此外，了解哈希表将有助于我们稍后理解称为哈希联接的常见数据库联接操作。数据库还使用此数据结构来存储一些内部内容(例如锁表或缓冲池，稍后将介绍这两个概念)
 

　　哈希表是一种数据结构，可快速找到具有其键的元素。要构建哈希表，你需要定义：
 

　　你元素的关键
 

　　键的哈希函数。计算得出的键的哈希值给出了元素(称为buckets)的位置。
 

　　比较键的功能。找到正确的存储桶后，你必须使用此比较在存储桶中查找要查找的元素。
 

　　一个简单的例子
 

　　让我们看一个直观的例子：
 

 

　　该哈希表有10个存储桶。由于我很懒，我只抽了5个水桶，但我知道你很聪明，所以让你想象另外5个水桶。我使用的哈希函数是密钥的模10。换句话说，我只保留元素键的最后一位来查找其存储桶：
 

　　如果最后一位数字为0，则该元素最终出现在存储区0中，
 

　　如果最后一位数字为1，则该元素最终出现在存储桶1中，
 

　　如果最后一位数字为2，则该元素最终出现在存储桶2中，
 

　　…

　　我使用的比较函数只是2个整数之间的相等。
 

　　假设你要获取元素78：
 

　　哈希表计算78的哈希码，即8。
 

　　它在存储桶8中查找，找到的第一个元素是78。
 

　　它给你元素78
 

　　的 搜索成本只有2个操作(1计算散列值，而另一个用于求出铲斗内的元件)。
 

　　现在，假设你要获取元素59：
 

　　哈希表计算59的哈希码，即9。
 

　　它在存储桶9中查找，找到的第一个元素是99。由于99!= 59，因此元素99不是正确的元素。
 

　　使用相同的逻辑，它查看第二个元素(9)，第三个元素(79)，…和最后一个元素(29)。
 

　　元素不存在。
 

　　搜索需要进行7次操作。
 

　　良好的哈希函数，根据你所寻找的价值，成本是不一样的!
 

　　如果现在我用键的模数1 000 000更改哈希函数(即取最后6位数字)，则第二次搜索仅花费1次操作，因为存储桶000059中没有元素。真正的挑战是找到一个好的散列函数，该函数将创建包含少量元素的存储桶。
 

　　一个简单的示例，当键为：
 

　　字符串(例如某个人的姓氏)
 

　　2个字符串(例如，一个人的姓氏和名字)
 

　　2个字符串和一个日期(例如，一个人的姓，名和出生日期)
 

　　…
 

　　有了良好的哈希函数， 哈希表中的搜索就在O(1)中。
 

　　数组与哈希表
 

　　为什么不使用数组?哈希表可以一半加载到内存中，而其他存储桶可以保留在磁盘上。对于数组，你必须在内存中使用连续的空间。如果要加载大表，则很难有足够的连续空间。使用哈希表，你可以选择所需的键(例如国家/地区和一个人的姓氏)。
 

　　以上是数据库内部的基本组件。大数据中数据库如何工作我们分成几个部分介绍，今天就先到这里了，对大数据分析感兴趣的朋友可以到AAA教育官网了解一下。