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

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

作为一名开发者,我讨厌使用我不明白的技术。此外,关系型数据库已经使用超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/(译者/伍昆 责编/夏梦竹)

原文发布于微信公众号 - CSDN技术头条(CSDN_Tech)

原文发表时间:2016-01-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏葬爱家族

Android高德之旅(17)出行路线规划废话简介总结

今天这篇来记录一下地图SDK中非常重要的一个功能:出行路线规划。我相信高德地图使用最多的也就是这个功能了,当然,我们今天的内容可能还做不到高德地图那么丰富的效果...

15110
来自专栏数据和云

大象起舞:用PostgreSQL解海盗分金问题

今天午休期间刷微信,看到云和恩墨的盖总转了一条朋友圈,说杨长老在Oracle中用SQL解海盗分金问题(原文《无往不利:用SQL解海盗分金的利益最大化问题》,看完...

14060
来自专栏数据结构与算法

BZOJ 1022: [SHOI2008]小约翰的游戏John (Anti-nim)

Description   小约翰经常和他的哥哥玩一个非常有趣的游戏:桌子上有n堆石子,小约翰和他的哥哥轮流取石子,每个人取 的时候,可以随意选择一堆石子,在...

28060
来自专栏牛客网

51信用卡/二面/java岗

19000
来自专栏不二小段

【爬虫与反爬】记一次网址编码研究

相爱相杀的爬虫与反爬工程师啊……愿你们和谐相处。 前些日子写爬虫时遇到一个比较奇怪的编码,是构造目标网址的一个组成部分,我更倾向于说是编码而不是加密,虽然的确有...

35480
来自专栏web编程技术分享

从啥也不会到可以胜任最基本的JavaWeb工作,推荐给新人的学习路线(二)

34050
来自专栏java一日一条

StackOverflow:7个你从未见过的Java问题最佳答案

对开发人员来说, StackOverflow就像一个金矿。对具体的问题,它能帮我们找到最有用的答案,并且我们也可以从上面学习新的知识。

8310
来自专栏三木的博客

Kobject浅析

面向对象的思想的确在应用软件的开发中颇具优势,它让一个个纯逻辑的函数和数据变成了一个个有生命的个体。鉴于性能的考虑,系统软件的实现(例如linux kernel...

24580
来自专栏calmound

poj 1088 滑雪

题意:找出最长的递增道路,可以上下左右四个方向走 DP方程:step[ i ][ j ] = max{ step[ i-1][ j ],  step[ i ][...

34150
来自专栏陈树义

我是SPI,我让框架更加优雅了!

自从上次小黑进入公司的架构组之后,小黑就承担起整个公司底层框架的开发工作。就在刚刚,小黑又接到一个任务:做一个通用的歌曲信息解析框架。即输入歌曲数据,之后返回该...

8910

扫码关注云+社区

领取腾讯云代金券