WEB+DB PRESSのRDBMS特集を1ページでまとめる

WEB+DBで簡単なRDBMSを作ろうという特集があったので、内容を超サクッと1ページでまとめておく。

作るもの

RDBMSは通常、

で構成する。このうち、クエリプランナは作らない。

また、簡単のため、ジョイン、トランザクション、削除なども実装しない。つまり、1テーブルを作って、データを挿入して検索出来るだけの小さなRDBMSを作る。

DBのデータはファイルに保存される。ファイルはページという単位で分割される。これは効率のため、ファイルシステムのブロックサイズの定数倍にする。今回は4KBを採用。このIOを担当する部品をディスクマネジャという。

バッファプールマネジャはディスクマネジャのIOをキャッシュする。ファイルシステムのページキャッシュに寄りかからない理由は、自分でキャッシュする方が効率的な実装が可能だから。

O(log N)で挿入と検索をするための平衡木。 B+ツリーについてはここの記事を読めばわかる。バケット溢れが起こった場合はまず同一階層で分割し、分割に用いた中央値が根方向に伝搬していく仕組み。

各ノードは、ページに格納される。ミニRDBMSの実装では、リーフに値が格納されるため、ページサイズを超えるような大きな値は保存出来ない。（筆者に確認した)

クエリ実行は木構造をなす。（実行順序をネストで表現する）クエリプランナを実装する場合、この出力がこの木構造となる。

B+ツリーを使っているため、範囲検索は、リーフ間で兄弟リンクを貼ることで効率よく実装出来る。

キーではなく値に対するインデックスは、その値からキーに対する逆引きのB+ツリーを構成する。この維持はライト時にコストを払う。ただし、これは値がユニークであることを要求する。（ユニークインデックス）

値がユニークでないならば、プライマリキーと合成することでユニークインデックスに帰着するというアイデアがある。これをノンユニークインデックスという。