[CMU15445] 03 Database Storage 1
storage hierarchy
计算机中的存储层级，如下，越下面的存储价格越低，容量越大，速度越慢，对于传统的数据库架构，我们主要关注易失介质和非易失介质那一层分界线
易失介质，通常指内存，CPU cache等，这些通常可以随机访问，也就是任意访问所需要的某一个字节，并且速度块，容量小，价格也更高，最重要的一点，当断电的时候，里面的数据就会全部丢失，不能进行持久化
非易失介质，通常指disk，ssd这些介质，这些介质速度慢，容量大，价格也更低，并且通常只支持顺序访问，每次读一条数据时，需要把该数据所在的一个block全部读到内存中，再进行随机访问，写数据也是如此
不同的介质有着不同的访问速度，通常的速度如下所示，可以看到，将1ns等同于1s后，不同介质的访问数据差了很多个数量级
disk-oriented database
典型的数据库结构为面向磁盘的数据库，总体流程如上图所示：
- 所有的数据都存在磁盘上，当想要操作数据时，就要把数据所在的该页从磁盘读到内存
- 在内存中根据执行引擎生成的查询要求，对数据进行操作
- 根据是否修改，将操作完的数据写回磁盘
Never use mmap in database
当把页从磁盘读到内存中时，你可以让操作系统来帮你管理这些内存页，也可以自己从头实现一个管理模块，mmap就是让操作系统来帮你管理，这样的好处通常是简单，但是从长远来看，它有着以下的坏处：
- Transaction Safety: 在执行事务的时候，页上的数据什么时候写回是由操作系统来决定的，如果事务到一半，操作系统就写回了部分数据，然后系统宕机了，那磁盘上的数据就会被污染
- I/O Stall：DBMS不知道哪些页再内存中，每次缺页时，线程就会提出缺页中断，操作系统就会停止执行该线程，直到I/O完成才会恢复执行
- Error Handling：每一个页都会有一个checksum来校验该页，如果内存直接由数据库管理，那么它可以在每次读取或写回时校验，但是如果是由操作系统管理，因为操作系统会对数据库隐藏调页，所以数据库并不能很容易处理这个
- Performance Issue：操作系统为了mmap需要额外的数据结构，而往往性能瓶颈就毁在这些数据结构上
总结起来就是：OS is not your friend，DBMS can always do a better work than OS
File storage
数据库在磁盘上按页存储，所有的数据都是按页存储在操作系统上，操作系统的页大小不一定和数据库页大小一致，取决于实现
更大的页可以减少系统调用的次数，减少存储页索引的数据大小，但是假如只需要读取1kb的数据，就要将一个16kb的页读入，就会造成I/O的浪费，并且硬件能保证原子写入的页大小是有限的，更大的页需要自己实现一些额外的机制
所有的页有一个页目录作为索引，根据数据内容来找到它在那一页上面
Page layout
一个page通常由header和Data部分组成，header存储一些metadata
tuple在page里面以这种slot array的形式来存储，每一个slot存储着一个tuple的偏移，以便于找到这个tuple
每一个tuple也分为header和data，header部分指示字段类型，变长字段的实际长度，该字段是否为null等信息
