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

----《大规模分布式存储系统:原理解析与架构实战》读书笔记

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

HeapFile是什么?

HeapFile是一种保存Page数据的数据结构,类似于链表,HeapFile也是一种无序容器。
HeapFile和SSTable其实都是具有特殊结构的文件。既然都是保存数据,为什么不直接使用文件呢?因为系统文件并不区分文件的内容。处理起来粒度大。而HeapFile和SSTable都能够提供记录级别的管理,从这一点上来说,二者的功能都是相同的,都是为系统提供更细粒度的存储管理。

基本上,Oracle,MySql,PostgreSql,SQLServer等传统数据库都使用HeapFile作为其存储布局管理。如同SSTable一样,HeapFile的结构实际很简单,但是你需要时刻知道,数据库中存储使用的是HeapFile。

我们都知道,数据库通常使用B+树作为索引,但是国内很少有人提到数据库使用的是HeapFile来管理记录的存储。国外的一些大学在“数据库系统实现”这门课上通常会让学生实现一个简单的数据库,因此有不少HeapFile的资料。

基于Page的HeapFile

采用链表形式的是HeapFile如下:
数据库在磁盘上的存储布局HeapFile
Heap file和链表结构类似的地方:

  • 支持增加(append)功能
  • 支持大规模顺序扫描
  • 不支持随机访问

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

像上图那样,索引单独存在一个page上。数据记录存在其他page上,如果有多个索引的page,则可以表示为:
数据库在磁盘上的存储布局HeapFile

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

  • 数据保存在二级存储体(disk)中:Heapfile主要被设计用来高效存储大数据量,数据量的大小只受存储体容量限制;

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

  • 数据被组织成页;

  • 页可以部分为空(并不要求每个page必须装满);

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

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

一种简单的布局实现方案

File的布局

在实现数据在文件中的布局的时候,为了实现更简单,我先做了一个简单的约定:一个文件表示一个关系
这意味着一个关系的记录的条数受到文件系统的限制,如果是FAT32位系统,一个文件最大只能是4G,如果是普通的etx3,单个文件则是2TB。

同样为了实现简单,采用了数组的方式来组织页。
HeapFile的组织如下:

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

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

  • 文件的总大小 FileSize = N * P + 2 * sizoeof(long).
  • 任意一页的页首地址 Page(k) = P * ( k - 1 ) +2 * sizeof(long) (k = 1,2,...,N)

Page的布局

页中可以包含多条记录。如果每天记录的长度都相同,则称为定长记录,如果每条记录的长度有不相同,则称为变长记录。定长记录可以采用数组的方式记录,但是变长记录不行。因此采用偏移量的方式来记录。page的布局如下:
数据库在磁盘上的存储布局HeapFile

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

  • FreeSpace表示该页空间剩余量的首地址,也是最后一条记录的尾地址+1;
  • N表示该页中已经存在的记录的条数,包括哪些被标记为删除的记录;
  • 尾部的R1,R2,..表示其对应记录在页内的偏移地址,同时还会分出1个bit位标记这条记录是否被删除。如果要支持记录跨页存储的话,还需要再分出2bit来标记其是否是跨页的记录。
    尾部的R1,R2等可以定义为如下结构体:
    struct IndexRecord
    {
    unsigned int pos:29; //记录在页内的偏移地址
    unsigned int isdelete:1; //是否删除的标记
    unsigned int spanned:2;  //是否跨页存储
    };
    
    IndexRecord总共为32bit,其中29bit表示记录的页内偏移地址 ; 1bit表示记录是否被删除 ; 2bit表示是否跨页存储,0x00表示不跨页,0x01表示跨页,记录为开始的部分,0x10表示跨页,记录为中间部分,中间部分可以有多条,0x11表示跨页,记录为结尾的部分。
    则:
  • 任意一条记录的IndexRecord首地址为 R(k) = P-(2+k)*sizeof(int); (k=1,2,..,N)
  • 计算一个页还能容纳的长度为 FreeLength = P-(2+N)*sizeof(int)
  • 判断一个页是否装满的条件为 FreeLength > 0

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

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

  1. 新记录和原记录一样长:原处更新记录即可
  2. 新纪录比原记录长:原记录标记删除,并新增一条记录,如果有索引,更新索引文件。
  3. 新纪录变原记录短:原处更新记录,无需更新索引文件,但是出现了记录的空隙。

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

记录的布局

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

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

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

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

  1. name字段是一个变长的字符串;
  2. birthdate可以为NULL;

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

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

Note:我们在首部设置4个整型去存储三个字段的四个边界offset。
上面的编排方式很自然的提供一种NULL字段的编排方式--可以标识该字段的值为NULL,如下图:

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

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

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

根据以上介绍, 可以有以下推断:

  • 记录的总长度 RecordLength = R[k] k为字段数
  • 每个字段的长度为 ColnumLength(k) = R[k] - R[k-1] , (k=1,2,3,...)
  • 判断一个字段是否为NULL ColnumLength[k] = 0 ,(k=1,2,3,...)

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

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

参考

这里有一篇关于HeapFile的翻译 关系型数据在磁盘上的存储布局
原文来自http://dblab.cs.toronto.edu/courses/443/tas/


欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏
如果阅读本文过程中有任何问题,请联系作者,转载请注明出处!


上一篇:ES 搜索结果expalain 可以类似数据库性能调优来看排序算法的选择


下一篇:BAT解密:互联网技术发展之路(2)- 业务如何驱动技术发展