课程咨询 :13623629309

太原PHP培训 > 达内新闻 > 太原达内php培训师:数据库的原理
  • 太原达内php培训师:数据库的原理

    发布:太原PHP培训      来源:达内新闻      时间:2016-05-03

  • 一提到关系型数据库,我禁不住想:有些东西被忽视了。关系型数据库无处不在,而且种类繁多,从小巧实用的 SQLite 到强大的 Teradata 。但很少有文章讲解数据库是如何工作的但少有文章讲解数据库是如何工作的。你可以自己谷歌/百度一下『关系型数据库原理』,看看结果多么的稀少【译者注:百度为您找到相关结果约1,850,000个…】 ,而且找到的那些文章都很短。现在如果你查找最近时髦的技术(大数据、NoSQL或JavaScript),你能找到更多深入探讨它们如何工作的文章。

    难道关系型数据库已经太古老太无趣,除了大学教材、研究文献和书籍以外,没人愿意讲了吗?

    太原达内

    作为一个开发人员,我不喜欢用我不明白的东西。而且,数据库已经使用了40年之久,一定有理由的。多年以来,我花了成百上千个小时来真正领会这些我每天都在用的、古怪的黑盒子。关系型数据库非常有趣,因为它们是基于实用而且可复用的概念。如果你对了解一个数据库感兴趣,但是从未有时间或意愿来刻苦钻研这个内容广泛的课题,你应该喜欢这篇文章。

    虽然本文标题很明确,但我的目的并不是讲如何使用数据库。因此,你应该已经掌握怎么写一个简单的 join query(联接查询)和CRUD操作(创建读取更新删除),否则你可能无法理解本文。这是唯一需要你了解的,其他的由我来讲解。

    我会从一些计算机科学方面的知识谈起,比如时间复杂度。我知道有些人讨厌这个概念,但是没有它你就不能理解数据库内部的巧妙之处。由于这是个很大的话题,我将集中探讨我认为必要的内容:数据库处理SQL查询的方式。我仅仅介绍数据库背后的基本概念,以便在读完本文后你会对底层到底发生了什么有个很好的了解。

    【译者注:关于时间复杂度。计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。如果不了解这个概念建议先看看维基百度百科,对于理解文章下面的内容很有帮助】

    由于本文是个长篇技术文章,涉及到很多算法和数据结构知识,你尽可以慢慢读。有些概念比较难懂,你可以跳过,不影响理解整体内容。

    这篇文章大约分为3个部分:

    • 底层和上层数据库组件概况
    • 查询优化过程概况
    • 事务和缓冲池管理概况

    回到基础

    很久很久以前(在一个遥远而又遥远的星系……),开发者必须确切地知道他们的代码需要多少次运算。他们把算法和数据结构牢记于心,因为他们的计算机运行缓慢,无法承受对CPU和内存的浪费。

    在这一部分,我将提醒大家一些这类的概念,因为它们对理解数据库至关重要。我还会介绍数据库索引的概念。

    O(1) vs O(n^2)

    现今很多开发者不关心时间复杂度……他们是对的。

    但是当你应对大量的数据(我说的可不只是成千上万哈)或者你要争取毫秒级操作,那么理解这个概念就很关键了。而且你猜怎么着,数据库要同时处理这两种情景!我不会占用你太长时间,只要你能明白这一点就够了。这个概念在下文会帮助我们理解什么是基于成本的优化。

    概念

    时间复杂度用来检验某个算法处理一定量的数据要花多长时间。为了描述这个复杂度,计算机科学家使用数学上的『简明解释算法中的大O符号』。这个表示法用一个函数来描述算法处理给定的数据需要多少次运算。

    比如,当我说『这个算法是适用 O(某函数())』,我的意思是对于某些数据,这个算法需要 某函数(数据量) 次运算来完成。

    重要的不是数据量,而是当数据量增加时运算如何增加。时间复杂度不会给出确切的运算次数,但是给出的是一种理念。

    太原达内php编程

    图中可以看到不同类型的复杂度的演变过程,我用了对数尺来建这个图。具体点儿说,数据量以很快的速度从1条增长到10亿条。我们可得到如下结论:

    • 绿:O(1)或者叫常数阶复杂度,保持为常数(要不人家就不会叫常数阶复杂度了)。
    • 红:O(log(n))对数阶复杂度,即使在十亿级数据量时也很低。
    • 粉:最糟糕的复杂度是 O(n^2),平方阶复杂度,运算数快速膨胀。
    • 黑和蓝:另外两种复杂度(的运算数也是)快速增长。

    例子

    数据量低时,O(1) 和 O(n^2)的区别可以忽略不计。比如,你有个算法要处理2000条元素。

    • O(1) 算法会消耗 1 次运算
    • O(log(n)) 算法会消耗 7 次运算
    • O(n) 算法会消耗 2000 次运算
    • O(n*log(n)) 算法会消耗 14,000 次运算
    • O(n^2) 算法会消耗 4,000,000 次运算

    O(1) 和 O(n^2) 的区别似乎很大(4百万),但你最多损失 2 毫秒,只是一眨眼的功夫。确实,当今处理器每秒可处理上亿次的运算。这就是为什么性能和优化在很多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 更糟糕的复杂度,比如:

    • n^4:差劲!我将要提到的一些算法具备这种复杂度。
    • 3^n:更差劲!本文中间部分研究的一些算法中有一个具备这种复杂度(而且在很多数据库中还真的使用了)。
    • 阶乘 n:你永远得不到结果,即便在少量数据的情况下。
    • n^n:如果你发展到这种复杂度了,那你应该问问自己IT是不是你的菜。

    注:我并没有给出『大O表示法』的真正定义,只是利用这个概念。可以看看维基百科上的这篇文章

    合并排序

    当你要对一个集合排序时你怎么做?什么?调用 sort() 函数……好吧,算你对了……但是对于数据库,你需要理解这个 sort() 函数的工作原理。

    优秀的排序算法有好几个,我侧重于最重要的一种:合并排序。你现在可能还不了解数据排序有什么用,但看完查询优化部分后你就会知道了。再者,合并排序有助于我们以后理解数据库常见的联接操作,即合并联接 。

    合并

    与很多有用的算法类似,合并排序基于这样一个技巧:将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并。

    我们用个简单的例子来看看这是什么意思:

    太原达内php培训

    通过此图你可以看到,在 2 个 4元素序列里你只需要迭代一次,就能构建最终的8元素已排序序列,因为两个4元素序列已经排好序了:

    • 1) 在两个序列中,比较当前元素(当前=头一次出现的第一个)
    • 2) 然后取出最小的元素放进8元素序列中
    • 3) 找到(两个)序列的下一个元素,(比较后)取出最小的
    • 重复1、2、3步骤,直到其中一个序列中的最后一个元素
    • 然后取出另一个序列剩余的元素放入8元素序列中。

    这个方法之所以有效,是因为两个4元素序列都已经排好序,你不需要再『回到』序列中查找比较。

上一篇:太原达内php培训班:.NET应用框架架构设计实践

下一篇:太原达内php培训班:SQL 语句中关于 NULL 的那些坑

最新开班日期  |  更多

php高级开发名企定制班(剩2个名额)

php高级开发名企定制班(剩2个名额)

开班日期:12-30

php高级开发周末班(剩5个名额)

php高级开发周末班(剩5个名额)

开班日期:12-30

php高级开发免费试听(剩5个名额)

php高级开发免费试听(剩5个名额)

开班日期:12-30

更多高级开发工程师精品班

更多高级开发工程师精品班

开班日期:12-30

  • 地址:山西省太原市小店区学府街长治路高新国际A座24层
  • 课程培训电话:13623629309     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56

    在线客服系统