database - B+tree とスナップショット分離を使用した範囲指定クエリの実装

Question

新しい NoSQL データベース サーバー製品を開発しています。スナップショット分離を使用するクラスター化された B+ ツリーに範囲クエリを実装する方法に関する論文はありますか?

Answer 1

私はいくつかのB+ツリーの実装を書きました。範囲クエリの場合、範囲の下限を持つキーにカーソルを移動し、上限に達するまで「右に移動」します。B +リンクツリー（リーフノード間に左/右ポインターがある）により、これは非常に簡単になります。

ただし、スナップショットアイソレーションを実装したことはありません。これは、分離アルゴリズムに強く依存すると思います。シャドウページ（トランザクションごとに変更されたページのコピーを作成する）を使用する場合は、リーフノードに沿って「右に移動」する前にシャドウページが存在するかどうかを確認する必要があります。

Answer 2

「RowVersion」と呼ばれる各行に非表示の列を追加できます。行を更新するたびに、現在のトランザクション番号に更新された RowVersion を使用して、代わりに新しい行を挿入します。読み取るときは、トランザクション番号よりも低いバージョンの行を取得します。また、何らかのクリーンアップ タスクも必要になります。

行バージョンを別の場所に保存することもできます。同じ B ツリーにある必要はありません。それらをRAMまたはサーバーの再起動時に再作成される一時データベースに保持できます。