Chapter 9 Data Storage Structures¶
Info
9.1 File Organization¶
数据库是一系列文件 (file) 的集合，文件是一系列记录 (record) 的集合，记录是一系列字段 (field) 的集合。我们假设每条记录的大小小于磁盘块的大小。
9.1.1 Fixed-Length Records¶
定长记录 (fixed-length record) 可以直接顺序存储，通过 \(n×(i−1)\) 得到第 \(i\) 条记录的起始地址。
定长记录的删除有以下几种方式：
- 将第 \(i\) 条记录后面的所有记录向前移动一个位置
- 将最后一条记录移动到第 \(i\) 条记录的位置
- 将第 \(i\) 条记录加入空闲链表 (free list) 中，标志已被删除，下次插入记录时优先插入空闲链表
9.1.2 Variable-Length Records¶
变长记录 (variable-length record) 可能因为以下几种情况产生：
- 在一个文件中存储多种记录
- 记录中有可变长度的字段
- 记录中有可重复的字段
一种可行的存储方式是，先放上每个变长字段的偏移量和长度，再放上定长字段，然后放上空位图 (null bitmap) 和变长字段。空位图的每一位对应一个字段，表示该字段是否为空。
解释一下上图
Instructor (id，name, dept_name, salary) 元组的值为 (10101, Srinivasan, Comp.Sci., 65000) ，由于这四个值均不是 null, 所以 bitmap 为 0000，如果 salary 字段为 null, 那么 bitmap 为 0001
然后我们可以在一个块中使用分槽页结构 (slotted-page structure) 来存储变长记录。分槽页结构将记录数量（number of record entries）、空闲空间的尾部位置（end of free space in the block）、每个记录的长度和起始地址（location and size of each record）存储在页的头部，然后将记录存储在页的尾部。
Records can be moved around within a page to keep them contiguous with no empty space between them; entry in the header must be updated.
Record pointers should not point directly to record — instead they should point to the entry for the record in header. 间接寻址
9.2 Organization of Records in Files¶
记录在文件中有以下几种组织方式：
- Heap: 记录可以放在文件中的任何地方
- Sequential: 根据记录的搜索键的值，将记录按顺序存储
- Multi-table clustering: 将多个表的记录存储在同一个文件中
- B+-tree: 有序存储，即使有插入和删除操作
- Hashing: 根据搜索键的哈希值，将记录放在文件的某个块中
9.2.1 Heap File Organization¶
堆文件组织 (Heap File Organization) 是最简单的文件组织方式，记录在文件中的顺序是任意的，记录通常分配后就不再移动。堆文件组织的优点是插入和删除记录的代价较低，缺点是查找记录的代价较高。
为了更快找到空闲空间，可以使用 free-space map。
free-space map
Array with 1 entry per block. Each entry is a few bits to a byte, and records fraction of block that is free.
In example below, 3 bits per block, value divided by 8 indicates
Can have second-level free-space map 可以增加一级，记录每四个 entry 中空闲最多的部分
In example above, each entry stores maximum from 4 entries of first-level free-space map
9.2.2 Sequential File Organization¶
顺序文件组织 (Sequential File Organization) 是将记录按照某个字段 (search-key) 的值排序后存储。这样可以加快查找记录的速度，但插入和删除记录的代价较高。
删除记录时可以使用指针链 (pointer chains)。插入记录时，如果有空闲空间则插入，否则插入到溢出块 (overflow block)。在任一情况下，都需要更新指针链，并且需要定期重新组织文件以恢复顺序。
9.2.3 Multi-table Clustering File Organization¶
多表聚簇文件组织 (Multitable Clustering File Organization) 是将多个表存储在同一个文件之中，会导致文件中出现变长记录。这样可以加快多张表连接操作的速度，但对单张表的操作速度会变慢。
9.2.4 Table Partitioning¶
表分区 (Table Partitioning) 是将一个关系中的记录分成多份，分别存储在不同的文件中，比如将 2018 年的记录放一个地方，2019 年的放另一个地方。这样可以减少一些操作的代价，比如空闲空间管理，还可以将不同的分区存储在不同的存储设备上，比如将今年的记录放在 SSD 上，提高操作速度。
9.3 Data Dictionary Storage¶
The Data dictionary (also called system catalog) stores meta data; that is, data about data, such as
Information about relations
- names of relations
- names, types and lengths of attributes of each relation
- names and definitions of views
- integrity constraints
User and accounting information, including passwords
Statistical and descriptive data
- number of tuples in each relation
Physical file organization information
- How relation is stored (sequential/hash/…)
- Physical location of relation
Information about indices
9.4 Storage Access & Buffer Manager¶
块是存储分配和数据传输的基本单位。在数据库系统中，数据通常被分割成固定大小的块进行处理。
数据库系统的目标之一是尽量减少磁盘与内存之间的块传输次数。通过将尽可能多的块保留在主内存中，可以减少对磁盘的访问次数，从而提高数据访问效率。
缓冲区（Buffer）：缓冲区是主内存的一部分，用于存储磁盘块的副本。这样可以在需要时快速访问这些数据，而不需要再次从磁盘读取。
缓冲管理器（Buffer Manager）：缓冲管理器是一个子系统，负责在主内存中分配缓冲空间。它管理缓冲区中的数据，并决定何时将数据从磁盘加载到缓冲区或从缓冲区写回到磁盘。
当需要用到磁盘中的一个块时，缓冲区管理器会做出以下操作：
- 如果块已经在缓冲区中，缓冲区管理器会直接返回块在主存中的地址
- 如果块不在缓冲区中，缓冲区管理器会先为块分配缓冲区空间，然后从磁盘读取块到缓冲区中
- 如果需要，缓冲区管理器会替换掉其他块，为新块腾出空间
- 如果被替换的块被修改过，那么需要先将其写回磁盘
固定块（Pinned block）：固定块是指不允许被写回磁盘的内存块。
- 在从块中读取或写入数据之前，需要执行“Pin”操作。
- 当读取或写入操作完成后，执行“Unpin”操作。
- 可以同时进行多个并发的Pin/Unpin操作。
每个缓冲块都有一个Pin计数，只有当Pin计数为0时，该缓冲块才能被驱逐出内存。
共享锁和独占锁（Shared and exclusive locks on buffer）：
-
共享锁（Shared lock）：读者获取共享锁，允许多个进程同时读取同一块数据。
-
独占锁（Exclusive lock）：更新块数据需要独占锁，确保在同一时间只有一个进程可以修改数据。
缓存替换策略有以下几种：
- 最近最少使用 (Least Recently Used, LRU)：替换最近最少使用的块。对于某些重复扫描数据的访问模式，LRU 可能不是一个好的策略
- 立即丢弃 (Toss Immediate)：当一个块的最后一个元组被处理完后，立即释放该块的空间
- 最近最常使用 (Most Recently Used, MRU)：系统会锁定当前正在处理的块，当该块的最后一个元组被处理完后，解锁该块，使其成为最近最常使用的块
- 时钟 (Clock)：维护一个环形链表，每个块有一个位 (reference_bit) 表示是否被访问过，1 表示被访问过，0 表示未被访问过。当需要替换块时，从当前位置开始，遇到被访问过的块就将其 reference_bit 设为 0，直到找到一个未被访问过的块为止。这是 LRU 策略的近似，实现上更加简单
时钟维护方式的介绍
数据库系统可以利用用户查询中的信息来预测未来的数据访问模式，提供更准确的缓冲替换建议，从而优化缓冲区管理。
9.5 Columnar Representation¶
列存储 (Column-Oriented Storage) 是将关系的每个属性单独存储的方式。列存储的优点有：
- 如果只有一部分属性被访问，可以减少 I/O 次数
- 可以提高 CPU 缓存性能
- 可以提高压缩效率
- 可以在现代 CPU 架构上实现向量处理
列存储的缺点有：
- 从列存储中重建元组的代价较高
- 元组的删除和更新代价较高
- 解压缩代价较高
列存储在决策支持系统中【需要对某个属性进行分析】比行存储更有效，而在事务处理中，传统的行存储更受欢迎。一些数据库支持同时使用两种存储方式，称为混合行列存储 (Hybrid Row/Column Stores)。
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！