数据库在磁盘上的存储布局HeapFile

----《大规模分布式存储系统：原理解析与架构实战》读书笔记 这篇依然是学习《大规模分布式存储系统：原理解析与架构实战》一书之外的一个话题。通过学习本书，知道了分布式键值系统，通常使用SSTable(一个无序的键值对集合容器)作为其磁盘上的布局。这不禁

这篇依然是学习《大规模分布式存储系统：原理解析与架构实战》一书之外的一个话题。通过学习本书，知道了分布式键值系统，通常使用SSTable(一个无序的键值对集合容器)作为其磁盘上的布局。这不禁让人产生联想，传统数据库使用的是什么存储布局来存储数据呢？这就是今天要探讨的主题----HeapFile.

HeapFile是什么？

基于Page的HeapFile

这种方式的HeapFile在寻找具有合适空间的半空Page时需要遍历多个页，I/O开销大。因此一般常用的是采用基于索引的HeaFile.在HeapFile中使用一部分空间来存储Page作为索引，并记录对应Page的剩余量。如下：

像上图那样，索引单独存在一个page上。数据记录存在其他page上，如果有多个索引的page，则可以表示为：

下面是Heap file自有的一些特性：

数据保存在二级存储体（disk）中：Heapfile主要被设计用来高效存储大数据量，数据量的大小只受存储体容量限制；

Heapfile可以跨越多个磁盘空间或机器：heapfile可以用大地址结构去标识多个磁盘，甚至于多个网络；

数据被组织成页；

页可以部分为空（并不要求每个page必须装满）；

页面可以被分割在某个存储体的不同的物理区域，也可以分布在不同的存储体上，甚至是不同的网络节点中。我们可以简单假设每一个page都有一个唯一的地址标识符PageAddress，并且操作系统可以根据PageAddress为我们定位该Page。

一般情况下，使用page在其所在文件中的偏移量就可以表示了。

一种简单的布局实现方案

File的布局

在实现数据在文件中的布局的时候，为了实现更简单，我先做了一个简单的约定：一个文件表示一个关系。

这意味着一个关系的记录的条数受到文件系统的限制，如果是FAT32位系统，一个文件最大只能是4G，如果是普通的etx3,单个文件则是2TB。

同样为了实现简单，采用了数组的方式来组织页。

HeapFile的组织如下：

其中N和P为文件的最开始的16(或32)个字节。即N和P实际保存的是两个long型的值。N表示文件中页的数目，P表示每页的大小。则：

Page的布局

页中可以包含多条记录。如果每天记录的长度都相同，则称为定长记录，如果每条记录的长度有不相同，则称为变长记录。定长记录可以采用数组的方式记录，但是变长记录不行。因此采用偏移量的方式来记录。page的布局如下：

从页首开始一条条记录。页尾用一个int整形记录剩余空间的偏移量，再用一个Int整形该页已存储的记录数，每一条记录在页中的偏移量和是否被删除的标记。

其中，

struct IndexRecord
{
unsigned int pos:29; <em>//记录在页内的偏移地址</em>
unsigned int isdelete:1; <em>//是否删除的标记</em>
unsigned int spanned:2;  <em>//是否跨页存储</em>
};

一个Page通常的大小为2K，4K,8K,16K等。

这里还要再提下空隙的问题，同时删除记录时直接采用标记法，但是当更新记录的时候，由于是变长记录。存在以下3种情况：

当空间紧张时，可以尝试压缩页，剔除其中的空隙。

记录的布局

定长记录的布局可以比较简单，此处不提。本节主要讨论变长记录的布局,也叫记录的序列化。

一个常见的例子为给定表Person的定义，使name可以是不超过1024个字符。Schema如下：

CREATE TABLE Person (
    name      VARCHAR(1024) NOT NULL,
    age       INTEGER NOT NULL,
    birthdate DATETIME
)

上面表的记录是变长的原因为：

变长record的序列化的关键是字段边界的界定。一种比较流行的方法是在record的首部保存字段边界的offset。

Person的record的编排方式如下：

Note：我们在首部设置4个整型去存储三个字段的四个边界offset。

上面的编排方式很自然的提供一种NULL字段的编排方式--可以标识该字段的值为NULL，如下图：

第三个offset和第四个offset指向同一个位置，那么就表明第三个字段的大小是零，即是一个NULL值。

可以看到，使用偏移量无论是Page的布局，还是记录的序列化，都是非常方便的。

根据以上介绍， 可以有以下推断：

最后我们在来看一遍关系Person的HeapFile文件的整体布局图

参考

这里有一篇关于HeapFile的翻译 关系型数据在磁盘上的存储布局

原文来自http://dblab.cs.toronto.edu/courses/443/tas/

欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏。

如果阅读本文过程中有任何问题，请联系作者，转载请注明出处！