DB04 Storage

开头讲了一些硬件小常识

一个有意思的表达：

strawman idea: 翻译过来大概是“抛砖引玉”或者“初步的想法”

Storage Hierarchy

简单来说，数据库的数据是这么存的：

• 一个数据库的数据划分存在许多文件里
• 一个文件里有许多 block/page
• 一个 block 里有许多 tuple

为了实现的方便，书上又做了一些假设：

• tuple 不会跨 block 储存
• block 不会跨文件储存

Tuple

最简单的实现就是照猫画虎地序列化一个 C struct

需要注意：

• tuple 内部的值可以不定长
• tuple 可以有 null value

解法也很简单，只需要加一个 tuple header 来存各个 attribute 的信息就行。通常这个 header 是定长的

Block

实际上要处理两个问题：

1. 怎么访问有用的数据（比如遍历 block 内的所有 tuple）
2. 怎么管理空闲的位置（比如找到任意一个空闲位置）

解法也很简单：

1. 用数据结构组织已分配的位置（链表/数组/...）
2. 用数据结构组织未分配的位置（链表/树/...）

因为插入和删除的位置可以是任意的，所以用数组就会很呆。如果做过 oslab 就会想到加 header 各种挤 metadata 的空间

fixed-length

这时候 fixed-length tuple 的假设就非常好了，回想 slab-page + bit flag 的设计，这里对应就是 block-tuple + bit flag

variable-length

最简单的办法就是像 slab 一样把 block 分类，每类只装大小为 4B 8B 16B 32B... 的 tuple（大小不足的向上取整），这样就变成 fixed-length 的问题了

书上还列举了很多比较具体的做法，都不是很难

File

和 block 管理是类似的，不同之处在于一些假设

Unordered

即 tuple 的顺序无所谓，每个 block 都是同等地位的。这个和内存分配是一样的

Ordered

要求 tuple 之间按照某个 key 排序。由于目前的架构是 tuple-block-file 三层的，这实际上提出了两个要求：

1. block 内部的 tuple 要(逻辑上)有序
2. file 内部的 block 要(逻辑上)有序

解决办法：

1. 如果用数组就可以直接移动位置排序，如果用链表就可以操作引用来排序。总之是排个序
2. 数组可以定时合并，链表可以横跨 block 排序

如果比我聪明的话应该马上就能想到用 B 树这样的数据结构来维护 树-结点-数据 这样的三层结构了。

Tricks

• prejoin：意思是把某些实际上相关的表提前 join 在一起
• partitioning：意思是把某些表划分成子表，这些子表内部满足一些性质(比如有序)，以此利用查询时的局部性