返回 登录
0

关系型数据库是如何运作的(上)

阅读17360

一说到关系型数据库,我总感觉缺了点什么。如果你尝试透过“关系型数据库是如何运作的”的关键词句来进行搜索,其搜索结果是少量的而且内容是简短的。难道说是由于它已经太老旧而已经不再流行吗?

作为一名开发者,我讨厌使用我不明白的技术。此外,关系型数据库已经使用超40年,肯定有它过人的原因。因此,我花了大量时间来想真正弄懂它里面如同黑盒子那样的奥秘。关系型数据库实际上是非常有趣的,因为它是基于实用和复用的概念。但是限于篇幅,以下我将把重点放在数据库如何处理SQL查询的问题上。本文内容大致划分为以下三部分:

1.低阶数据库和高级数据库组成概述
2.查询优化流程的处理概述
3.事务和缓冲池管理概述

基本概念回顾

在编程年代早期,开发者是必须要理解清楚自己所进行操作的原理的。他们对于所使用的算法和数据结果是了然于胸的,因为他们很注重在计算机配置较低时于CPU和内存上的开销。在这一节,我首先要介绍的是数据库索引。

O(1) vs O(n2)

时间复杂度用于计算算法处理数据的用时。科学家使用大O表示法来进行时间复杂度描述,其定义是对于输入的数据算法需要进行多少步运算。这里要强调的是,它的核心是数据量增加对运算增加的影响而不是数据量的多少。时间复杂度不会直接给出精确的运算步数,而是以趋势的方式展示。

图片描述

在上图中,你可以看到不同复杂度的发展趋势,我使用的方法是对数法。换言之,数据量将会从1快速地增加到10亿。我们可以得出以下结论:

  • O(1)或常数复杂度是维持不变的
  • O(log(n))在处理10亿数据量时也维持与一个较低复杂度水平
  • O(n2)复杂度增长最快
  • 其余两种复杂度位于中游

举例说明

如果是处理少量数据,O(1)和O(n2)的差别是不明显的。例如是2000个运算元素:

  • O(1) 的运算量是1
  • O(log(n)) 的运算量是7
  • O(n) 的运算量是2000
  • O(n*log(n)) 的运算量是14000
  • O(n2) 的运算量是4 000 000

尽管O(1) 和 O(n2)的运算量的差距是4百万,但是这仅需2ms,也就是眨眼的功夫。此外,如果使用的是多核处理器,其运算速度会更快。所以性能和优化问题在现在的重视程度无法跟以往相比。

如果处理的数据量是1 000 000,其结果又会如何呢?

  • O(1) 的运算量是1
  • O(log(n)) 的运算量是14
  • O(n) 的运算量是1 000 000
  • O(n*log(n)) 的运算量是14 000 000
  • O(n2) 的运算量是1 000 000 000 000

这样一来,你可以先喝杯咖啡休息下再回来看结果了!如果再加个0,你可以先进行午休了!

进一步说明

这里有几点提示:
在一个完整hash表中进行一次搜索会提交一个元素给O(1)
在一个全平衡树种进行一次搜索会提交一个结果给O(log(n))
在一个数组中进行一次搜索会提交一个结果给O(n)
最优排序算法的时间复杂度与O(n*log(n))相当
低效排序算法的时间复杂度与 O(n2)相当

注意:具体算法和数据结果会在本文稍后列示

时间复杂度的类型有:

  • 平均事件场合
  • 最佳时间场合
  • 最差时间场合

时间复杂度通常是最差时间场合。除了时间复杂度,复杂度还可以用来表示内存使用和磁碟I/O占用情况等。诚然,比n2更复杂的计算有n4,3n,nn 。

合并排序

如果你要对一个集合进行排序该如何做呢?什么?使用sort()?听起来是个好的答案。

但如果排序对象是一个数据库,你就务必知道sort()的工作原理。这里我介绍排序算法中最重要的一种:合并排序。对合并排序理解透彻,一方面可以掌握如何进行查询优化,二来可以更好地理解本文稍后说到的合并join运算。

合并(Merge)

合并排序的运算过程是:合并两个已排序的N/2数组到一个已排序N个元素数组,例如下图所示:

图片描述

以上是本系列文的上篇,更多内容请关注后续文章,后续内容简述:全局概念,客户管理器,查询管理器,数据管理器。

英文链接:http://coding-geek.com/how-databases-work/

(译者/伍昆 责编/夏梦竹)

评论