database - btree はどのようにディスクに保存されますか?

Question

btree をメモリに実装する方法は知っていますが、btree をディスクに格納する方法については明確ではありません。大きな違いは次の2つだと思います。

1. メモリ ポインタとディスク アドレス間の変換については、この投稿を参照してください。
2. 新しい k/v アイテムを挿入するときにページを分割する方法は? メモリに実装するのは非常に簡単です。

ありがとう

Answer 1

それはすべて、使用する DBMS によって異なります。MS SQL Server での実装方法を知りたい場合は、以下を参照してください。

• ページ (ほとんどすべての最新の DBMS にあると思います) - SQL Server では 8Kb です。データベースファイルはページから構成されています。
• エクステント - 連続した 8 ページの論理グループ
• (S)GAM - (共有) グローバル割り当てマップ。空きエクステントと占有エクステントに関する情報を含むビットマップ。これは、データベース ファイルの最初のページの 1 つです。
• IAM - インデックス割り当てマップ。どのインデックス/ヒープがどのエクステントに格納されているかを確認できます。この情報があれば、インデックス/ヒープが格納されているファイル内の場所を取得できます。

IAM と GAM (または SGAM) を使用すると、ページを分割できます。ページの一部 (オーバーフローするはずです) をファイル上の別のページに移動するだけです。

IAM と GAM は、最初の質問に対する回答でもあります。

これらの名前のほとんどは MS SQL Server から取られていますが、他の DBMS でも非常によく似た方法で解決されると確信しています。

それが役に立てば幸い。

Answer 2

私のおすすめは、「データベースシステムの実装」という本をご覧になることです。

第2章「データストレージ」と第3章「データ要素の表現」では、この問題に関するヒントをいくつか紹介します。

第4章インデックス構造にはBtreeに関するセクションがあります

これは、このトピックに関してこれまでに見つけた最高の情報源です。