Goals of the DBMS

  • Allow the DBMS to manage databases that exceed the amount of memory available
  • Reading/writing to disk is expensive, so it must be managed carefully

DBMS总是希望自己来管理所有东西,而不是依靠操作系统

File Storage

  • 最简单的形式,一张表存储一个文件。但是也有多个关联的表存在一个文件的实现。
  • 操作系统对于db的文件内容是不关心。

每个file由多个page组成,有多种不同的方式来存储,

  • Heap File
  • Sequential File
  • Hashing File
  • Log-Structured File

Heap File

page在文件是无序的可以任意放,一般有两种方式组织

  • Linker List:用两个链表,data list和free list。这种方式在获取某个page的时候用时较长,需要遍历链表。
  • Page Directory:用一个特殊的page,来存所有page的位置。一般采用这种。

Sequential File

所有Tuple是按照某个特定的键(比如主键)排序存放的。在根据特殊键操作表的时候性能会Heap形式要好

Log-Structred

不存储tuple,只存储log(即insert,delete,update操作)。当查找的时候,反向搜索,recreate一个tuple。插入快,读慢。一般会考虑额外建立索引来维护log,并定期压缩。

Database Page

  • 单个文件分成多个page,每个page的大小是固定大小的

page的存储格式是多样的。为了支持变长的Tuple,一般的存储格式为slotted-page structure如下图。

当中间的Tuple被删除的时候,前面的Tuple需要往后移来对齐。这个移动的性能消耗不是太高,因为一般page大小也就4k。若Tuple过大,超过一个page的大小,一般会考虑采用一个额外的overflow page来保存。

Tuple layout

tuple才是真实的一条记录,即一串二进制序列,由database负责解释。分为两块。

  • header:metadata,每个属性的位置和长度,bitmap来快速发现null属性
  • data

目前普遍是按行存的做法,某些情况不是很好,比如应用只需要一行的其中一个数据,但db会将整行都读入,浪费io带宽。也有一些按列存的数据库。比如单个page只存某个属性的数据。

Different type of the DBMS in different workloads

  • OLTP: On-line transaction processing 适合简单增删改操作,事务短,操作快的类型
  • OLAP: On-line analyitical processing 适合复杂的分析操作,需要运行较长时间。

Buffer pool

类似虚拟内存。让database可以管理超出内存大小的数据。也就在内存维护cache,以page为单位,来换入换出。

  • 脏页换出需要写入磁盘
  • pin counter:当有线程在使用这个页的时候,不能换出。

优化

  • 多个buffer pool,减少锁竞争
  • 根据query plan,进行预读取。
  • cursor共享。两个不同query,但是可能读取的东西是相同,可以依附于同一个cursor来读,更好利用缓存。

Reference

  • cmu 15445
  • Database System Concepts 6th Edition