数据库原理

发表于 | 分类于

伯乐在线学习总结

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

本文分为三个部分：

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

算法的复杂度包括：算法的磁盘 I/O 消耗，时间消耗，内存消耗三个方面。这里我们主要讨论时间复杂度。

时间复杂度

时间复杂度用来检验某个算法处理一定量的数据要花多长时间。O(函数) 这里表达的含义就是：这个算法需要多少次运算才能完成。

大O符号是一种算法复杂度的相对表示方式。这里重要的不是数据量，而是当数据量增加时运算如何增加。时间复杂度不会给出确切的运算次数，但是给出的是一种理念。n^2 +2n在百万数据时，2n的部分根本无关紧要。我们只关心复杂度最重要的部分。

时间复杂度经常处于最差情况场景。

合并排序

合并排序有助于我们以后理解数据库常见的联接操作，即合并联接 。

过程

合并排序是把问题拆分为小问题，通过解决小问题来解决最初的问题（注：这种算法叫分治法，即『分而治之、各个击破』）。

  • 拆分阶段，将序列分为更小的序列，有log(N)次运算。
  • 排序阶段，把小的序列合在一起（使用合并算法）来构成更大的序列。每次运算N次，共log(N)次，整体成本是 Nlog(N) 次运算。

强大之处

1.『原地算法』(in-place algorithm)：你可以更改算法，以便于节省内存空间，方法是不创建新的序列而是直接修改输入序列。
2.『外部排序』(external sorting)：你可以更改算法，以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时，这是个很重要的技巧。
3.分布式运行：你可以更改算法，以便于在 多处理器/多线程/多服务器 上运行。

阵列，树和哈希表

接下来介绍三种常用的数据结构，此为现代数据库的强大支柱。

阵列(array)

二维阵列是最简单的数据结构。一个表可以看作是个阵列，这种方法用来保存和可视化数据确实不错，但是在查找的时候，就需要N次运算，那有没有更快的方式呢？这就需要树了。

树和数据库索引

二叉查找树(B树)是带有特殊属性的二叉树，每个节点的关键字必须：
1.比保存在左子树的任何键值都要大；
2.比保存在右子树的任何键值都要小。

这样，按层找确实运算次数有所减少，变为log(N)次。这也是数据库索引所做的。
但是问题又来了，如果你要找的是查找两个值之间的多个元素时，你的运算成本就变为O(N)，因为你需要遍历每一个去寻找符合条件的(例如，使用中序遍历，父节点在中，左中右)。而且，对磁盘I/O消耗巨大。为了解决这个问题，现代数据库使用了一种修订版的树，叫做B+树。

B+树

在一个B+树里：
1.只有最底层的节点（叶子节点）才保存信息（相关表的行位置）；
2.其它节点只是在搜索中用来指引到正确节点的。

B+树

尽管节点更多了（多了两倍）。确实，你有了额外的节点，它们就是帮助你找到正确节点的『决策节点』（正确节点保存着相关表中行的位置）。但是搜索复杂度还是在 O(log(N))（只多了一层）。一个重要的不同点是，最底层的节点是跟后续节点相连接的。

那你想找N之后的M个节点，时间复杂度就是M+log(N)。那你就不需要读整个树，减少了I/O的消耗。

然而还有新的问题（又来了！）。如果你在数据库中增加或删除一行（从而在相关的 B+树索引里）：

1.你必须在B+树中的节点之间保持顺序，否则节点会变得一团糟，你无法从中找到想要的节点。
2.你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N)。

换句话说，B+树需要自我整理和自我平衡。B+树需要自我整理和自我平衡。谢天谢地，我们有智能删除和插入。但是这样也带来了成本：在B+树中，插入和删除操作是 O(log(N)) 复杂度。所以导致了使用太多索引会减慢了快速插入/更新/删除表中的一个行的操作，因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者，增加索引意味着给事务管理器带来更多的工作负荷。

哈希表

当你想快速查找值时，哈希表是非常有用的。而且，理解哈希表会帮助我们接下来理解一个数据库常见的联接操作，叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西（比如锁表或者缓冲池，我们在下文会研究这两个概念）。

哈希表这种数据结构可以用关键字来快速找到一个元素。为了构建一个哈希表，你需要定义：

1.元素的关键字
2.关键字的哈希函数。关键字计算出来的哈希值给出了元素的位置（叫做哈希桶）。
3.关键字比较函数。一旦你找到正确的哈希桶，你必须用比较函数在桶内找到你要的元素。

这里面真正的挑战是找到好的哈希函数，让哈希桶里包含非常少的元素。可以使哈希表里搜索的时间复杂度为 O(1)。

那为什么不用阵列呢？

1.阵列需要分配连续的空间，而哈希表的空间是分散的，剩下的哈希桶可以留在硬盘上。
2.用哈希表的话，你可以选择你要的关键字

全局概览

数据库是由多种互相交互的组件构成的。

核心组件

  • 进程管理器（process manager）：很多数据库具备一个需要妥善管理的进程/线程池。再者，为了实现纳秒级操作，一些现代数据库使用自己的线程而不是操作系统线程。

  • 网络管理器（network manager）：网路I/O是个大问题，尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。

  • 文件系统管理器（File system manager）：磁盘I/O是数据库的首要瓶颈。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统，是非常重要的。

  • 内存管理器（memory manager）：为了避免磁盘I/O带来的性能损失，需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器，尤其是你有很多查询同时使用内存的时候。

  • 安全管理器（Security Manager）：用于对用户的验证和授权。

  • 客户端管理器（Client manager）：用于管理客户端连接。

  • ……

工具

  • 备份管理器（Backup manager）：用于保存和恢复数据。

  • 复原管理器（Recovery manager）：用于崩溃后重启数据库到一个一致状态。

  • 监控管理器（Monitor manager）：用于记录数据库活动信息和提供监控数据库的工具。

  • Administration管理器（Administration manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。

  • ……

查询管理器：

  • 查询解析器（Query parser）：用于检查查询是否合法

  • 查询重写器（Query rewriter）：用于预优化查询

  • 查询优化器（Query optimizer）：用于优化查询

  • 查询执行器（Query executor）：用于编译和执行查询

未完！