データベース技術[実践]入門 第二章

インデックスで高速アクセスを実現する

この章ではデータ検索をするためにどのような手法が考えられるか。その手法のひとつであるB+TreeのRDBMSに合わせた最適化内容などが述べられている。

データ検索のためには以下のような手法がある。メリット・デメリットは本を読んで自分で考えたものなので違っているかもしれない。

1. 線形探索を行う
   • メリット
     • 単純
   • デメリット
     • O(N)
2. データ全体を固定長として扱う
   • メリット
     • O(1)
   • デメリット
     • 空間効率が悪い
     • 拡張性に欠ける
3. インデックス構造を導入する(ハッシュ)
   • メリット
     • O(1)
   • デメリット
     • 範囲検索・ソートが行えない
4. インデックス構造を導入する(B+Tree)
   • メリット
     • O(logmN)
     • 範囲検索(前方一致)・ソートが行える
   • デメリット
     • ハッシュよりもコストが大きい

また、RDBMSではB+Treeのような手法に以下のような課題に対してそれぞれ最適化を行っている。

1. 一意性の保障
   • 一般的にRDBMSでは一意性の保障にインデックスを活用することによって実現している。
2. マルチカラムインデックス
   • 複数のデータ項目に対するインデックスのことをマルチカラムインデックスと呼び、AND条件での検索に対して有効であるということ。(AND検索に対してのみ有効というのは覚えておいたほうがいいと思った)
3. インデックスだけを読む検索
   • ある条件に合致するデータの件数を求めるクエリの場合、実際のデータの内容を読みに行く必要はないのでインデックスだけで結果を返すということ。
4. インデックスマージ
   • 複数の項目の検索を行うときはそれぞれの項目のインデックスの検索結果をマージするということ。

実データに加えてインデックスを用意するということは、当然データの変更時にはインデックスの更新コストも増加する。
それに対してRDBMSは「ディスクへのまとめ書き」「並列更新性能の向上」などの対策を実施している。

データベースたるものデータの永続化はかなり重要なテーマで、永続化の実現というのはとりもなおさずディスクへのデータの書き込みであるため。なのでディスクの特性にあわせた最適化が非常に重要だということがここまで読んだだけでもわかった。（気がする）