数据存储：磁盘与文件

# 数据存储：磁盘与文件 ## 1. 商业系统中的记录标识符（RIDs） 在商业数据库系统中，如 IBM DB2、Informix、Microsoft SQL Server、Oracle 8 和 Sybase ASE，通常将记录标识符（RIDs）实现为页面 ID 和槽号的组合。以 Sybase ASE 为例，其页面组织具有代表性：页面包含一个头部，随后是行数据和一个槽数组。头部包含页面标识、分配状态、页面空闲空间状态和时间戳等信息。槽数组则是槽号到页面偏移量的映射。 不过，Oracle 8 和 SQL Server 在一种特殊情况下使用逻辑记录标识符，而非页面 ID 和槽号。当表有聚簇索引时，表中的记录会使用聚簇索引的键值来标识。这样做的好处是，当记录在页面间移动时，无需重新组织二级索引。 我们可以把页面看作是槽的集合，每个槽包含一条记录。通过页面 ID 和槽号这对组合来标识记录，这就是记录标识符（RID）。虽然也可以为每条记录分配一个唯一整数作为 RID，并维护一个表来记录每个 RID 对应的页面和槽，但由于维护该表的开销较大，使用页面 ID 和槽号作为 RID 的方式更为常见。 接下来，我们将探讨在页面上管理槽的不同方法，主要考虑这些方法如何支持页面上记录的搜索、插入和删除等操作。 ## 2. 定长记录的存储 ### 2.1 定长记录的特点 如果页面上的所有记录长度相同，那么记录槽是均匀的，可以在页面内连续排列。在任何时刻，有些槽被记录占用，有些则为空。插入记录时，需要找到一个空槽并将记录放入其中。主要问题在于如何跟踪空槽以及如何定位页面上的所有记录，而不同的处理方式取决于如何处理记录的删除操作。 ### 2.2 两种存储方式 - **方式一：紧凑存储** - 这种方式将记录存储在页面的前 N 个槽中（N 为页面上的记录数量）。当删除一条记录时，将页面上的最后一条记录移动到被腾出的槽中。这种格式允许通过简单的偏移量计算来定位页面上的第 i 条记录，并且所有空槽会出现在页面的末尾。 - 然而，如果存在对被移动记录的外部引用，这种方法就不可行，因为 RID 包含槽号，槽号的改变会导致 RID 变化。 - **方式二：位图存储** - 使用一个位数组来跟踪空闲槽信息，每个槽对应一位。定位页面上的记录需要扫描位数组，找到位为 1 的槽；删除记录时，将其对应的位设置为 0。 下面是两种存储方式的对比表格： | 存储方式 | 优点 | 缺点 | | ---- | ---- | ---- | | 紧凑存储 | 可通过简单偏移量计算定位记录，空槽集中在末尾 | 存在外部引用时不可用 | | 位图存储 | 处理删除操作简单 | 需要扫描位数组定位记录 | 对于定长记录，在某些情况下，如需要对页面上的记录进行排序时，为变长记录设计的带槽页面组织方式也很有吸引力。 ## 3. 变长记录的存储 ### 3.1 变长记录的挑战 如果记录长度可变，就不能将页面划分为固定的槽集合。插入新记录时，需要找到长度恰好合适的空槽，使用过大的槽会浪费空间，而使用过小的槽则无法容纳记录。因此，插入记录时必须为其分配恰好合适的空间，删除记录时，需要移动记录以填补删除产生的空洞，确保页面上的所有空闲空间是连续的。所以，在页面上移动记录的能力非常重要。 ### 3.2 灵活的组织方式 最灵活的变长记录组织方式是为每个页面维护一个槽目录，每个槽包含记录偏移量和记录长度的对。记录偏移量是从页面数据区域起始位置到记录起始位置的字节偏移量，可看作是指向记录的“指针”。删除记录时，只需将记录偏移量设置为 -1。由于 RID 是页面号和槽号（即目录中的位置），记录移动时 RID 不会改变，只有槽中存储的记录偏移量会改变。 ### 3.3 空闲空间管理 由于页面没有预先格式化为槽，需要仔细管理新记录可用的空间。一种方法是维护一个指针（即从页面数据区域起始位置的偏移量），指示空闲空间区域的起始位置。当新记录太大无法放入剩余空闲空间时，需要移动页面上的记录，以回收之前删除记录释放的空间，确保重组后所有记录连续排列，后面跟着可用的空闲空间。 需要注意的是，删除记录的槽并不总是能从槽目录中移除，因为槽号用于标识记录，删除槽会改变后续槽的槽号，从而改变后续槽指向的记录的 RID。只有当最后一个槽指向的记录被删除时，才能移除该槽。插入记录时，应扫描槽目录，找到当前不指向任何记录的槽来存储新记录，只有当所有现有槽都指向记录时，才在槽目录中添加新槽。如果插入操作