B+tree の内部ノードもディスクに格納される実装はありますか? 誰かがそのような実装を認識しているか、このようにすることで本当の利点を見ているかどうか疑問に思っていますか? 通常、リーフ ノードをディスクに格納し、必要に応じて B+ ツリーを作成します。
しかし、B+tree の内部ノードの現在の状態を保存することも可能です (ポインタをそれが指すディスク ブロック番号に置き換えることにより): ディスク ブロックと同期してメモリ内の内部ノードを維持するなど、他の課題があることがわかります。ただし、B+ ツリーは nvram に実装するか、バッテリ バックアップ式のドラムまたはその他の方法で同期を維持することができます。
Linux の bcache や別の実装のように、誰かがすでにこの方法で実装しているのではないかと思っていますか?
乾杯、cforfun!
これまでに見たすべての永続的な B+Tree 実装は、純粋な「一時的な」メモリ内構造とは対照的に、両方のノード タイプをディスクに格納します。
そうしないと、インデックスを再構築するためにロードごとにすべてのデータ (外部ノード、別名「シーケンス セット」) をスキャンする必要があります。状況。
ページマネージャーがダーティページを排出するときとプログラムのシャットダウン時にのみディスクイメージを同期するシングルユーザー実装を見てきました。長い間ディスクに。これは、クラッシュ後に内部 (「インデックス」) ノードを再構築できるため、外部 (「データ」) ノードのみが完全なフォールト トレラントな永続化処理を必要とするという事実によってある程度正当化されます。このようなスキームの利点は、更新頻度がかなり高いルートに近いノードの無駄な書き込みをなくすことです。たとえば、SSD を考えてみましょう。
永続化されたメモリ内構造のディスク効率を向上させる 1 つの方法は、ログのみをディスクに永続化し、再起動のたびにログからツリー全体を再構築することです。非常に成功した Java パッケージの 1 つは、このアプローチを使用して大きな利点をもたらしています。