データベースと秋の空・RDBMS掌握術!

第4回 RDBMSマジック、インデックス(2)
~インデックス界の帝王,B-Tree

この記事を読むのに必要な時間:およそ 2 分

戻ってB-Tree

戻ってB-Treeは,木構造で高速な検索を行う二分探索木の特徴を受け継ぎつつ,より複雑化したアルゴリズムです。ポイントとしては,

  • ノードことに可変数のキーを格納するため,ノードをたどる回数が少なくて済む
  • 記憶領域の利用効率が高く,50%以上を期待できる
  • ハードディスクのような補助記憶装置に木構造を配置するのに非常に適している

といった点があげられます。PostgreSQLでは通常のB-Treeですが,それ以外にも改良型のB+-TreeやB*-Treeというアルゴリズムを使うことがあります。これらも基本的には似たようなものと言っていいでしょう。

また,B-Treeはより複雑化した結果,データの削除が非常に困難です。もちろん完全な削除を実装しているケースもあります。しかし,実装困難以外にも理由があったりして,単に「このデータは削除した」フラグをつけてごまかすケースも多いです。これは多くの場合,B-Treeインデックスが更新や削除を繰り返すことにより,削除フラグがついているだけのインデックスが多くなってしまい,肥大化してしまうことを意味します。

このような事情から,多くの実装ではインデックスを再作成するためのコマンドを用意していたりします。

Clustered index ー⁠ーインデックスを劣化させないための一工夫

MySQLのinnodbでは,clustered index(階層化インデックス)という一見奇妙な機能が実装されています。これは

  • インデックスを「主キー」「それ以外」の2種類に階層化する
  • 主キーのインデックスには,キーと実際に格納されている場所が書かれている
  • それ以外のインデックスには,キーと主キーの値が格納されている

となっています。従って検索時に

  • 主キーのインデックスを使って検索する場合は,そのまま検索して格納されている場所を得る
  • それ以外のインデックスを使って検索する場合は,まずいったん主キーを得,主キーのインデックスを使って改めて検索する

という非常にまどろっこしいことをしなければなりません。

Clustered Index

Clustered Index

なんでわざわざこんなことをしなければいけないのか?という話になりますが,これは実は先ほどの「B-Treeインデックスはデータの削除が困難なため,肥大化が発生する」という点と組み合わせてもらえると非常にわかりやすいのです。

まず,経験的に

  • 主キーは滅多に変更されない
  • 主キー以外の値は良く変更される

と言えます。ですので,⁠主キー以外のインデックス→主キー」というインデックスはあまり更新は行われないことが期待できます。しかし,主キーのインデックスは物理位置の情報があるので,移動が発生するような追記型アーキテクチャでは頻繁に更新されます。そこでこの二つを分離ことによって,肥大化するインデックスを主キー一つに抑えられます。

また,キーに指定している値以外が更新された場合について,インデックスの肥大化を抑える方法というのもあります。例としては,ちょうどPostgreSQL 8.3 の目玉機能としてあげられている HOT (Heap Only Tuple) というものが挙げられます。そのような手法を組み合わせれば,主キーが更新されないかぎりインデックスの増加を抑えることが可能です。筆者はMySQL-innodbがそのような手法を導入しているかどうかは存じ上げませんが,おそらく導入していることでしょう。

インデックスの再構築作業というのは多くの場合長い時間のロックを伴ったりします。実際PostgreSQLではテーブル全体をロックするため気軽には出来ません。そのためこのようなインデックスの劣化を避けられるしくみは,長期間運用する上では非常に好ましいといえるでしょう。

まとめ

  • インデックスは様々な種類がありますが,ほとんどB-Treeです。
  • B-Treeはソート,範囲,一致検索に使え,ほとんどのケースをカバーします。
  • ノードの削除が難しいため,肥大化する傾向があります。肥大化しないような手法を採用したものもあります。

著者プロフィール

谷田豊盛(たにだゆたか)

国立明石工業高等専門学校卒。いったん公務員になるが,プログラミングが好きでコンピューター業界に転進。 PostgreSQLを触り出したのは6.3のころから。特にCygwinを使ったWindows環境で使っていたが,それが高じて現在ではPostgreSQLで飯を食うことに。