上一篇博客: 数据库系统的数据存储方式 | Amiriox’s Storage

上次写博客是在一个多月前了, 最近比较忙, 博客只能抽空写. 精神状态也不是很好, 得想想办法 ()

数据库系统的访问方法

我们在这个系列的第一篇文章(数据库系统的基本概念 | Amiriox’s Storage)中就介绍了数据库的架构分层, 但没能真正展开.

典型关系型数据库的架构分层
查询优化(Query Planning)
算子执行(Operator Execution)
访问方法(Access Method) <-
缓冲池管理器(Buffer Pool Manager)
磁盘管理器(Disk Manager)

具体来说:

  • 磁盘管理器单纯用来和磁盘进行交互, 不过通常实现一些异步方案进行优化(Bustub 就利用了 std::promise)
  • 缓冲池在上一篇文章(数据库系统的数据存储方式 | Amiriox’s Storage)中介绍了, 为防止磁盘 I/O 成为性能瓶颈, 有计划地(一些页驱逐策略)将磁盘中的页加载到内存中作为内存中的一个页帧\(^{[*]}\)
  • 访问方法通过特定的数据结构从页中找到上层算子执行所需要的信息, 本文将详细解释这些数据结构
  • 算子是关系代数中的具体操作实现(当然, 事实上是基于可重集合, 甚至有序可重集合的特殊关系代数), 这在后面的文章中会详细介绍, 例如数据和逻辑是如何在这些算子间流动最终得出查询结果的, 算子的执行体现了程序究竟在做什么: “用逻辑塑造一个管道让数据在其中塑形”。
  • 查询优化, 面对一个已知的 SQL 语句, 预估大概的执行成本, 选择采用什么索引, 某些算子的执行顺序交换, 以形成相对更优的执行计划

页中的数据如何被解释

上一篇文章中介绍了各种数据存储模型。将各种数据模型联系到一起, 并向 Access Method 负责的就是 Record ID, 即包含了一个元组存储位置的元组唯一标识, 对列存就是对齐的列位置(详见上一篇文章).

那么, 具体来说, 这些访问方法就是用一些数据结构找这些 Record ID, 从而访问到数据库中一行又一行元组.

最简单的方法自然是全表扫描线性查找, 通过全局的 Catalog (这个目录中包含表的各种元数据) 找到表数据的第一个页面(例如, 这个表的 Page Directory, 对于 Heap File 存储), 然后由 Page Directory 中的数据找到某个页的位置(文件+偏移量), 由 Disk Manager 和 BPM 管理读进内存, 然后按照约定的页面结构(比如之前介绍过的槽页面)解析, 顺序扫描.

需要注意的是, 数据库系统的规模可能非常大(后面我们会看到, 将数据存在磁盘上除了可持久化需求, 另一个原因是内存是存不下了), 例如对一条在几亿条记录的表中查找某个 id 的记录, 线性查找除了时间复杂度问题, 还会造成大量的磁盘 I/O. 因此我们需要找到时间复杂度更优、磁盘 I/O 较少(或尽可能保证顺序磁盘 I/O)的办法来获取 Record ID.

数据结构

重复一下我们的需求: 维护一个可重复的集合, 尽可能地支持高效插入、删除、查找(尤其对于 OLAP workload)

其次, 对于查找(或者说数据库的查询), 存在单点查找、范围查找等不同情况, 而通常是具有查询的具体类型的, 所以我们可以对不同查询采取不同的数据结构。

最后, 我们还希望数据结构的磁盘 I/O 能尽可能少, 或者尽可能是顺序 I/O 而不是随机 I/O

单点查询

从复杂度上来讲, 毫无疑问是哈希表的 \(O(1)\) 查询在一众数据结构中最亮眼。Yes, but at what cost? 哈希表基本都是随机 I/O, 但这毕竟是单点查询, 相对于”在可能规模极大的数据中 O(1) 查找的优势”, 在单点查询中造成一次或几次随机磁盘 I/O 并非无法接受。(No free lunch here)

这里哈希表的键可以是主键, 或某一属性; 值可以是元组(剩余元素)本身, 或是 Record ID(常见).

静态哈希

对于键个数已知的 scenario, 可以采用静态哈希。静态哈希解决冲突的手段通常是开放定址:

  1. 探测: 线性探测/平方探测

    插入 \(k_2\) 时若 \(H(k_2) = H(k_1)\), 进而尝试其他位置(所谓”开放定址”), 对于线性探测来说可能是 \(H(k_2) + f(i), f(i) = c i, i=1,2,3,...\) 如果觉得线性探测可能造成堆积现象, 也可以采用 \(f(i)=c i^2\) 进一步避免冲突的键堆积在一起. 查找时也按相同规则找位置即可. 但要注意删除不能直接删除, 而是要 rehash 或标记墓碑(通常采用后者): 在被删除元素的位置上打上特殊标记, 让查找操作并不在此处终止而是继续向下寻找, 直到在某次新的插入操作中复用这个墓碑的位置。

  2. Cuckoo Hashing

    非常古怪的名字. 杜鹃这种生物会把自己的蛋下到别人窝里然后把别人的蛋挤走, Cuckoo Hash 也是类似的策略:
    在 \(H_1(k_2) = H_1(k_1)\) 即新插入的 \(k_2\) 和先前的 \(k_1\) 发生冲突时,

    • 先使用另一个哈希函数计算 \(H_2(k_2)\), 如果那个位置恰好空缺则插入成功
    • 如果仍然不成功(存在 \(H_2(k_0) = H_2(k_2)\)) 就只好把那里的冲突键 \(k_0\) 踢掉, 把 \(k_2\) 放进去
    • 当然, 我们决不会对还未出生的鸟宝宝坐视不管: 继续执行将被抢走位置的键 \(k_0\) 插回去的操作, 同样可能涉及到其他无辜键被踢出然后重新插入(谁还不是一只杜鹃了呢?). 由于我们有两个哈希函数 \(H_1(x)\) 和 \(H_2(x)\), 通常我们都能找到某个在 \(H_1(k_i)\) 位置的 \(k_i\) 并且其备选位置 \(H_2(k_i)\) 为空的键. 如果不存在就只能自认倒霉(这可能造成死循环, 通常需要终止操作, 扩容哈希表, 然后重新 rehash 所有元素)

    Cuckoo Hashing 的优点在于绝对的最坏 \(O(1)\) 查询复杂度 (探测法在极端数据下可能因为需要不断向下探测找下一个位置导致 O(n) 的查询复杂度), 但代价就是插入操作复杂, 同时可能触发扩容.

静态哈希仅仅适用于我们(大致)知道有多少键需要维护的情况, 否则就需要重建整个哈希表并且 rehash.

动态哈希

最令人熟知的应该是 Chained Hashing, 也就是国内常叫的拉链法(为什么你们总喜欢这么弱智的翻译? “拉链”? “主码”?). 通常的实现是, 每个 \(H(x)\) 值域对应的位置上是一个链表的表头, 每次冲突时只需要头插法(同样弱智的翻译)插在这个链表头即可. 然而, 拉链法同样可能像探测法一样造成查询的退化 (你可能会说这主要是哈希函数太烂导致多个键冲突在一起, 但是总有这种情况发生, 对吧?\(^{[*]}\)), 以下是一些优化:

  1. Extendible Hashing

    设立一些桶和桶对应的局部计数器 \(d_i\), 其意义是: 在桶 \(i\) 容纳的键值对中, 最少需要查看 \(d_i\) 个键的哈希值的二进制位才能区分开桶里的这些键值对 (例如 010 和 110 只需要 \(1\) 位区分, 而 010111 和 011111 需要至少两位 \(2\) 位才能区分)

    维护一个全局计数器 \(d\), 其意义是对当前哈希表中所有键值对的键的哈希值, 最少需要 \(d\) 个二进制位才能进行区分. 以及配套的一个长为 \(2^d\) 的目录, 这个目录记录了对一个哈希值应该去哪个桶来找 (例如, \(d=3, H(k) = 0b0110010\), 则在前三位 011 对应的目录指向的桶中查找/插入/删除这个键值对)

    一条不变量是: 局部计数器 \(d_i\) 永远小于全局计数器 \(d\). (否则目录项一定会是错的, 导致查找到的桶无法正确离散不同键的哈希值)

    对于查找操作, 计算哈希值, 取哈希值的前 \(d\) 位二进制, 通过目录中这 \(d\) 位二进制对应的目录项指针找到对应的桶, 最多查找 \(2^d\) 次就能找到(更确切来说, 只需要查找 \(2^{d_i}\) 即局部计数器即可)

    对于插入操作, 定位过程类似, 但是若插入导致桶满了需要分裂, 则存在以下情况:

    • \(d_i + 1 \leq d\): 创建新桶, 并且修改新旧两个桶的局部计数器为 \(d_i+1\), 因为超出 \(2^{d_i}\) 个(不重复的)键意味着仅靠 \(d_i\) 位无法区分这 \(\gt 2^{d_i}\) 个(不重复的)键的哈希值了. 不过此时局部计数器较小仍不需要动全局计数器
    • \(d_i + 1 \gt d\): 准确来说是 \(d_i = d\). 此时强行扩展局部计数器会导致一个目录项必须指向两个桶(这显然是不符合规则的). 所以要扩展全局计数器, 将目录从 \(2^d\) 扩展为 \(2^{d+1}\) 项, 此时两个目录项会指向同一个桶(对于未分裂的桶), 或是两个目录项分别指向分裂操作造成的两个桶, 桶分裂的过程和上面一样.

    是靠”哈希值的二进制位”对哈希表中的位置进行了一次离散化, 然后在这个离散化精度不够高的时候在(惰性地)增加精度(\(d\) 位到 \(d+1\) 位)

  2. Linear Hashing

    <TODO: 也是个很有想法的哈希, 但是解释起来有点麻烦, 先鸽一下>

范围查找

范围查找通常是基于索引的, 而提到数据库的索引就不得不提到 B+ Tree, 时间复杂度和体系结构友好的完美权衡.

从需求下手, 我们需要一个能够以优良时间复杂度维护元素有序性质的、磁盘随机 I/O 次数较少的数据结构.

那么, 链表怎么样? 有序链表维护有序性代价太高了, 插入等操作需要遍历定位(注意链表是不能二分查找的, 因为不具有 \(O(1)\) 随机访问性质).

跳表(跳跃表, SkipList) 怎么样? 跳表可以通过不同层数的节点巧妙界定范围, 并且依据随机性可以勉强维持 log 的时间复杂度, 但是跳表的节点定位几乎都是随机磁盘 I/O, 因此也否决了. 但跳表的确在数据库系统中得到了一些应用, 主要是在纯内存数据结构上(不涉及磁盘 I/O)的情境下.

因为类似的原因, 平衡树也同样被否决了(而且常规平衡树也只能做单点查询, 当然这不是主要问题, Splay, FHQ Treap, 线段树这样的数据结构也能进行区间查询, 但是依然存在随机磁盘 I/O 次数较多的问题).

那么有没有一种办法, 可以把跳表和平衡树的优势结合起来?

  1. 跳表可以通过不同层次的节点确定查找范围, 平衡树可以根据二叉查找树的节点性质和平衡树的平衡性质(防退化)以 \(O(\log n)\) 的复杂度确定查找范围; 但在这两个问题上两者的缺陷是一致的: 需要跳转太多次导致随机磁盘 I/O 太多, 那么能不能通过添加分叉数的方式降低平衡树的树高, 从而降低查找结点所需的跳转次数呢? 对于平衡树不能, 因为平衡树几乎都是基于二叉搜索树添加了一系列平衡规则, 但我们可以记着这一点, 称为 性质1.
  2. 在跳表中, 一旦达到最低层次, 就可以通过链表结点的连接指针向后遍历, 这是常规平衡树所不具备的. 我们称之为 性质2

而 B+ Tree 就是具备 性质1 和 性质2 的数据结构. 具体来说:

  • 只在叶子节点存储实际数据, 且每个节点存储多个相邻且处于同一范围的(单调的)数据, 相邻叶子节点通过 sibling pointer 连接, 形成一个链表, 用于加速范围查询.
  • 内部节点不存储实际数据, 而是发挥类似跳表上层的定位功能. 具体来说, 内部节点存储一系列单调的元素(\(e_1 < e_2 < e_3 < ...\)), 而在每两个元素间存在一个指针指向下一层的节点, 含义是这个指针指向的子树中的所有元素大小都在这两个元素之间 (例如 \(e_1\) 和 \(e_2\) 之间的指针指向的子树中所有的元素 \(e\) 都保证 \(e_1 \leq e \lt e_2\), 取等取决于具体实现). 由于每个节点能够索引到的范围变多了(对平衡树来说, 一个节点只能区分出两个范围: 大于这个节点值的子树, 和小于这个节点值的元素), 树高可以明显降低, 而在由于每个节点的元素都是单调的, 可以通过二分查找加速索引过程, 依然可以保证 log 复杂度.
  • 完美平衡, 节点平衡因子为0. 这一点保证了 log 级别的查找复杂度, 实现上是通过保证每个节点内的元素个数大于半满小于全满从而防止太多范围聚集到一个节点上而很多节点几乎为空导致退化为链的情况. (取决于具体实现, 对于叶子节点和内部节点实际上要求略有不同, 这一点后面会说)

仅仅从数据结构的定义形态上来看, B+ Tree 是简洁自然的, 然而为了保证这些性质, 可遭老罪了, Insert 和 Remove 操作真的要处理很多种 case:

  • 插入导致节点满了, 进行 split, 同时要保持上述性质
  • 删除导致节点空了, 或者小于半满(这些约束称为”不变量约束”), 需要 re-distribute 或者 merge

而这些操作需要在 B+ Tree 复杂结构的条件下, 区分叶子节点和内部节点, 还要对根节点特判, 同时数据库系统中通常还要保证并发安全… 没错, 这就是 cmu15445 的 Project #2: Database Index: 手写一个并发安全的 B+ Tree.

split, re-distribute 和 merge 操作, 以及兼顾并发安全和效率的 Latch Coupling 技术, 我会接着展开, 同时我还会介绍一些使用 cgdb 和 rr, 包括使用自己的 GTest 测试进行调试的经验. <TODO: 但因为太麻烦所以暂时先鸽着>

此外, 对于倒排索引、Trie 树等在数据库系统中广泛运用的数据结构这里不做展开.

辅助优化

<TODO: 概率数据结构(如布隆过滤器)>

下一篇博客: 数据库系统的算子执行 | Amiriox’s Storage