当前位置:首页 » 个人博客 » 正文

关于关系数据库是如何工作的(篇章1)

 人参与  2022年11月20日 13:00  分类 : 个人博客  点这评论

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

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

 

logos of main databases

 

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

 

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

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

 

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

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

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

内容 [显示]

 

回归基础

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

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

 

O(1)对O(n2)

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

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

 

这个概念

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

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

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

time complexity analysis

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

  • O(1)

    或者恒定复杂度保持不变(否则就不叫恒定复杂度)。
  • O(log(n))即使有数十亿数据也保持低位.

  • 最糟糕的复杂性是

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

  • 两个

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

    es正在迅速增加。

 

例子

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

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

    2

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

O(1)和O(n)的区别2)看起来很多(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

    2

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

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

 

更深入

给你一个想法:

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

    2

    )复杂性

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

 

时间复杂性有多种类型:

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

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

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

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

 

当然还有比n更复杂的情况2,比如:

  • n4

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

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

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

 

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

 

合并排序

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

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

 

合并

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

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

merge operation during merge sort algorithm

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

  • 1)比较两个数组中的两个当前元素(第一次current=first)
  • 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;

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

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

 

分裂阶段

division phaseduring merge sort algorithm

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

我怎么知道?

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

 

分类阶段

sort phaseduring merge sort algorithm

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

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

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

 

合并排序的威力

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

因为:

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

注:这种算法称为原状.

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

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

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

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

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

 

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

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

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

本文标签:博客    

微信公众号:升级接入中

<< 上一篇下一篇 >>
为祖国加油
祖国加油,相信新的一年会更好...
为祖国加油
森林防火,人人有责。祖国加油...

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

搜索

网站分类

Tags列表

最新留言

++发现更多精彩++

    海内存知己,天涯若比邻。

黔ICP备2020011602号黔ICP备2020011602号-8
贵公安备52052602000222号

❤安全运行 Copyright © 2018-2023 李烨自媒体 版权所有.

本站采用创作共用版权 CC BY-NC-SA 3.0 CN 许可协议,转载或复制请注明出处