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

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

作るもの

RDBMSは通常、

  1. クエリプランナ:EXPLAIN相当の機能
  2. クエリエクゼキュータ + アクセスメソッド:淡々と実装。インデックス構造もここに含まれる
  3. IO(ディスクマネジャ、バッファプールマネジャ)

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

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

ディスクマネジャ + バッファプールマネジャ

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

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

B+ツリー

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

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

クエリ実行

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

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

セカンダリインデックス

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

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

関連記事