Lec7 存储与文件结构

阅读信息

2065 字  7 分钟  本页总访问量 加载中...

概览

数据库系统可以分为两层：

1. 查询处理器（query processor）：负责SQL语句的解析、优化、生成执行计划
2. 存储管理器（storage manager）：负责真正将数据存到磁盘文件中，并将需要的数据读到内存中

在MiniSQL结构中，Record Manager、Index Manager、Catalog Manager、Buffer Manager都为存储管理模块。

Q：要解决什么核心问题？

内存无法放下所有数据，而磁盘访问过慢，因此需设计合理的存储层次结构，尽量减少磁盘访问次数。

物理存储介质

物理存储介质的分类：

1. 按可靠性分类：

2. 易失性（volatile）：断电后数据丢失，如cache、main momery

3. 非易失性（non-volatile）：断电后数据保留，如flash、disk、tape

4. 按速度分类：从快到慢依次为cache, main memory, flash, disk, tape

存储层次结构一般为：

1. 主存储（primary storage）：cache和main memory，快但易失
2. 辅助存储（secondary storage）：flash和disk，非易失、速度中等
3. 三级存储（teriary storage）：optical disk和tape，非易失但慢，适合备份归档

Flash

Flash用晶体管存储电荷，属于非易失性存储器（断电后电荷不消失，数据仍在）。

Flash的特点：

• 读很快，接近内存
• 写慢，且不能overwrite、必须擦除后再写
• 擦除更慢，必须按block擦除

Optical Disk

Optical disk利用激光反射的差异，用凹坑和平面表示0和1。

• 优点：成本低、可移除、寿命长（适合归档）
• 缺点：读写慢、容量相对较小、机械结构复杂

Tape

Tape利用磁性材料存储数据，用磁头按顺序读写。最重要特征为从头扫到目标位置，因此必须顺序访问、不能随机访问。

Disk

磁盘读写的步骤：

1. disk arm移到对应的track
2. 盘片旋转至目标sector转到read-write head下
3. 传输数据

磁盘控制器（disk controller）：负责将系统的高层读写请求转换为底层磁盘操作，并进行校验、坏扇区重映射、写后读回验证、多个磁盘的接口管理。

Q：怎么计算磁盘访问时间？

磁盘访问时间 = 寻道时间 + 旋转等待时间（+数据传输时间 + 控制信号时间）

Q：怎么优化磁盘块的访问？

1. 优化block大小：disk和memory传输数据的基本单位是block。Block太小，则每次读的数据少，需要更多IO；block太大，则读入暂时不用的数据，浪费空间。
2. 优化磁盘臂调度：典型算法为电梯算法（elevator algorithm），磁臂先朝一个方向移动并处理沿途请求，到没有请求后再反向移动。
3. 文件碎片与整理：通过碎片整理，将相关block尽量放到相邻位置。
4. 非易失写缓冲：先将写请求写到非易失存储器组成的缓冲区，再由控制器慢慢写入磁盘。这样可以较快确认数据是否已保存，不用等待磁盘真正写入。
5. 日志磁盘：Log一般顺序写，不需要频繁寻道，因此用专门的磁盘记录日志用于意外情况下数据库恢复。

Q：单个磁盘容易坏，怎么提高其可靠性？

使用RAID（redundant arrays of independent disks，独立磁盘冗余阵列）。这部分内容见。

存储访问

区分概念：

• block：disk中存储的数据单位
• page：数据库管理的数据单位（block和page有时混用）
• frame：buffer中的数据单位

CPU只能处理内存中的数据，因此需要在disk和CPU中增加内存buffer。Buffer维护表 frame-page_id，表示某个内存frame对应的是哪个disk page。

另外，当某个事务正在使用一个page时，该page不能被buffer manager替换，因此用pinned block表示不能被替换的page。更一般地，使用pin count：每次使用时pin count加一，使用完后减一，为零时表示能被替换。

Buffer hit和miss的操作同cache，略。

文件组织

数据库最终以文件形式存储数据。Database是file的集合，file是records（记录）的序列，record是fields（字段）的序列。

Record种类

固定长度记录（fixed-length records）

格式：每条记录长度相同。定位简单，容易实现。

Q：固定长度记录下，怎么删除记录？

1. 后面的记录整体前移。能保持紧凑，但移动成本高。
2. 将最后一条记录移动到删除位置。只移动一条，但破坏原有顺序。
3. 使用空闲链表（free list）：文件头记录第一个空闲记录位置，每个空闲记录内部存下一个空闲记录的位置。

Q：固定长度记录会导致什么问题？

浪费大量空间，即下面的可变长度记录解决的问题。

可变长度记录（variable-length records）

格式：用 (offset, length) 表示真实数据的起始位置和长度。另外，如果某些字段为null值则不用存完整的值，用bitmap标记null值。

场景：一个file中有多种record类型，record中的field本身变长（如varchar），存在若干次重复的field

Q：怎么表示变长记录？

1. 预留空间法（reserved space）：给每条记录预留最大长度空间；短记录剩余部分填null或end-of-record。简单，但浪费空间。
2. 指针法（pointer method）：用指针串成链表。可区分anchor block（第一块）和overflow block（其余块）。

Q：可变长度记录会导致什么问题？

删除后产生页内碎片；field更新可能导致record长度变化，但外部指针直接指向物理地址，record移动则指针失效。即下面的分槽页结构解决的问题。

分槽页结构（slotted page structure）

格式：一个page分为三部分

page头		page尾
page header \(\to\)	free space	\(\leftarrow\) record

• page header（也称slot directory）：page的总括信息，包含record总数、free space边界位置、每条record的offset和length（称为slot entry）
• free space：在page的中间，未记录信息
• record：从页尾向前增长，存储record的具体内容

外部指针存储RID，即page编号和slot编号的组合。由RID找到对应record的offset、length，再读取记录。这种“间接指针”的方式使得记录移动时只需改slot，而不用改真实数据的索引。

Q：分槽页结构下，怎么插入记录？

1. 系统检查free space是否够用
2. 如果够，在record区域分配对应空间，写入记录
3. 在page header中新增一个slot entry，记录新增record的offset、length
4. 返回RID =

Q：分槽页结构下，怎么删除记录？

1. 根据RID找到对应的page、slot
2. 根据slot找到真实record并删除
3. 标记对应slot为空，或保留tombstone
4. 可移动剩余record减少剩余空间，移动后更新对应的slot entry

Q：分槽页结构下，怎么更新记录？

更新后若变长或变短，调整其他record，并更新对应slot。

Record组织方式

堆文件（heap file）

组织方式：记录可以放在文件中任意有空间的位置。

• 优点：插入快，实现简单
• 缺点：查找时需扫描，不支持按key的顺序访问

顺序文件（sequential file）

组织方式：按照某个search key排序存储。插入时先找到正确位置；如果空间不够，则放到overflow block，并维护指针链。

• 优点：适合顺序扫描或范围查询
• 缺点：多次插入删除会破坏顺序，需定期重组

散列文件（hashing file）

组织方式：对某个属性做hash，根据hash结果决定放在哪个block。

• 优点：适合等值查询
• 缺点：不适合范围查询

聚集文件组织（clustering file organization）

组织方式：将多个相关的记录放在同一个文件甚至同一个block中。

• 优点：查询相关值时I/O更少，join更快
• 缺点：只查询某个值时读入无关数据，维护成本高

系统目录

系统目录（system catalog）也称data dictionary，存储metadata。包括关系名、属性名和属性类型、视图定义、完整性约束、用户和权限信息、统计信息、物理文件组织方式、关系的物理位置、索引信息。

列式存储

传统数据库多使用行式存储（一行记录的所有属性连续存放），而列式存储为每一列单独存放。

行式：

(id1, name1, age1, salary1)
(id2, name2, age2, salary2)

列式：

id列：id1, id2, id3, ...
name列：name1, name2, name3, ...
age列：age1, age2, age3, ...
salary列：salary1, salary2, salary3, ...

Q：列式存储有什么优点？

1. 减少I/O：如果查询只需要某几列，不用读整行。
2. 压缩效果好：同一列的数据类型相同、分布相似，更容易压缩。
3. cache友好：连续处理同一列数据，缓存命中率更高。
4. 适合向量化：现代 CPU 可以一次处理多个同类型数据。

Q：列式存储有什么缺点？

1. 重构tuple成本高：取完整一行需要从多个列文件中拼回来。
2. 删除和更新复杂：更新一行可能要修改多个列文件。

Q：行式存储和列式存储分别有什么适用场景？

• 行式存储：OLTP（事务处理系统）、点查询、高并发系统
• 列式存储：OLAP（分析型系统）、大数据分析、报表