【読書メモ6】詳説 データベース
はじめに
エンジニアとして正式に就職した。目指すスキル感としては
- データベース技術に特化しているが、
- Web開発が問題なくこなせる程度に広い知識・経験も持っている
エンジニアになりたい。
ということで、今回は近年のデータベース技術を詳しく解説している「詳説 データベース」を読み、DBMSの実装の詳細と、NewSQLのような新技術の内容について理解を深めていくつもり。
重要な観点として、以前に読んだ2001年の書籍である「Transactional Information Systems」からどの程度研究開発が進歩しているかという差分にも着目したい。 TISでも分散システムにおけるトランザクション管理と回復の話はなされていたが、今ではハードウェアスペックも比べ物にならないほど上がり、またデータの分散配置の重要性も跳ね上がっているので、一番注目する話題だろう。
所感
個別の事項メモ
1章 基本事項
- DBMSの設計に共通する青写真はない。コンポーネントの境界は論文上や資料には存在していても、ソースコードではパフォーマンスの最適化、エッジケースへの対応、アーキテクチャ上の決定などを理由にして分離されていないことがある
- DBMSでは通常データファイルとインデックスファイルが分けられている
- データファイルにはインデックス構成表・ヒープ構成表・ハッシュ構成表というバリアントがある
- プライマリキーに基づくインデックス(プライマリインデックス)に関連して、レコードにプライマリインデックスを介してアクセスするかどうかでトレードオフが発生する
- プライマリインデックスを参照してからレコードへアクセスする場合、
- データ書き込み時のオーバヘッドが少ない。セカンダリインデックスはプライマリキーをポインタとして保持すればよいため。
- ただし読み込み時にプライマリインデックスを経由するオーバヘッドが発生する。
- プライマリインデックスを介せず、直接ポインタでレコードアクセスする場合、これと逆の利点・欠点が発生する
- プライマリインデックスを参照してからレコードへアクセスする場合、
- ストレージエンジンに用いられるデータ構造は複数出てくるが、それらの評価項目は主に3つ
- バッファリング
- ファイルの不変性
- レコードの順序付け
2章 B木の基本
- だいたい知ってる話
- 二分探索木はディスク上のデータ構造としては使える？
- ファンアウト(ノードの子の最大数)が2しかないので更新が多いし、検索の際にたどるノード数も多いためディスク上のデータ構造としては向かない
- B木とB+木の違いは、B+木は葉ノードのキーにしか値を持たせない点
- なので、B+木では、内部ノードにあるキーと同一のキーが葉にも存在する
- 葉の分割時には内部ノードにキーを昇格するとき、コピーするのに対し、
- 内部ノードの分割時には単に移動する
- なので、B+木では、内部ノードにあるキーと同一のキーが葉にも存在する
3章 バイナリエンコーディング
- ファイルフォーマットの設計がディスク上のデータに対する操作の効率に影響する
- スロット化ページ (PostgreSQLなど多くで採用される)
- ページをポインタと実際のレコードを格納するセルの領域に分ける
- ポインタは各レコードが実際に格納されるセルを指す
- ポインタはページの先頭側から、それが指すセルはページの終端側から詰め込んでいく
- キーのソートを維持するにはポインタの方を並び替えればよいので、セルはそのままでよい
- セルを削除して生じた空き領域は、メモリ上の利用可能リストに登録し、新しくセルを挿入するときにまず利用可能リストを参照して空きがあれば入れる
- 利点
- オーバヘッドを最小に抑えながら可変長レコードを格納できる
- 削除されたレコードが使用していた領域を回収できる
- 実際の配置に関わらずページ内のレコードを参照できる
- ページをポインタと実際のレコードを格納するセルの領域に分ける
4章 B木の実装
- B木をディスク上に実装する際の諸々
- キーやレコードが大きくて1ノードの全てが1ページに収まらなかったとき、オーバーフローページを割り当てる
- プライマリページから始まる連結リストの形をとる
- プライマリキーでB木を構成する場合、新しいデータは最も右にしか挿入されないのでノード分割の必要がない
- 単に新たに右の葉を作ればよい
