B +ツリーとスナップショットアイソレーションによる遠隔照会の実装

Question

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

Answer 1

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

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

Answer 2

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

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