データベースのB木インデックスとスキャンの仕組み！検索を高速化する

データベースの検索速度を決定づける要素のひとつがインデックス構造です。特にB木（B-Tree/B+Tree）は、巨大なテーブルでも効率よくデータを探せる基本構造として使われています。この記事では「データベース インデックス B木 スキャン 仕組み」というキーワードの背景にある意図を汲み取りながら、最新情報をもとに、B木インデックスがどのように作られ、どのようにスキャンされ、検索を高速化するのかを徹底解説します。エンジニア初心者から中級者まで理解を深められる内容ですので、ぜひ最後まで読み進めてください。

データベース インデックス B木 スキャン 仕組みとは何か

B木インデックスとは、データベースがテーブル内のデータを効率よく検索するためのデータ構造であり、「検索」「範囲取得」「並び替え（ORDER BY）」など多様な検索操作を高速化します。インデックスがなければ、テーブルの全行を調べるフルテーブルスキャンが必要となり、データ量が大きいと応答速度が劇的に下がります。B木インデックスは、高さが抑えられた多分岐な木構造を持ち、各ノードにはキーとポインタが含まれ、葉ノードには実際のデータまたはデータの位置情報が格納されます。最新のデータベース実装では、B+木構造を用いることが主流で、葉ノード同士がリンクされていて範囲検索を効率化する仕組みが組み込まれています。検索操作はまず根（root）から内部ノードをたどり、最終的に葉ノードに到達します。このとき、特定の値での等価検索も、範囲検索も同様の経路を通りますが、実際に読み込むページ数やI/Oの仕方が異なります。これが「B木インデックススキャンの仕組み」の核です。

B木とB+木の違い

B木は内部ノードと葉ノードの両方にデータを格納できる構造ですが、B+木は実際のデータが葉ノードのみに集中しており、内部ノードはキーとポインタだけを持ちます。この構造により、B+木は葉ノードがリンクされていて範囲スキャンが連続的に可能という特徴があります。データ読み込みのI/Oコストやキャッシュ効率で有利となります。最新の実装ではほぼB+木を用いており、等価検索・範囲検索・ソートなどにおいて強みを発揮します。

なぜインデックスが必要か：フルテーブルスキャンとの比較

もしインデックスがない状態で検索条件を指定した場合、データベースはテーブルの先頭から末尾まで全ての行を調べる必要があります。これをフルテーブルスキャンと呼び、データ量が増えるほどI/Oコスト・時間が線形に増加します。一方でB木インデックスを使うと、ページ（ディスクまたはストレージ上のブロック）を段階的にフィルタリングしながら検索し、必要なページだけを読み込むことで検索量を大幅に削減できます。実際には10万行規模でも数ページの読み込みで目的の行に到達できることもあります。

スキャン（scan）の種類：等価・範囲・ソートなど

インデックスを使ったスキャンには、等価比較（key = 値）、範囲比較（key BETWEEN 値1 AND 値2）、ソートやORDER BY降順／昇順の操作など多岐にわたる形式があります。範囲スキャンでは、葉ノード同士がリンクしているため、範囲の開始点を見つけた後は葉ノードの隣接リンクをたどって必要な範囲分を順次読み込むことが可能です。ソートやORDER BYにインデックスが適していれば、並べ替えの追加処理を減らすことができます。

データベースにおけるB木インデックススキャンの実際の構造と機能

B木インデックスの内部構造は実装するデータベースシステムによって多少異なりますが、共通する要素があります。内部ノード（internal nodes）と葉ノード（leaf nodes）、ページ構造、リンク、クラスタ化と非クラスタ化の違いなどがあり、それぞれがスキャンの性能に深く関わります。最新実装ではページサイズやフィルファクタなどのパラメータによって、読み込みページ数やI/O方式を最適化できる設計がなされています。

内部ノードと葉ノードの役割

内部ノードにはキーと子ノードへのポインタが格納され、検索過程でルートから葉ノードへの道筋を案内します。葉ノードにはインデックスキーと、テーブルの行を指すポインタまたは行データそのものが含まれます。クラスタ化インデックス（例：テーブルの物理順序がインデックス順序と一致するもの）では、葉ノードに実データが含まれることで、範囲取得やORDER BYの処理においてディスクI/Oが順次的で高速になります。非クラスタ化インデックスでは葉ノードにはキーと行の参照のみが含まれ、さらに行データの取得には追加のI/O操作が必要になることがあります。

葉ノードのリンク構造と範囲スキャン

葉ノードは隣接する葉と双方向リンクで結ばれており、これにより範囲検索が効率化されます。範囲スキャンでは、まず範囲の開始キーを探すためにルートから葉へ降り、そこから必要な範囲分だけ葉ノードを順に辿ります。このとき内部ノードを再度たどる必要がなく、葉ノードリンクだけで連続的に読み込めるためディスクシークが少なく済みます。

クラスタ化インデックスと非クラスタ化インデックスの違い

クラスタ化インデックスはテーブルの物理的なデータがインデックスキーの順序に配置されており、範囲スキャンやソート時のI/Oが順次アクセスになりやすく、効率が高いです。非クラスタ化インデックスは物理配置が独立しており、葉ノードで行データへのポインタを追う必要があるためランダムI/Oが発生することがあります。カバリングインデックス（必要な列がインデックスに含まれるもの）があれば、葉ノード参照だけで結果取得できるため追加のI/Oが不要になる場合があります。

ページサイズ・分割（page split）・フィルファクタの影響

ページサイズ（例：8KB、16KBなど）は1ページに収められるキー数を決め、木の高さやノードの幅に影響します。葉ノードが満杯になると分割が発生し、新しいページが割り当てられ、キーが上下に分散されます。分割が頻繁に起こると書き込み性能は低下しますが、逆にページをほぼ満杯にしておけば読み取り時のI/Oが減少します。フィルファクタはページ作成時にどれだけ空き領域を残すかを設定するもので、高い値は読み取り重視、低い値は書き込み重視になります。これらは最新のデータベースアーキテクチャでも重要視されるチューニング要素です。

スキャン戦略と実際の検索処理の流れ

データベースが実際にクエリを処理する際、どのようなスキャン戦略が選ばれるか、検索処理がどのように進むかを見ていきます。スキャン戦略とは、対象テーブルと条件によって「インデックススキャン」「インデックスオンリースキャン」「ビットマップインデックススキャン」などの方式を選択することです。最新ではこれらの戦略が賢く使い分けられ、クエリプランナーが統計情報を元に最適なものを決定します。

等価検索（Index Scan）の流れ

等価検索では、まず根ノードから比較演算を繰り返し、該当するキーを含む内部ノードをたどり、最終的に葉ノードに到達します。葉ノードで目的のキーが見つかれば、そこに格納された行取得用ポインタまたはデータを使って行を返します。この流れは典型的な「index lookup」であり、条件の選択性が高い（該当行が少ない）場合に非常に効率的です。読み込むページ数は木の高さに比例しますが、最新実装では多分岐構造により木の高さ自体が抑えられているため、巨大なデータでも数ページの読み込みで済むことが多いです。

範囲検索（Range Scan）の流れ

範囲検索では等価検索と同様に範囲の最初のキーを探すためにルートから葉ノードまで降ります。その後、葉ノードのリンクを使って隣の葉ノード群をたどりながら範囲内のすべてのキーを順次読み出します。この方法によって、連続的なデータアクセスが可能となり、ディスクアクセスが並列性や読み込むページ数の自然なまとまりで済むため、性能が高まります。範囲の終端が決まっていれば途中で読み取りを終了できます。

インデックスオンリースキャンとビットマップインデックススキャン

インデックスオンリースキャンは、必要なすべての列がインデックスに含まれており、テーブルの行データを参照することなしに結果が取得できる方式です。追加のI/O不要で高速です。ビットマップインデックススキャンでは、まず符合する行がどのページに存在するかをビットマップでまとめ、後に必要なページを順に読み込む方式です。指定条件の選択性が中程度の場合に有効で、ランダムアクセスを減らしつつ複数の値の検索をまとめて処理できます。

B木インデックススキャンの性能に影響する要因

単にインデックスが存在すれば検索が高速になるわけではなく、様々な要因がスキャンの速度を決めます。それにはテーブルサイズ・インデックスの種類・キー分布・キャッシュの使われ方・ページの空き具合などが含まれます。最新のデータベースはこれらを統計的に把握し、クエリプランに反映させています。

選択性（selectivity）とカーディナリティ（cardinality）

選択性とは指定条件でマッチする行の割合のことであり、この割合が低ければ等価検索が有効になります。逆に高い選択性（多くの行が該当する）であればフルテーブルスキャンやビットマップスキャンの方が効率的なことがあります。またキーの重複の度合いやデータの分布（偏りがあるかなど）も性能に大きく関わります。

キャッシュとI/O性能

内部ノードや最近使われた葉ノードなどはメモリキャッシュに保持されることが多いため、検索操作の初期段階でのディスクアクセスを回避できます。逆にキャッシュミスが多いとディスクI/Oが増え、性能が低下します。ストレージのタイプ（SSD vs HDD）、OSのIOスケジューラ、データベースのバッファプールのサイズなども影響します。

更新コストとインデックスの維持

インデックスは読み取り重視の構造ですが、書き込み（INSERT／UPDATE／DELETE）時のコストも無視できません。特にキーの更新や挿入でページ分割が頻繁に発生すると、書き込みのオーバーヘッドが増えます。また複数のインデックスを持つと、それぞれに対する維持コストがかかります。最新ではホット（HOT）最適化やバージョン管理機構などが使われ、重複バージョンの掃除や非アクティブなエントリの削除などが行われています。

パラメータ設定の重要性：fill factor やページサイズ

ページが満杯だと検索時のI/Oは少なく済みますが、分割が頻発すると書き込みが重くなります。fill factor（ページの初期充填率）を設定することで、読み書きのバランスを取ります。ページサイズを選ぶこともまた、1ページに入るキーの数、木の高さ、ディスクやキャッシュの利用特性などに影響します。最新のデータベース実装ではこれらの設定を調整できるため、負荷やワークロードに応じて最適なパラメータを選択することが推奨されます。

B木インデックスとスキャンの具体的な利用シナリオとベストプラクティス

実践的な観点から、どのような場合にインデックススキャンを使うべきか、あるいは使わない方がよいか、また運用中に注意する点について解説します。検索条件やテーブル設計からインデックスの種類とスキャン方式を意図的に選ぶことが、高い性能を引き出す鍵です。

等価検索を伴うクエリの最適設計

主キー検索やユニークキーによる検索等、行数が1〜数行で絞り込める等価検索ではインデックスが非常に有効です。これらのクエリではインデックスルックアップにかかるページ読み込み数は木の高さにほぼ一致し、データ量が増えても非常に少ないI/Oで済みます。テーブル設計でユニーク制約や主キーを適切に設定することが、等価検索パターンを意識した設計になります。

範囲検索やORDER　BYを伴うクエリの最適設計

範囲検索ではインデックスの葉ノードリンクを活かすことで効率的に処理できるため、検索条件にBETWEENや比較演算子（>・<）を使う場合、インデックスが有効です。ORDER　BYを使う場合でも、インデックスがソート順と一致していれば追加のソート処理を省けます。複合キーインデックスを使う時には、検索条件とインデックスのキー順序を一致させることが重要です。

更新の多いテーブルでのインデックス運用の注意点

頻繁なINSERT／UPDATE／DELETEでインデックスが頻繁に更新されるテーブルでは、ページ分割や競合、インデックスの断片化が発生しやすくなります。これはスキャン性能にも影響します。運用上は定期的な再構築や統計の更新、インデックスのモニタリングを行うことが望ましいです。さらに、不要なインデックスを削除することも書き込みコストを低く保つ有効な対策です。

統計情報とクエリプランナーの活用

データベースはテーブルの行数・キーの分布・重複度などの統計情報を収集し、それをもとにクエリプランナーがどのスキャン方式を使うかを決定します。等価検索・範囲検索・フルテーブルスキャンとの比較において、統計が正確でないと選択ミスが起きます。最新情報では、自動統計収集やヒストグラムの作成がより精緻になっており、プランナーの精度が向上しています。

主要なデータベースでのB木インデックススキャンの違いと実装の例

MySQL（InnoDB）、PostgreSQL、Oracleなど主要なデータベースシステムでは、B木インデックスとスキャンの仕組みに共通点がありながらも、実装や最適化の手法が異なります。これを比較することで、自分の使っているシステムに応じた最適な設計が可能になります。

MySQL InnoDBの実装特徴

MySQL InnoDBストレージエンジンでは、すべてのインデックスがB+木構造で実装されています。クラスタ化インデックスでは主キーが葉ノードに完全な行データを持ち、非クラスタ化インデックスでは主キーへの参照情報だけが葉ノードに含まれます。範囲検索時には葉ノード同士のリンクを使って連続的にアクセス可能で、検索後の行取得コストを抑えるためにカバリングインデックスを活用する設計が推奨されます。最新の実装ではインデックスページの利用状況やアクセス頻度をモニタリングする機能も備わっています。

PostgreSQLの実装特徴

PostgreSQLでは、B木（マルチ分岐の平衡木）をデフォルトのインデックス構造として採用しており、内部ノードと葉ノード、ページ構造などは非常に精密に設計されています。葉ノードにはキーデータと行識別子が入っており、クラスタ化インデックスはテーブルデータの物理順序を直接制御しません。そのため、テーブル構造とインデックス設計が検索性能に強く影響します。最新ではINDEX-ONLY SCAN / BITMAP INDEX SCANなど多様なスキャン方式が組み合わされ、クエリプランが選ばれるようになっています。

Oracleや他の商用DBの特徴

Oracleや他の商用データベースでもB木インデックスが基本で、ブランチブロックとリーフブロック、逆順インデックス、圧縮インデックスなどの機能が備わっています。インデックス全体を順に読み込む「フルインデックススキャン」が最適と判断される場合もあります。最新の実装では逆キーインデックスや昇順・降順の設定、インデックス圧縮などによりストレージ使用量やI/Oの効率を改善するものが多いです。

まとめ

データベースの検索を劇的に高速化する鍵が、B木インデックスとそのスキャン方式にあります。等価検索・範囲検索・ORDER BY・INDEX-ONLYおよびビットマップ方式など、目的に応じて使い分けることで、検索性能を最大化できます。更新操作や設定パラメータ（ページサイズ・fill factor・インデックス列の選定など）も無視できない要因です。

自分の使用するデータベースでどのスキャン方式が使われているかを把握し、統計情報とクエリプランナーの動きを理解することで、設計やチューニングがより効果的になります。インデックス構造は「作ればよい」ものではなく、「どう作り、どう使うか」が性能を左右する要素であることを理解しておくことが、実務上非常に重要です。