1

Linux 用の C 言語でデータベース エンジンを構築しており、インデックス作成を実装する必要があります。次のような単純な二重リンク リスト インデックスを考えてみましょう。

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

永続的なストレージの場合、次のように、この構造をディスク ブロックに変換する必要があります。

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 つのエントリを追加する必要があります。インデックスの要素が少ない場合、1 ブロックの write() はアトミックであるため、一貫して 1 ディスク ブロックに格納できます。ただし、リストが最初のブロックを完全に埋める場合は、挿入時に別のブロックを追加し、両方のブロックでポインターを更新する必要があります。しかし、問題は、アトミックに書き込めるブロックが 1 つだけであることです。それで、私の質問は、この種の構造を一貫して保存する方法ですか?

これはトランザクション ログなしで実行できますか? 操作の説明を最初に別のディスク ブロックに保存し (一種のトランザクション ログ)、インデックスのポインターを更新してから操作の説明を削除することができるため、これは 3 回の write() で行う必要があります。遅すぎる

4

1 に答える 1

0

2 つの一般的な戦略があります。

  1. トランザクション ログ
  2. コピーオンライト

後者は、常に新しいデータと変更されたデータを新しいセクターにコピーし、新しいイメージがセットアップされた後、1 つのアトミック セクター書き込みを使用してリンクすることで機能します。

残念ながら、これが二重にリンクされたリストに対してどのように機能するかわかりません。片方向リストの場合は機能します。

于 2012-08-17T11:04:16.263 に答える