c - 如何在磁盘 block 中一致地存储索引

Question

我正在用 C 为 Linux 构建一个数据库引擎，我需要实现索引。 考虑这样一个简单的双链表索引:

struct node_t {
   void *prev;
   void *next;
   long  data;
};

对于永久存储，我必须将此结构转换为磁盘 block ，例如:

struct node_on_disk_t {
    size_t prev_disk_block;
    short  prev_disk_offset;
    size_t next_disk_block;
    short  next_disk_offset;
    long   data;
};

现在，当我插入一条记录时，也必须将一个条目添加到索引中。如果索引只有几个元素，我可以将它一致地存储在 1 个磁盘 block 上，因为 1 个 block 的 write() 是原子的。但是，如果列表完全填满了第一个 block ，则必须在插入时添加另一个 block ，并且必须在两个 block 上更新指针。但问题是，只有 1 个 block 可以原子写入。那么，我的问题是如何一致地存储这种结构？

这可以在没有事务日志的情况下完成吗？因为我可以先将操作的描述存储在另一个磁盘 block 上(某种事务日志)，更新索引的指针，然后删除操作的描述，但这必须在 3 write()s 中完成，太慢了

Answer 1

有两种常见的策略:

1. 事务日志记录
2. 写时复制

后者的工作原理是始终将新的和更改的数据复制到新的扇区，并在设置新镜像后，使用一个原子扇区写入将其链接起来。

不幸的是，我看不出这对双向链表有何作用。对于单链表，它有效。