はじめに

データベースを扱う仕事をしていると，パフォーマンスの問題に悩まされることは日常茶飯事です。とくに最近は，データベースに格納されるデータ量が飛躍的に増え，サーバのCPUやメモリといったハード面の増強だけでは追いつかないことも多くあります。

そのようなケースに対応するため，DBMSは性能改善のための手段を多く用意しています。その中で最もコストパフォーマンスの良い方法が，インデックス（索引）です。アプリケーションにもハード構成にも影響を与えずに実行でき，うまくいかなければすぐに削除できるという手軽さが大きな魅力で，効果はしばしば絶大です。

インデックスにはいろいろな種類があり，またDBMSによってもサポートする種類に差がありますが，本稿では最も重要な2つを取り上げます。それが，B-treeとハッシュです。インデックスには，ほかにもビットマップインデックスや関数インデックスなどのバリエーションがありますが，ほとんど使わないか，上の2つの応用で理解できるものばかりです。

そのため本稿では，とくに重要な上記2つのインデックスについて，内部ロジックを解説し，それぞれどのような利点と欠点を持つのかを明らかにしていきたいと思います。また，ハッシュの場合はインデックスに限らず，ハッシュパーティションなど一般的なハッシュの使用法についても同時に説明します。

読者対象

• 実務でインデックスを使ったことのある人，または使いたいと考えている人
• DBのパフォーマンス問題を抱えている人

稼働環境

• すべてのリレーショナルデータベース

B-tree

概要

特に一般的で重要な索引の種類は，B木（B-tree）である。すべてのアプリケーションに最適な単一の記憶構造というものが存在しないことは事実であるが，もし一つの構造が選ばれなければならないとすれば，B木の類が恐らく選択されていることはまず疑いようがない。

Christopher J. Date『データベースシステム概論⁠』⁠ 第6版／丸善

インデックスというのは，（⁠x,α）という形式の配列です。PerlやRubyをよく使う人には連想配列と言ったほうがわかりやすいでしょうか。ここで，xはキー値，αはそれに結び付く情報..実データか，あるいはそれへのポインタ..です。実際には，DBにおいてαはデータへのポインタであることが多いため，C言語的な表現を使って，キー値とポインタの配列と言っても良いでしょう。本の最後にあるインデックスも，キーとなる単語と，ページ番号（ポインタ）の連想配列です。

B-treeは，インデックスの中では一番ポピュラーで，日常業務で使うインデックスの90％はこれです。そのため，何の修飾もなしにCREATE INDEX文を実行すると，ほとんどのDBでは，暗黙にB-treeインデックスが作成されるぐらいです。

しかし誤解のないように言っておくと，B-Treeは，検索のアルゴリズムとしては飛び抜けて性能の良いものではありません。考案者の1人であるRudolf Bayer自身が「もし世界が完全に静的で，データが変化しないなら，ほかのインデックス技術でも同程度のパフォーマンスは達成できるだろう」と認めています。

長所

B-treeの長所は平均点の高さです。Dateの言葉を借りるなら，B-treeは「幅広い名手」なのです。B-treeに多角的な評価を付けると，次のように「オール4」の秀才型になります（図1⁠）⁠。

• ❶均一性（4点⁠）⁠：各キー値の間で検索速度にバラツキが少ない
• ❷持続性（4点⁠）⁠：データ量の増加に比してパフォーマンス低下が少ない
• ❸処理汎用性（4点⁠）⁠：検索／挿入／更新／削除のいずれの処理もそこそこ速い
• ❹非等値性（4点⁠）⁠：等号（=）に限らず，不等号（<，>，<=，>=）を使ってもそこそこ速い
• ❺親ソート性（4点⁠）⁠：GROUP BY，ORDER BY，COUNT/MAX/MINなどソートが必要な処理を高速化できる

B-treeがバランスよく高得点を取れる理由は，その構造を見るとわかります。今，整数値（1, 3, 4, 6, 7, 9,10）を含む列にインデックスを作成したとすると，図2のような木が作られます。

最下層のリーフ（葉）と呼ばれるノードから，実データに対するポインタが出ています。なお，実際には多くのデータベースでは，リーフにだけキー値を保持するB+tree という亜種を採用しています（Oracle，Postgre SQL，My SQLなど⁠）⁠。これは，B-treeに比べて検索をより効率的にしたアルゴリズムで，データベース以外でも，NTFSやXFSなどのファイルシステムでも利用されています。本質的な特徴はB-treeと変わらないため，以下，基本的にこのB+treeを前提に話を進めます。