ディスク上の btree のアーキテクチャを最終的に理解するのに最も近いのは、これです。
シンプルでとても読みやすく、理解しやすいです。しかし、私はまだ混乱しています。メモリ内のデータ構造がまったくないようです。何か不足していますか？これを btree にする理由は何ですか? 子ノードのキーを「指す」だけの long の配列ですか? それは効率的ですか？それは、ほとんどのデータベースとファイルシステムが設計されている方法ですか?
メモリ内のディスク btree (または他のデータ構造) に実装する方法はありますか? 各ノードには、ファイル オフセットまたは何かが含まれていますか?
通常、ノード ポインターはアドレスとしてディスクに格納されます (たとえば、long 整数を使用)。
一般に、実装は物理アドレスまたは論理アドレスのいずれかを使用することを選択します。
物理アドレッシングは高速です (解決メカニズムが必要ないため)。ただし、論理アドレッシングを使用すると、ポインターを書き換えなくてもノードを再編成できます。この方法でノードを再編成できる機能は、適切なクラスタリング、スペースの利用、さらには低レベルのデータ分散を実装するための基礎として使用できます。
一部の実装では、各アドレスがセグメント (ブロブ) を (動的に) 参照する論理アドレスとそのセグメント内の物理アドレスで構成されるように、論理アドレス指定と物理アドレス指定の組み合わせを使用します。
ノード アドレスはディスク ベースであるため、メモリ内ポインタに直接変換できないことに注意してください。
場合によっては、データをメモリにロードするときにディスク ベースのポインタをメモリ ポインタに変換する (そして、書き込み時にディスク ベースのポインタに戻す) と便利です。
この変換は、ポインター スウィズリングと呼ばれることもあり、さまざまな方法で実装できます。基本的な考え方は、スワップされたメモリ内ポインタによってアドレス指定されたデータは、ポインタがナビゲート/トラバースされる前にメモリにロードされないということです。
これに対する一般的なアプローチは、論理インメモリ アドレス指定スキームを使用するか、メモリ マップ ファイルを使用することです。メモリー・マップ・ファイルは、メモリー・ページがアクセスされる前にメモリーにロードされない仮想メモリー・アドレッシングを使用します。仮想メモリにマップされたファイルは、OS によって提供されます。このアプローチは、メモリにマップされていないメモリ ページ上のデータにアクセスするとページ フォールト割り込みが発生するため、ページ フォールトアドレッシングと呼ばれることがあります。