精华内容
下载资源
问答
  • 关系型数据库工作原理简述 翻译自 VLADMIHALCEA 的 How does a relational database work,从属于笔者的 服务端基础架构入门与实践。本文只是寥寥数言的关系型数据库工作流程简述,关于关系型数据库工作原理的详细...

    关系型数据库工作原理简述 翻译自 VLADMIHALCEA 的 How does a relational database work,从属于笔者的 服务端基础架构入门与实践。本文只是寥寥数言的关系型数据库工作流程简述,关于关系型数据库工作原理的详细介绍建议阅读 Christophe 的 How does a relational database work。

    概述

    在我撰写 High-Performance Java Persistence training 一书时,我逐步认识到让读者明白关系型数据库工作原理会是了解如何构建高性能的 Java 持久化存储的重要基石。不过关系型数据库中的事务相关的重要概念:原子性、持久性以及检查点等等也是相当绕人。而本文中我希望以相对高屋建瓴的方式来解释关系型数据库内部工作原理,也会涉及一些数据库实现细节。

    Data Pages

    访问磁盘中的数据往往速度较慢,换言之,内存中数据的访问速度还是远快于 SSD 中的数据访问速度。基于这个考量,基本上所有数据库引擎都尽可能地避免访问磁盘数据。并且无论数据库表还是数据库索引都被划分为了固定大小的数据页(譬如 8 KB)。当我们需要读取表或者索引中的数据时,关系型数据库会将磁盘中的数据页映射入存储缓冲区。当我们需要修改数据时,关系型数据库首先会修改内存页中的数据,然后利用 fsync) 这样的同步工具将改变同步回磁盘中。

    Undo log

    由于同时可能由多个事务并发地对内存中的数据进行修改,因此关系型数据库往往需要依赖于某个并发控制机制(2PL 或者 MVCC)来保证数据一致性。因此,当某个事务需要去更改数据表中某一行时,未提交的改变会被写入到内存数据中,而之前的数据会被追加写入到 undo log 文件中。

    Oracle 或者 MySQL 中使用了所谓 undo log 数据结构,而SQL Server 中则是使用 transaction log 完成此项工作。PostgreSQL 并没有 undo log,不过其内建支持所谓多版本的表数据,即同一行的数据可能同时存在多个版本。总而言之,任何关系型数据库都采用的类似的数据结构都是为了允许回滚以及数据的原子性。

    如果当前运行的事务发生了回滚,undo log 会被用于重建事务起始阶段时候的内存页。

    Redo Log

    某个事务提交之后,内存中的改变就需要同步到磁盘中。不过并不是所有的事务提交都会立刻触发同步,过高频次的同步反而会对应用性能造成损伤。不过根据 ACID 原则,提交之后的事务必须要保证持久性,也就是即使此时数据库引擎宕机了,提交之后的更改也应该被持久化存储下来。这里关系型数据库就是依靠 redo log 来达成这一点,它是一个仅允许追加写入的基于磁盘的数据结构,它会记录所有尚未执行同步的事务操作。相较于一次性写入固定数目的数据页到磁盘中,顺序地写入到 redo log 会比随机访问快上很多。因此,关于事务的 ACID 特性的保证与应用性能之间也就达成了较好的平衡。该数据结构在 Oracle 与 MySQL 中就是叫 redo log,而 SQL Server 中则是由 transaction log 执行,在 PostgreSQL 中则是使用 Write-Ahead Log( WAL )。
    下面我们继续回到上面的那个问题,应该在何时将内存中的数据写入到磁盘中。关系型数据库系统往往使用检查点来同步内存的脏数据页与磁盘中的对应部分。为了避免 IO 阻塞,同步过程往往需要等待较长的时间才能完成。因此,关系型数据库需要保证即使在所有内存脏页同步到磁盘之前引擎就崩溃的时候不会发生数据丢失。同样地,在每次数据库重启的时候,数据库引擎会基于 redo log 重构那些最后一次成功的检查点以来所有的内存数据页。

    总结

    上面我们简要讨论的这些原则与考虑都是为了保证基于磁盘的存储的较高吞吐量的同时保证数据一致性。其中,undo lo 主要用于提供原子性(允许回滚),而 redo log 则是保证磁盘页的不可变性。

    参考文献:
    1.关系型数据库工作原理简述

    展开全文
  • 数据库工作原理资料

    2016-11-30 11:46:55
    内容为数据库工作原理相关资料,欢迎大家下载并学习,一起研究探讨。
  • JDBC-ODBC方式连接数据库工作原理解释   1:工作原理: JDBC-ODBC桥驱动程序有sun与Merant公司联合开发,主要的功能是把JDBC API 调用转换成ODBC API 调用,然后ODBC API调用针对供应商的ODBC驱动程序来访问...

    JDBC-ODBC方式连接数据库工作原理解释

     

    1:工作原理:

    JDBC-ODBC桥驱动程序有sun与Merant公司联合开发,主要的功能是把JDBC API 调用转换成ODBC API 调用,然后ODBC API调用针对供应商的ODBC驱动程序来访问数据库,即利用JDBC-ODBC桥通过ODBC来存储数据源。

    如下图:JDBC-ODBC应用模式:

    JDBC-ODBC桥是一个JDBC驱动程序,对ODBC而言,它像是通用的程序,桥为所有适用于ODBC的数据库实现JDBC。

    它作为sun.jdbc.odbc包实现,其中包含一个用来访问ODBC的本地库。由于ODBC被广泛的使用,所有的桥的优点就是让JDBC能够访问所有的数据库。桥支持ODBC 2.X,这是当前大多数据ODBC驱动程序支持的版本。桥驱动程序为java提供的一种把JDBC调用映射为ODBC调用的方法。因此,需要在客户端机器上安装ODBC驱动。JDBC-ODBC桥在JDBCAPI和ODBCAPI之间提供了一个桥梁,这个桥把标准的JDBC调用翻译成对应的ODBC调用,然后通过ODBC库把它们发送给ODBC数据源。

    2:JDBC-ODBC所有的配置

    桥作为包sun.jdbc.odbc与JDK一起自动的安装,无需特殊的配置。java2sdk类库中包含了用于JDBC-ODBD桥接驱动程序的类,因此不需要安装任何附加包就可以使用。但是客户机要通过生成数据源名(Data Source Names,DNS)来配置ODBC管理器。DSN是一个把驱动程序,数据库,一些可选的设置连接起来的命名配置。

    展开全文
  • 本文翻译自Coding-Geek文章:《 How does a relational database work》。原文链接:...本文翻译了如下章节, 介绍数据库整体框架: Global overview 所谓的数据库是指一组易于访问和修...

    本文翻译自Coding-Geek文章:《 How does a relational database work》。原文链接:http://coding-geek.com/how-databases-work/#Buffer-Replacement_strategies
    本文翻译了如下章节, 介绍数据库整体框架:

    这里写图片描述

    Global overview

    所谓的数据库是指一组易于访问和修改的数据集合。但是,但是一组简单的文件也能实现这个功能。实际上,最近简单的一些数据库系统如SQLLite实现的功能与一组文件没有大的差异。但是,SQLLite可以算作设计得非常优秀的一组文件。因为它支持:

    1. 通过事务管理保证了数据的安全性和一致性。
    2. 大数据快速处理能力,能处理百万级的数据。

    我们现在来了解一下数据库包含哪些重要的组件,请看这张数据数据库架构图。

    这里写图片描述

    在写下这篇文章之前,我已经研究了大量关于如何实现数据库的书籍、文档、甚至源代码。因此,别太在意我为何要这样设计数据库的架构图,以及这些组件为何取这样的名字。针对这篇文档,我做了一些取舍。真正需要关注的是这些组件承担的不同职责。 一句话,数据库是由一组相互交互,功能不同的组件构成的系统。

    The core components

    1. The process manager
      进程管理器。许多数据库都有专用的进程池或者线程池管理。甚至,仅仅为了获得纳秒级的性能提升,许多现代处理器设计了专用的线程,代替操作系统的线程。

    2. The network manager
      网络管理。对于分布式数据库来讲,网络I/O是一个关键问题。所以设计了专用的网络管理器。

    3. File system manager
      文件系统管理。磁盘I/O是数据库最关键的性能瓶颈(Disk I/O is the first bottleneck of a database)。设计一个文件管理器能完美的与操作系统的文件系统交互,甚至替换操作系统的文件系统是非常主要的。

    4. The memory manager
      内存管理。为了避免频繁的磁盘I/O操作,通过一个块大的内存来缓存数据是必须的。但是,有了大的内存缓存,就需要对它高效的管理。特别是有大量查询并发访问内存缓存的时候。

    5. Security Manager
      安全管理。管理用户授权和权限认证。

    6. Client manager
      客户端管理。管理客户端的连接。

    The tools

    1. Backup manager
      备份管理。数据库备份与恢复。

    2. Recovery manager
      数据库恢复系统。数据库崩溃后重启,保证数据库的一致性。

      1. Monitor manager
        监控系统。日志记录数据库的活动状态,并提供功能监控数据库系统。
    3. Administration manager
      系统管理。元数据存储管理(例如表名、表结构)。提供工具管理数据表结构、存储空间配置等。

    The query Manager

    1. Query parser
      查询解析器。SQL编译,检查查询语句的有效性。

    2. Query rewriter
      查询重写器。SQL前置优化。

    3. Query optimizer
      查询优化器。对SQL语句做性能上的优化(类似C++编译器优化代码执行路径,提升执行效率)。

    4. Query executor
      查询执行器。编译SQL代码,执行查询数据库操作。

    The data manager

    1. Transaction manager
      事务管理。启动/提交/回滚事务。

    2. Cache manager
      缓存管理。在读取数据之前将数据提前加载到内存;在修改数据之后将数据持久化到磁盘。

    3. Data access manager
      数据访问管理器。操作磁盘上的数据文件。

    接下来的章节,我将重点介绍数据库如果执行一条SQL的查询操作。通过三部分展开:
    - the client manager—客户端管理
    - the query manager—查询管理
    - the data manager —数据管理

    展开全文
  • (翻译)关系型数据库工作原理(一)

    千次阅读 2019-01-17 17:29:32
    原标题:How does a relational database work 作者:Christophe ...ps:翻译这篇文章,是为了强迫自己看得更仔细,同时将好东西分享出来....  每当谈起关系型数据库,我总是觉得缺了点什么。他们无处...

    原标题:How does a relational database work
    作者:Christophe
    http://coding-geek.com/how-databases-work/
    ps:翻译这篇文章,是为了强迫自己看得更仔细,同时将好东西分享出来.现在技术底蕴不厚,写不出好的文章,没关系,翻译大佬的文章也是一条成长之路


    前言

      每当谈起关系型数据库,我总是觉得缺了点什么。他们无处不在。有很多不同的数据库:从小巧犀利的SQLite 到强力支持万亿级数据的数据库。但是解释数据库如何工作的文章却寥寥无几。你可以通过google搜索“how does a relational database work”来看看相关结果到底少到什么地步。并且这些文章都很短。目前,如果你去搜索时下比较流行的技术(Big Data, NoSQL or JavaScript),你会发现很多文章都深入地解释了这些技术背后的原理。
      除开在大学课程上,研究论文和书本上,关系型数据库探讨是否显得太过时,太无聊?
    在这里插入图片描述
      作为一个开发者,我讨厌用一些自己不懂的技术。并且,数据库已经被使用超过40年了,这不是没有道理的。过去几年,我花费了数百个小时的时间才搞懂这些每天都在用的黑匣子。关系型数据库基于可用和可重用的概念,所以很有意思。如果你对了解数据库有兴趣却没有太多时间去深入发掘背后的原理,你可以看下这篇文章。
      这篇文章的主题很明确,不是去教你如何使用数据库。因此,为了保证你能读懂这篇文章,你至少要会简单的连接查询和基础的CRUD操作。其他的我会在文章中解释。
      我会以时间复杂度等计算机科学的东西开始,我知道你们有些人比较讨厌这个概念,但是,不搞清楚这些概念,你很难彻底弄清数据库内部原理。这个话题比较宽泛,我会将焦点放在数据库处理SQL查询,这是我个人认为很有必要的。我只会介绍数据库的基本概念,目的是在文章结束后,你会对引擎下发生的事情有一个更好的了解。
      这是一篇很长的技术性文章,并且包含了很多算法和数据结构。你需要花费一些时间来读它。一些概念比较晦涩难懂,你可以跳过查看结论。

      为了让你更容易读懂,这篇文章分为三个部分。

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

    基础回顾

      很久以前,开发者想要明确知道他们设计的程序需要操作的步数。他们想了解他们的算法和数据结构,这对他们的程序提高cpu和内存的使用效率很重要。
      在这一部分,我会解释一些必须的数据库基本概念以及数据库索引的概念。

    O(1) vs O(n2)

      现在,大多数开发者并不关心时间复杂度…这没啥问题。
      但是,如果你想处理大量的数据(不是指上千这样的级别),或者是追求毫秒级的处理,那么理解这些概念就显得异常重要。也许你已经猜想到了,数据库必须同时处理这两种场景。我不会占用你太多时间,现在就来了解下这个想法。这会帮助我们理解基于成本优化的概念。

    时间复杂度概念

      时间复杂度常常被用来衡量一个算法处理给定规模的输入数据所耗费的时间。为了描述这个时间复杂度,计算机科学家使用大O表示法。此表示法与一个函数一起使用,该函数描述算法对给定规模的输入数据需要多少操作。
      例如,当我说“此算法在O(some_function())”时,这意味着对于一定规模的数据,算法需要some_function(a_certain_amount_of_data)操作来完成其工作。
      我们不关心数据量的多少。我们关心的是伴随着数据规模的增长,所耗费操作数的增长方式。时间复杂度不是用来算具体耗费操作数的,它反映了变化的趋势。
    在这里插入图片描述
      在此图中,你可以看到不同类型复杂度的演变。 我使用对数刻度来绘制它。 换句话说,数据的规模从1增加到10亿。 我们可以看到:

    • O(1)或常数复杂度随数据规模增加保持不变(否则也不会被称作常数复杂度)
    • O(log(n))即使有数十亿数据规模,也能保持在较低的水平
    • 最糟糕的复杂度是O(n2) ,耗费的操作数随着数据规模增加而爆发式增长
    • 其他两种复杂度增长也是很迅速的

    例子

      当数据规模很小的时候,O(1)和O(n2)的差距可以忽略不计。假定我们有个算法需要处理2000个元素时。

    • O(1)算法将花费您1次操作
    • O(log(n))算法将花费你7次操作
    • O(n)算法将花费你2000次操作
    • O(n*log(n))算法将花费你14 000次操作
    • O(n2)算法将花费你4 000 000次操作

      O(1)和O(n2)的差距看起来很多(400万),但是你最多也就损失2ms,一眨眼的时间。事实上,现代处理器每秒可以执行几亿次操作,这也就是为什么很多IT项目中,性能和优化不是什么大问题的原因。
      就像我说的那样,面对大量数据时,弄懂这一概念仍然相当重要。假如这次算法需要处理100万个元素(这对数据库来说并不多)

    • O(1)算法将花费您1次操作
    • O(log(n))算法将花费您14次操作
    • O(n)算法将花费您1 000 000次操作
    • O(n*log(n))算法将花费您1400万次操作
    • O(n2)算法将花费您1 000 000 000次操作

      我就不仔细算了,但我要说,O(n2)算法使得你有时间喝一口咖啡(甚至是两口)。如果数据规模变成1000万,你就可以短暂的休息一下了。

    进阶

      一些常见的结论:

    • 在一个hash算法好的hash表里查找一个元素,时间复杂度是O(1)
    • 在一个平衡良好的树中查找一个结果,时间复杂度是O(log(n))
    • 在一个数组中查找的一个元素,时间复杂度是O(n)
    • 最好的排序算法,时间复杂度是O(n*log(n))
    • 最坏的排序算法,时间负责度是O(n2)
        提示:接下来的部分,我们要讨论那些算法和数据结构

      时间复杂度有多种类型:

    • 平均情况
    • 最好的情况
    • 最坏的情况

      时间复杂度通常是指最坏的情况
      我只讨论了时间复杂度,复杂度也适用于:

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

      当然还有比O(n2)更糟糕的时间复杂度:

    • n4:太烂了! 我将提到的一些具有这种复杂度的算法。
    • 3n:这更糟糕了! 我们将在本文中间看到的算法之一具有这种复杂度(并且它确实在许多数据库中使用)。
    • n!:即使数据量很少,你也永远不会得到你的结果。
    • nn:如果你最终有这种复杂性,你应该问问自己,IT是否真的是适合你的领域…

    注意:我没有给你大O符号的真正定义,只说明了这一思想。 你可以在维基百科上阅读这篇关于真实(渐近)定义的文章。
    https://en.wikipedia.org/wiki/Big_O_notation

    归并排序(Merge Sort)

      当你需要对一个集合排序时,你会怎么做呢?啥?你要调用sort()函数…那行,算是个好答案。但是对数据库来说,你必须知道这个sort()函数是怎么运作的。
      有好几种优秀的排序算法,我这里只会讨论最重要的一种:归并排序。你现在可能还不理解数据排序的重要性,不过在查询优化部分讲完你自然就懂了。除此之外,理解归并排序有助于后面我们理解数据库基本连接操作: merge join.

    合并Merge

      和许多有用的算法一样,归并排序是基于这样的一个技巧:将长度为N/2的两个有序数组中的元素放进长度为N的有序数组里,只需要N次操作。这一过程称为一次合并。
      看个简单的列子,直观感受下:
    在这里插入图片描述
      从上图里可以看出,要想得到长度为8的有序数组,你只需要将这两个长度4的数组各遍历一次。因为他们都是有序的。

    1. 你比较两个数组中的current元素。(current元素是指开始遍历数组中的第一个元素)
    2. 然后将其中较小的那个放进长度为8的数组中
    3. 并将获取较小元素的数组中current指向下一个元素

      重复步骤1、2、3直到获取其中一个数组中的最后一个元素
      最后,将另一个数组的剩下全部元素放进长度为8的数组中。
      现在,我们已经理解了这个技巧,下面是我归并排序的伪代码

    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;
    

      归并排序将问题分解成若干小问题,通过寻找这些小问题的结果最终获得初始问题的结果(注意:这种算法被称为分治)。不理解这个算法不要紧,我第一次看的时候也是很懵逼。下面分析也许会帮助你理解这个算法。我将这个归并算法看成一个两阶段算法:

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

    分割阶段

    在这里插入图片描述
      在分割阶段,我们用3步将初始数组分割成了只包含单一元素的数组。正确来讲,耗费的步数是log(n)(因为N = 8,log(n)= 3)。
      我是怎么知道的呢?
      因为我是天才! 是因为数学。原理是:我们每一步会将初始数组的长度除以2,所以总的步数其实就是初始数组长度可以除以2的次数。这就是对数的精确定义.

    排序阶段

    在这里插入图片描述
      排序阶段,我们从单个元素的数组开始,每一步中都会多次merge,总共耗费操作次数 N= 8.

    • 第一步,总共有4次merge,每个merge操作2次
    • 第二步,总共有2次merge,每个merge操作4次
    • 第三步,总共有1次merge,每个merge操作8次

      因为总共有log(n)步,所以总共耗费的操作数为 n*log(n)。

    归并排序的强大性

      为什么这种算法这么强?
      因为:

    • 你可以修改它以减少内存占用,方法是不创建新的数组,而是在原数组上直接修改。注意:这种算法叫原地算法in-place。
    • 你可以修改它,在不需要付出巨大的I/0代价同时,使用少量的内存和磁盘空间。方法是仅在内存加载当前处理的部分。当你需要使用最多100兆字节的内存缓冲区对一张大小为数千兆字节的表进行排序时,这很重要。注意:这种算法叫外部排序
    • 你可以修改它,使之在多个进程/线程/服务器上运行。比如,分布式归并排序是Hadoop(大数据框架)的关键组件之一。
    • 这种算法可以将铅变成黄金(真的)

      这种算法是大多数数据库使用的算法之一。如果你想进一步了解,你可以阅读这篇讨论数据库常见算法优缺点的论文。
    http://wwwlgis.informatik.uni-kl.de/archiv/wwwdvs.informatik.uni-kl.de/courses/DBSREAL/SS2005/Vorlesungsunterlagen/Implementing_Sorting.pdf

    Array, Tree and Hash table

      现在我们已经讨论完时间复杂度和排序,接下去我们讨论三种数据结构。它们非常重要,是现代数据库的基石。我还会介绍数据库索引的概念。

    Array

      二维数组是最简单的数据结构。表可以被视为一个数组,如下图:
    在这里插入图片描述

    • 二维数组就是一个带行和列的表
    • 每一行代表一个主题
    • 列用来描述主题
    • 每一列存储一个明确的数据类型(integer, string, date …)

      存储和可视化数据很容易,但是当你需要查找特定值的时候就比较糟糕了。
      例如,你想要找到所有在UK工作的男孩,你需要查看每一行是否这行包含UK。这会耗费N次操作(N是行数)。这看起来还行,但是就没有更快的方式了吗?这就轮到Tree出场了。
      注意:大多数现代数据库都提供高级数组来高效地存储表,如堆组织表或索引组织表。 但它并没有改变在一组列上快速搜索特定条件的问题。

    Tree and database index

    The idea

      二叉搜索树是具有特定属性的二叉树。每个节点的key必须是:

    • 比存储在左子树中的所有key大
    • 比存储在右子树中的所有key小

    在这里插入图片描述
       这棵树有N = 15个元素,寻找key = 208:

    • 我们从key=136的根节点开始, 136 < 208, 所以在key=136节点的右子树查找。
    • 398>208,所以继续在key=398节点的左子树查找。
    • 250>208,所以继续在key=250节点的左子树查找。
    • 200<208,所以在key=200节点的右子树查找,但是右子树不存在,所以查找的值不存在。(如果存在,那必然会在key=200节点的右子树上)

       现在,我慢看一下查找key=40的过程:

    • 我们从key=136的根节点开始, 136 < 40, 所以在key=136节点的左子树查找。
    • 80>40,继续在key=80节点的左子树查找
    • 40=40,节点存在,我提取存在节点内部,数据行的id(未在图中画出)并根据id在表中查找。
    • 知道行的id,我就清楚知道数据在表中精确的位置,我就可以立马得到它

       最后,这两次搜索都耗费了树级别范围内操作次数。如果你仔细阅读了归并排序部分,确定它的时间复杂度为log(N)级别。所以搜索的成本是log(N),还行。

    回到我们的问题

       但是这些东西非常抽象,所以让我们回到我们的问题。不去想这些愚蠢的数字,把表里的字符串想象成代表某个人工作的的国家。假设你的表里有一个包含“国家”的列。

    • 如果你想知道谁在UK工作。
    • 在这棵树上查找代表UK的节点
    • 在这个“UK节点”内,你会找到包含在UK工作的人的定位。

      这种搜索方式只会花费你log(N)次操作而不是直接查找数组的N次操作。你刚刚所想象的就是数据库索引。
      只要你有一个比较key(一组列)的函数去建立key之间的顺序(这是针对数据库所有基本类型的情况),你就可以为任何列构建tree index(字符串,整数,2个字符串,整数和字符串,日期…)。

    B+Tree Index

      尽管通过上面的二叉搜索树,你可以轻松查找一个具体的值。但是当你想要查找两个值之间所有的元素,就会出现大问题。它将花费O(N),因为你必须查看树中的每个节点并检查它们是否在这两个值之间(例如,对树的有序遍历)。另外,这种操作不是磁盘I / O友好型,因为你必须查看完整的树。 我们需要找到一种能有效进行范围查询的方法。为了解决这个问题,现代数据库使用 B+Tree,它是上面二叉搜索树的改良版。
      在B+Tree中:

    • 只有最低的叶子节点中存储信息(相关表中行的位置)
    • 其他节点在这里只是负责搜索中路由到正确的节点。

    在这里插入图片描述
      就像你看到的那样,节点更多了(两倍还多)。实际上,你有额外的节点,“决策节点”将帮助你找到正确的节点(存储了数据行在关联表中的位置)。但是搜索复杂度还是O(log(N))(就多了一层)。最大的区别在于,最底层的节点链接到了他们的后继结点上。
      通过B+Tree,你可以查找介于40和100直接的值:

    • 你只需要按照二叉搜索树的方式查找40的节点,(如果40不存在,就找一个值最接近的)
    • 在40节点的所有后继者中查找所有小于100的节点

      假设有M个后继者,树有N个节点。和二叉搜索树一样,查找具体节点花费log(N)次。一旦你获得了这个节点,你只需要通过M次操作就能从所有的后继者中获取满足条件的M个后继。对比二叉搜索树的N次操作,这种查找方式只需要M + log(N) 次操作。你不需要遍历整棵树(就M + log(N)个节点),这就意味着更少的磁盘使用。如果M比较小(比如200行)、N比较大(100万行),差距就会非常明显。
      但是,又有新的问题了(为什么要说“又”字?)。如果你想在建立了B+数索引的数据库中新增或者删除一行记录:

    • 你必须确保B+树内部的节点是有序的,否则你很难在无序的节点中查找出正确的值。
    • 你必须确保树的高度尽可能的低,否则时间复杂度可能会由O(log(N)) 变成 O(N).

      换句话说,B+树必须保持自我有序、自我平衡。比较庆幸的是,这可以通过智能删除和插入来实现。但是,这么做是有成本的:B +树中的插入和删除是O(log(N))。所以我们会常常听到“不要滥用索引”。实际上,因为数据库更新表的索引时,每个索引都要付出O(log(N))的代价,因此减慢了表中行的快速插入/更新/删除速度。另外,添加索引意味着事务管理器工作量的增加(我们将在文章末尾看到这个事务管理器)。

    想要进一步了解,你可以看看维基百科上这篇关于B +树的文章。
    https://en.wikipedia.org/wiki/B%2B_tree
    如果你想看数据库中B +树实现的例子,可以阅读《a core developer of MySQL》中的两篇文章。
    https://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/
    https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/
    这两篇文章核心是innoDB(MySQL的引擎)如何处理索引。
    注意:有读者指出,由于low-level优化,B+树需要完全平衡。

    Hash table

      我们最后一个重要的数据结构是哈希表。哈希表对于快速查找是非常有用的。另外,理解哈希表会有助于我们理解一种数据库基本连接操作:hash join。这个数据结构也被数据库用来存储一些系统内部东西(比如锁定表或缓冲池,我们稍后会看到这两个概念)。
      哈希表是一种根据键值快速查找对应元素的数据结构。 要构建哈希表,你需要定义:

    • 元素的key
    • 针对key的哈希函数,计算key的哈希值获取元素的存放位置(称之为“桶”)
    • 一个比较key的函数。一旦你确定了桶的位置,你需要通过比较在桶中查找出对应的元素。

    一个简单的例子

      来看一个具体的例子:
    在这里插入图片描述
      这个哈希表有10个桶,我比较懒,剩下5个没有画出来,但是我认为你比较聪明,能想象出来其他5个。我使用的哈希函数是key模以10,像这样:

    • 如果最后一个数字为0,则元素始终存放于序号为0桶内。
    • 如果最后一个数字为1,则元素始终存放于序号为1桶内。
    • 如果最后一个数字为2,则元素始终存放于序号为2桶内。

      我使用简单整数比较作为比较函数。
      假设你要找元素78:

    • 上面的哈希表计算出78的哈希码是8
    • 在序号为8的桶内寻找,第一个元素就是78
    • 哈希表返回查找到的元素78
    • 整个查找只花费了2次操作(1次计算哈希值,另外1次在桶里查找元素)

    假设要查找元素59:

    • 计算出59的哈希值为9
    • 在序号为9的桶里,第一个元素是99。 99!= 59,元素99不是我们想要的
    • 用同样的方法,比较第二个元素(9)、第三个元素(79)、…、最后一个元素(29)
    • 查找的元素不存在
    • 查找总共花费7次操作

    优秀的哈希函数

      从上面可以看出,查找的值不一样,消耗的时间也是不一样的。如果我修改hash函数,对key模以1 000 000(也就是取最后6位)。第二次查找之会花费1次操作,因为在000059的桶里压根就没有任何元素。
    真正的挑战是找到一个优秀的哈希函数,它将创建包含极少量元素的桶。

      在我的例子中,找一个优秀的哈希函数比较容易。但这只是一个简单的例子。当你的key是以下类型时,就会变得很困难:

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

      一个优秀的哈希函数可以使查找时间控制在O(1)。

    Array vs hash table

    为什么不选择数组?

    呃,这个问题问得好。
    哈希表可以只加载一半的数据到内存,剩下一半留在磁盘里。
    使用数组你必须使用连续的内存空间。如果你加载大表,很难找到够用的连续空间。
    哈希表可以选择你需要的key(比如国家和姓氏)。

    想要了解更多,你可以阅读我这篇关于 Java HashMap的文章。 Java HashMap是哈希表的一个高效实现。阅读这篇文章也不需要你懂Java 。
    http://coding-geek.com/how-does-a-hashmap-work-in-java/


    转载请注明作者和出处

    展开全文
  • 本文翻译自Coding-Geek文章:《 How does a relational database work》。 ... 本文翻译了如下章节: 一、 前言 ...谈到关系型数据库,我想不到有什么东西能缺少它,可以说关系型数据已经无处不在...
  • 关系型数据库工作原理-数据结构(3)

    万次阅读 2016-04-29 07:07:15
    备注:现代数据库使用更高级的数组结构来存储表数据,如heap-organized tables或者index-organized tables。但是都没有解决如何在数组中根据一些列的过滤条件快速筛选数据的问题。 三、Tree and database index ...
  • 关系型数据库工作原理-高速缓存(20)

    千次阅读 2016-03-27 07:54:28
    举个例子说明它的工作原理,这个简单的示例中缓存池能容纳3个数据。 Cache Manger使用数据1后,将1放入缓存。 Cache Manger使用数据4后,将4放入缓存。 Cache Manger使用数据3后,将3放入缓存。 Cache ...
  • 关系型数据库工作原理-归并排序(2)

    千次阅读 2016-04-22 06:58:42
    关系型数据库工作原理-事务管理(一): http://blog.csdn.net/ylforever/article/details/51048945 6. 关系型数据库工作原理-事务管理(二): http://blog.csdn.net/ylforever/article/details/51082294
  • 数据库管理员(DBA)的一项基本的技能是对SQL数据库引擎的系统数据库的深刻理解。数据库开发人员了解SQLSERVER自带的系统数据库也是十分有用的。下面就列出了其中的一些系统数据库。(注:如果你决定研究一下这些...
  • 数据库管理员(DBA)的一项基本的技能是对SQL数据库引擎的系统数据库的深刻理解。数据库开发人员了解SQLSERVER自带的系统数据库也是十分有用的。下面就列出了其中的一些系统数据库。(注:如果你决定研究一下这些...
  • 1) 如果所有的事务仅仅是读取数据,他们能并行工作,相互无影响。 2) 如果有一个事务(哪怕只有一个)在修改其他事务读取的数据,数据库需要考虑如何屏蔽数据修改对其它事务的影响。并且,需要要确保修后的数据不会...
  • 你重启了数据库,然后数据库恢复工作就开始了。 ARIES使数据库从崩溃中恢复有三个步骤: 1. The Analysis pass (分析阶段):恢复程序读取所有的事务日志,重建灾难发生时现场环境。以决定哪些事务需要回滚,...
  • 分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理
  • 数据库系统原理教程

    2007-11-13 12:35:17
    数据库系统原理教程详细介绍数据库工作原理!
  • 数据库系统原理 - - (5)数据库编程

    万次阅读 2020-07-19 12:09:42
    数据库系统原理
  • 数据库原理

    2018-03-24 18:51:56
    详细讲述了数据库原理,对大数据和数据相关工作者有很大帮助!
  • 关系型数据库工作原理(翻译) 关系型数据库工作原理(翻译)
  • 数据库系统原理 - - (3)数据库设计

    万次阅读 2020-07-03 08:55:25
    上一篇:数据库系统原理【一】 文章目录第三章:数据库设计1.数据库设计概念1)数据库的生命周期2)数据库设计的目标3)数据库设计的内容4)数据库设计的方法a. 直观设计法b.规范设计法c.计算机辅助设计法5)数据库...
  • 通过两个图形说明了在oracle数据库中b-tree索引和位图索引的工作原理
  • 数据库原理习题

    万次阅读 2020-09-07 18:39:47
    数据库原理是每个计算机专业的学生必须掌握的课程之一,所以学好数据库原理对日后实际工作和项目十分重要。这篇博客通过总结广州大学数据库原理课程和教材中的例题,希望能够对数据库原理加深理解。
  • 数据库索引工作原理

    千次阅读 2016-06-24 20:31:07
    数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。  在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以...
  • 数据库select工作原理

    千次阅读 2013-06-28 14:20:28
    select在数据库中的工作原理。 B/S架构中最经典的话题无非于三层架构,可以大概分为数据层,业务逻辑层和表示层,而数据层的作用一般都是和数据库交互,例如查询记录。我们经常是写好查询SQL,然后调用程序执行SQL...
  • 以至于从来没有研究过它们的工作原理,在这里我们说一说select在数据库中的工作原理。 B/S架构中最经典的话题无非于三层架构,可以大概分为数据层,业务逻辑层和表示层,而数据层的作用一般都是和数据库交互,例如...
  • 说明:这是武汉理工大学计算机学院【数据库系统原理】课程课内实验。 >>点击查看WUTer计算机专业实验汇总 谨记:纸上得来终觉浅,绝知此事要躬行。 1、实验内容: 项 目 名 称 实验内容 ...
  • SQLite数据库工作原理

    千次阅读 2018-12-18 16:35:23
    介绍 数据库是构建软件系统的重要组成部分,用于有效地存储和读取数据。在这里,我们将使用早期版本的SQLite讨论数据库实现的一些体系...如果您愿意在编码级别学习数据库的内部,那么SQLite是最好的开源数据库,具...
  • 数据库基本原理

    千次阅读 2019-05-09 19:58:14
    数据库基本原理我对DB的理解1、数据库的组成:存储+实例不必多说,数据当然需要存储;存储了还不够,显然需要提供程序对存储的操作进行封装,对外提供增删改查的API,即实例。一个存储,可以对应多个实例,这将提高...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 402,707
精华内容 161,082
关键字:

数据库工作原理