IX. Storage

Overview of Physical Storage Media

• Volatile Storage (易失性存储)
  • Loses data when power is switched off.
  • Examples: Cache, DRAM.
• Non-Volatile Storage (非易失性存储)
  • Data persist when power is switched off.
  • Examples: Flash Memory, Disk, Tape.

Magnetic Disks

$$\displaystyle{\text{ Access Time } = \text{ Seek Time } + \text{ Rotational Latency }}$$

• 前者是调整不同半径，后者是旋转磁盘．

• 平均寻道时间(average seek time)：$\frac{n - 1}{3}$．

• 平均故障时间(mean time to failure, MTTF)：磁盘预计无故障持续运行的时间．

• 通过 非易失性写缓存(non-volatile RAM, NVRAM) 可以加速，从而配合电梯算法减少磁盘臂的移动距离．

Storage Access

• 数据库系统中，页面(page) 和 块(block) 是基本等价的概念．

• LRU 策略(least recently used strategy)：将最近最少使用的页面移出缓存．$\Longleftrightarrow$ 对于每一个页面记录最后一次访问的时间戳，需要从 buffer 中删除时删除时间戳最早的．

• 序列洪泛问题(sequential flooding problem)：扫描表的时候会往 buffer 中写入大量只需要读取一次的页面（实际上不需要长久放在 buffer 里），从而导致性能下降．

File Organization

Fixed-Length Records

• 定长记录(fixed-length record) 的存储方法：

  • 假设每条记录（比如每个元组）的大小都是相同的．

  • 删除的时候只需要把最后一条记录覆盖到被删的记录上即可．

Variable-Length Records

• 变长记录(variable-length record) 的存储方法：

  • 从前往后存一个固定长度的，存储每条记录的 $\left( \text{offset},\text{ length} \right)$．

  • 从后往前存储记录的实际数据．

  • 使用 开槽页结构(slotted page structure)，如下图：

Column-Oriented Storage

• 列主导的存储方法(column-oriented storage)