CMU-cs445:存储引擎

存储层次

tips：在数据库存储上尽量不要使用mmap，这会带来内存/并发等一系列问题，会成为系统瓶颈。

页式存储引擎

页
a. 数据往往存储在以页为单位的空间中，页中包含元数据/索引/表数据，有的数据库将元数据和对应的表数据存放在一起，为了保证其他页丢失的情况下本页不受影响。
b. 通常一页不会存放不同类型的数据，例如某页都是tuple，另一页全都是索引数据.
c. 每个page会被赋予一个唯一的内部标识符，系统会生成属于page的ID.
d. indirection层会吧page id映射到某个文件的某个位置（也就是记录一个相对位置，当文件整体移动后，使用相对位置+偏移量就能重新找到page）
e. 物理页和操作系统页都在4kb左右，数据库的页在512b～16kb
管理页的方式
a. Heap File Organization
b. Sequential/sorted File Organization
c. Hashing File Organization
Heap File管理方式
heap file是许多页的无序集合，有两种组织形式：链表和页目录
- 链表管理就是定义两个链表，一个数据链表表示都是存满的数据页，另一个时空闲链表，用来新写入数据。
- 页目录管理：使用一些特殊的页记录数据页page id和他的位置的映射关系，甚至可以记录页的剩余空间的大小。
页头（page header）
- page size
- checksum
- DBMS version
- transaction Visibility
- 压缩信息
页内tuple布局
- 长度固定方法：每个tuple固定长度
- slotted pages：如下图所示，为了支持可变长度的记录作出的妥协。
tuple布局
- header：Visibility info（并发控制信息），Bit Map for NULL values.header并不需要存储数据的元数据，因为他们都是按顺序记录的。
- record数据按定义时顺序写入

日志式文件布局

![](/images/db-3.png)
通过追加命令的方式记录信息，有点像redis的rdb模式
比较出名的有leveldb，基于leveldb，移除其mmap的rocksdb等。