死磕数据库系列（一）：关系型数据库是如何工作的？
知识体系结构
SQL DB - 关系型数据库是如何工作的
知识点
从数据结构说起
时间复杂度
对于数据库而言，重要的不是数据量，而是当数据量增加时运算如何增加。
时间复杂度用来检验某个算法处理一定量的数据要花多长时间，时间复杂度不会给出确切的运算次数，但是给出的是一种理念。
- 绿：O(1)或者叫常数阶复杂度，保持为常数（要不人家就不会叫常数阶复杂度了）。
- 红：O(log(n))对数阶复杂度，即使在十亿级数据量时也很低。
- 粉：糟糕的复杂度是 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 次运算
归并排序
对于数据库，你需要理解这个 sort() 函数的工作原理。
归并排序是把问题拆分为小问题，通过解决小问题来解决初的问题（注：这种算法叫分治法，即『分而治之、各个击破』）。
为什么是归并排序？
- 你可以更改算法，以便于节省内存空间，方法是不创建新的序列而是直接修改输入序列。注：这种算法叫『原地算法』(in-place algorithm)
- 你可以更改算法，以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时，这是个很重要的技巧。注：这种算法叫『外部排序』(external sorting)。
- 你可以更改算法，以便于在 多处理器/多线程/多服务器 上运行。比如，分布式合并排序是Hadoop（那个的大数据框架）的关键组件之一。
二叉搜索树
数据库中查询的时间复杂度，是我们无法使用矩阵，转而使用二叉搜索树(BST)。
- 二叉搜索树只需 log(N) 次运算，而如果你直接使用阵列则需要 N 次运算
B+树索引
查找一个特定值这个树挺好用，但是当你需要查找两个值之间的多个元素时，就会有大的麻烦了。你的成本将是 O(N)，因为你必须查找树的每一个节点，以判断它是否处于那 2 个值之间（例如，对树使用中序遍历）。而且这个操作不是磁盘I/O有利的，因为你必须读取整个树。我们需要找到高效的范围查询方法。
- 这就是为什么引入B+树索引
如果你在数据库中增加或删除一行（从而在相关的 B+树索引里）：
- 你必须在B+树中的节点之间保持顺序，否则节点会变得一团糟，你无法从中找到想要的节点。
- 你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N)。
换句话说，B+树需要自我整理和自我平衡。谢天谢地，我们有智能删除和插入。但是这样也带来了成本：在B+树中，插入和删除操作是 O(log(N)) 复杂度。所以有些人听到过使用太多索引不是个好主意这类说法。没错，你减慢了快速插入/更新/删除表中的一个行的操作，因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者，增加索引意味着给事务管理器带来更多的工作负荷（在本文结尾我们会探讨这个管理器）。
哈希表
当你想快速查找值时，哈希表是非常有用的。而且，理解哈希表会帮助我们接下来理解一个数据库常见的联接操作，叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西（比如锁表或者缓冲池，我们在下文会研究这两个概念）
为什么不用阵列呢？
- 如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。
- 一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
- 用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间。
全局概览
我们已经了解了数据库内部的部分重要算法，现在我们需要回来看看数据库的全貌了。
数据库一般可以用如下图形来理解：
核心组件
- 进程管理器（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 manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。
- ……
查询管理器
- 查询解析器（Query parser）：用于检查查询是否合法
- 查询重写器（Query rewriter）：用于预优化查询
- 查询优化器（Query optimizer）：用于优化查询
- 查询执行器（Query executor）：用于编译和执行查询
数据管理器：
- 事务管理器（Transaction manager）：用于处理事务
- 缓存管理器（Cache manager）：数据被使用之前置于内存，或者数据写入磁盘之前置于内存
- 数据访问管理器（Data access manager）：访问磁盘中的数据
数据查询的流程
本章集中探讨数据库如何通过如下进程管理SQL查询的：
- 客户端管理器
- 查询管理器
- 数据管理器（含恢复管理器）
- 客户端管理器
客户端管理器
客户端管理器是处理客户端通信的。客户端可以是一个（网站）服务器或者一个终用户或终应用。客户端管理器通过一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式来访问数据库。客户端管理器也提供专有的数据库访问API。
当你连接到数据库时：
- 管理器首先检查你的验证信息（用户名和密码），然后检查你是否有访问数据库的授权。这些权限由DBA分配。
- 然后，管理器检查是否有空闲进程（或线程）来处理你对查询。
- 管理器还会检查数据库是否负载很重。
- 管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间，它会关闭连接并给出一个可读的错误信息。
- 然后管理器会把你的查询送给查询管理器来处理。
- 因为查询处理进程不是『不全则无』的，一旦它从查询管理器得到数据，它会把部分结果保存到一个缓冲区并且开始给你发送。
- 如果遇到问题，管理器关闭连接，向你发送可读的解释信息，然后释放资源。
查询管理器
这部分是数据库的威力所在，在这部分里，一个写得糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器。
这个多步骤操作过程如下：
- 查询首先被解析并判断是否合法
- 然后被重写，去除了无用的操作并且加入预优化部分
- 接着被优化以便提升性能，并被转换为可执行代码和数据访问计划。
- 然后计划被编译
- 后，被执行
这里我不会过多探讨后两步，因为它们不太重要。
查询解析器
每一条SQL语句都要送到解析器来检查语法，如果你的查询有错，解析器将拒绝该查询。比如，如果你写成”SLECT …” 而不是 “SELECT …”，那就没有下文了。
但这还不算完，解析器还会检查关键字是否使用正确的顺序，比如 WHERE 写在 SELECT 之前会被拒绝。
然后，解析器要分析查询中的表和字段，使用数据库元数据来检查：
- 表是否存在
- 表的字段是否存在
- 对某类型字段的 运算 是否 可能（比如，你不能将整数和字符串进行比较，你不能对一个整数使用 substring() 函数）
接着，解析器检查在查询中你是否有权限来读取（或写入）表。再强调一次：这些权限由DBA分配。
在解析过程中，SQL 查询被转换为内部表示（通常是一个树）。
如果一切正常，内部表示被送到查询重写器。
查询重写器
在这一步，我们已经有了查询的内部表示，重写器的目标是：
- 预优化查询
- 避免不必要的运算
- 帮助优化器找到合理的佳解决方案
重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：
- 视图合并：如果你在查询中使用视图，视图就会转换为它的 SQL 代码。
- 子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询
例如：
SELECT PERSON.*FROM PERSONWHERE PERSON.person_key IN(SELECT MAILS.person_keyFROM MAILSWHERE MAILS.mail LIKE 'christophe%');
