インデックスとB-treeとは ― データベースを速くする仕組み

WHEREで絞り込むSQLが遅いとき、まず検討するのがインデックスです。データベースのインデックスとは、列の値から、その値を持つ行の場所をすぐに引けるようにした索引です。索引が無いと、DBMSは条件に合う行を探すために、表の全ての行を順番に確認します。この確認の仕方をフルスキャンと呼びます。

B-treeという木構造の索引なら、DBMSが読み書きする単位であるページに100件入ると仮定して、1億件の表でも4ページを読むだけで目的の行に届きます。ただし、索引を付けると書き込みは遅くなり、付けても効かない列もあります。

WHERE句で行を絞り込む書き方は、SQLの基本の記事で説明しています。索引は、3層スキーマでは記憶装置への置き方を決める内部スキーマに含まれます。

B-treeインデックスは、列の値をソートして持つ、バランスの取れた木構造のインデックスです。木の一番上のページをルートページ、一番下のページをリーフページと呼びます。

ルートページには、子ページへの分かれ道を示す区切りの値が入っています。探したい値をこの区切りと比べれば、確認する必要のない子ページを早い段階で除外できます。次の図で、9件の小さな例を使って、フルスキャンとB-treeの動きを比べます。

フルスキャンは、5件目で50を見つけたあとも、ほかに50が無いかを確かめるため9件すべてを確認します。B-treeは、ルートページで40・70と比較して真ん中のリーフページだけに進み、2ページを読んで50を見つけます。左右2つのリーフページは読みません。

次の図では、先ほどと同じ9件の例で、ルートからリーフまでをたどる手順を1段ずつ確認できます。

読んだページは、ルートとリーフを合わせて2ページでした。残り2つのリーフページは、比較の対象にもなりません。

DBMSは、表もインデックスもページという単位で読み書きします。下の図は、表のページにもインデックスのページにも1ページに100件が入ると仮定して、読むページの数を行数ごとに計算したものです。フルスキャンは表の全ページを読み、B-treeはルートからリーフまで1段に1ページずつ読みます。

行数が1億件になっても、B-treeは4ページを読むだけで絞り込めます。フルスキャンは、行数に比例して読むページが増え、1億件では100万ページになります。1ページに入る件数は、行やキーの大きさで変わる仮定の値です。それでも、行数が増えても木の高さは緩やかにしか増えないという傾向は変わりません。

インデックスを作ると、検索は速くなりますが、書き込みは遅くなります。行を追加・更新・削除するたびに、DBMSは索引も合わせて更新する必要があるからです。

PostgreSQLの公式ドキュメントも、「インデックスが作成された後、システムでは、テーブルとインデックスとの間で常に同期を取っておく必要があります。これにより、データ操作の処理にオーバーヘッドが加わります」と説明しています。

MySQLのInnoDBは、表に行を挿入するとき、後の挿入や更新に備えてページの1/16を空けておこうとします。削除が進んでページの使用率が既定の50%を下回ると、隣のページとの併合を試みます。PostgreSQLの実装では、ページが一杯になるとそのページを2つに分割します。分割がルートページまで及ぶと、新しいルートページが作られ、木の高さが1段増えます。

書き込みのたびに、表の本体に加えて、作成したインデックスの数だけ索引の更新が増えます。そのため、PostgreSQLの公式ドキュメントは、めったに使われないインデックスは削除したほうがよいとしています。

WHERE句の条件に使う列や、JOINで表をつなぐ列には、インデックスがよく効きます。MySQLの公式ドキュメントも、インデックスの用途として、WHERE句に合う行を素早く見つけることと、JOINでほかの表から行を取り出すことを挙げています。文字列のLIKEでは、前方一致ならインデックスを使える場合がありますが、%で始まるパターンでは使えません。詳しくはLIKEの記事で説明しています。

条件で絞り込んだあとに残る行が少ない列ほど、効果が大きくなります。MySQLは、複数のインデックスから選べるとき、見つかる行が最も少なくなるインデックスを通常は使うと説明しています。

一方で、小さな表や、条件に合う行の割合が大きい列には、インデックスは向きません。PostgreSQLの公式ドキュメントは、10万行から1000行を選ぶ場合はインデックスの候補になると説明しています。しかし100行から1行を選ぶ場合は、その100行がおそらく1つのディスクページに収まるため、ページを順に読むほうが速いとしています。前の節の図で、100件ではどちらも1ページだったのと同じ状況です。

どの列に索引を付けるかは、データベース設計の段階のうち物理設計で決めます。

B-tree以外にも、ビットマップインデックス・ハッシュインデックス・クラスタ化インデックス・カバリングインデックス・転置インデックスといった方式があります。それぞれの仕組みの説明は省きます。

• PostgreSQL 16 日本語ドキュメント「11.1. はじめに」（インデックス保守のオーバーヘッド、使われないインデックスの削除）
• PostgreSQL 16 日本語ドキュメント「11.2. インデックスの種類」（B-treeが扱う問い合わせの種類）
• PostgreSQL 16 日本語ドキュメント「11.12. インデックス使用状況の検証」（小さな表・高い選択率にインデックスが向かない理由）
• MySQL 8.4 Reference Manual「How MySQL Uses Indexes」（WHERE句・JOIN・最も絞り込めるインデックスの優先利用）
• MySQL 8.4 Reference Manual「The Physical Structure of an InnoDB Index」（インデックスページの既定サイズ、挿入・削除時の保守）
• PostgreSQLソースコード nbtree/README（ページ分割が根まで及ぶと木の高さが増える仕組み）