メインコンテンツへスキップ
見出し画像

インデックス(索引)完全攻略 | B-tree・ハッシュ・ビットマップ etc の違いと使い分け

    はじめに

    データベースのインデックス(索引)は、SQLの検索性能を大きく左右する重要な仕組みです。しかし、次のような疑問を持つ方も多いのではないでしょうか。

    • B-treeインデックスとハッシュインデックスは何が違う?

    • カーディナリティが高い列に索引を作るべき?

    • 複合インデックスは列の順序によって何が変わる?

    • ビットマップインデックスはどんなシステムに適している?

    • インデックスを作ったのにSQLが速くならないのはなぜ?

    特にIPAの基本情報技術者試験・応用情報技術者試験では、データベースの基本構造や検索性能に関する知識が求められます。

    実際、令和6年度秋期の応用情報技術者試験・午後のデータベース問題では、B-treeインデックスの特徴、カーディナリティ、検索に適した索引列の選定が問われています。

    この記事では、代表的なインデックスの仕組みを図解で整理したうえで、ECサイト、金融システム、データ分析基盤などの具体例を使って、適切な索引の選び方を解説します。特定のデータベース製品に依存せず、RDBMSに共通する考え方を中心に紹介します。


    1. そもそもインデックス(索引)とは?

    インデックスとは、テーブル内の目的のデータを効率よく見つけるための検索用データ構造です。

    身近な例では、辞書の索引が挙げられます。辞書の中から「データベース」という言葉を探す際、最初のページからすべて読み進めることはありません。五十音順の見出しを利用して目的のページを探します。データベースの索引も、基本的には同じ考え方です。

    インデックスがない場合:フルテーブルスキャン

    例えば、100万件の顧客情報が登録されているテーブルから、特定の顧客を検索するとします。

    SELECT *
    FROM customers
    WHERE customer_id = 12345;

    適切な索引が利用できない場合、DBMSはテーブルを広く読み取り、条件に一致する行を探す必要があります。このような検索方式をフルテーブルスキャン(全表走査)と呼びます。

    インデックスがある場合:インデックススキャン

    customer_id に適切な索引があれば、索引を使って対象行を絞り込み、必要なデータを取得できます。ただし、索引を利用しても、テーブル本体の行にアクセスする処理が必要になる場合があります。

    また、索引が存在していても、DBMSがフルテーブルスキャンの方が効率的だと判断することがあります。つまり、インデックスは「作れば必ず速くなる」というものではありません。


    2. 代表的なインデックスの種類

    まずは、代表的な索引の種類と特徴を整理しましょう。

    主要な索引構造の比較

    画像

    ① B-treeインデックス:最も基本的な索引

    B-treeは、木構造を使って検索対象を段階的に絞り込む索引です。RDBMSでは、葉ノード同士を順序付きでたどりやすいB+tree系の実装も広く利用されています。

    特徴

    • 等値検索(=)に対応

    • 範囲検索(BETWEEN、<、>など)に対応

    • 並べ替え(ORDER BY)にも利用できる

    • バランスの取れた木構造によって効率的な検索が可能

    例えば、次のSQLに適しています。

    SELECT *
    FROM products
    WHERE price BETWEEN 3000 AND 5000;

    索引のキーが価格順に管理されていれば、3000円付近を探し、その後は5000円までの範囲を順番に読み進められます。

    検索計算量
    平衡木の探索経路の長さは、代表的には次のオーダーで表されます。

    O(log⁡N)O(\log N)

    ただし、これは主に索引をたどる探索部分の計算量です。検索結果が大量にある場合は、その件数に応じた読み取りコストも発生します。

    ② ハッシュインデックス:等値検索に特化

    ハッシュインデックスは、キー値からハッシュ値を計算し、対応する格納位置を探す方式です。

    例えば、

    SELECT *
    FROM users
    WHERE user_id = 12345;

    のような完全一致検索に適しています。

    一方、ハッシュ値には元データの大小関係が保存されないため、通常のハッシュ索引は範囲検索や並べ替えには適しません。

    特徴

    • 完全一致検索に適する

    • 一般的に範囲検索には利用できない

    • キーの順序に基づく並べ替えには利用できない

    • ハッシュ衝突や実装方式によって性能が変化する

    なお、ハッシュインデックスが常にB-treeより速いわけではありません。

    ③ ビットマップインデックス:少種類の値を組み合わせる検索

    ビットマップインデックスは、各値に対応する行を0と1のビット列で管理する索引です。

    例えば、商品の状態が「販売中」「販売停止」「売切れ」の3種類しかない場合を考えます。販売中の商品を1、それ以外を0で表現すれば、次のように管理できます。

    行番号       1  2  3  4  5  6
    販売中       1  0  1  1  0  1
    関東エリア   1  1  0  1  0  0
    --------------------------------
    AND演算      1  0  0  1  0  0

    「販売中」かつ「関東エリア」の行は、ビット列のAND演算によって1行目と4行目だと判定できます。

    特徴

    • 値の種類が少ない列と相性がよい

    • 複数条件のAND・OR演算に適する

    • データ分析・DWHなどで利用される

    • 更新が頻繁なOLTPシステムには不向きな実装がある

    ただし、すべてのRDBMSが独立したビットマップインデックスを提供するわけではありません。

    ④ 転置索引(インバーテッドインデックス):全文検索向け

    転置索引は、検索語から、その語を含む文書や行を探せるようにする仕組みです。

    例えば次のようなデータがあるとします。

    記事1:SQLの基礎を学ぶ
    記事2:SQLの性能改善
    記事3:DB設計の基礎

    索引は概念的に以下のようになります。

    SQL       → 記事1、記事2
    基礎      → 記事1、記事3
    性能改善  → 記事2

    文章そのものを最初から順番に探す必要がなくなるため、検索語を使った全文検索に適しています。

    用途例

    • ニュースサイトの記事検索

    • ECサイトの商品説明検索

    • FAQ・ナレッジ検索

    • 大量の文書データの検索

    なお、全文検索のためのトークン化、言語処理、検索構文は製品ごとに異なります。

    ⑤ 空間インデックス:地図や位置情報の検索

    空間インデックスは、座標、領域、距離などを使った検索の効率化に利用されます。

    代表的な構造としてR-tree系などがあります。例えば、地図アプリで「指定地点の近くにある店舗」を探す場合です。単純なB-treeでは、緯度・経度の二次元的な位置関係を扱いにくいことがあります。空間インデックスでは、地点や領域の空間的なまとまりを利用して検索対象を絞り込みます。

    用途例

    • 地図アプリ

    • 不動産の物件検索

    • 配送・物流の拠点検索

    • GIS(地理情報システム)

    空間検索の演算子や距離計算への対応は、DBMSによって異なります。


    3. 索引の設計方法:単一・複合・カバリング

    ここまで説明したB-treeやハッシュは、主に内部のデータ構造の違いです。

    一方、単一列索引、複合索引、ユニーク索引、カバリングインデックスなどは、索引の列構成や役割による分類です。両者は区別して理解しましょう。

    ① 単一列インデックス

    1つの列を対象にする索引です。

    CREATE INDEX idx_customers_email
    ON customers (email);

    メールアドレスで顧客を検索する処理などに適しています。

    ② 複合インデックス

    複数の列を組み合わせる索引です。

    CREATE INDEX idx_orders_customer_date
    ON orders (customer_id, ordered_at);

    例えば、特定の顧客の注文履歴を日付順に取得する処理に適しています。

    重要なのは列の順序です。

    複合B-tree索引 (customer_id, ordered_at) は、まず顧客ID、次に注文日時という順序で管理されます。そのため、一般には先頭列を条件に含む検索で効率よく利用できます。

    逆に、ordered_at だけを条件にした検索では、その索引を効率よく使えないことがあります。ただし、一部のDBMSにはスキップスキャンなどの最適化もあります。

    ③ カバリングインデックス

    検索に必要な列を索引内に保持し、テーブル本体へのアクセスを減らすための設計です。

    例えば、

    SELECT customer_id, ordered_at
    FROM orders
    WHERE customer_id = 12345;

    であれば、(customer_id, ordered_at) の索引だけで必要な値を取得できる可能性があります。ただし、索引だけで処理を完結できるかは、DBMSの実装やトランザクションの可視性確認などにも依存します。

    ④ ユニークインデックス

    同じキー値の重複を防止する索引です。

    例えば会員番号や注文番号など、重複を許可しない列に利用します。

    CREATE UNIQUE INDEX idx_users_member_no
    ON users (member_no);

    NULLの扱いを含め、一意性制約と索引の実装にはDBMS間の違いがあります。


    4. 【実践】業種・システム別に考える索引設計7選

    ここからは、実際の業務システムを想定して、適切な索引を考えてみましょう。

    ケース① ECサイト:注文履歴の検索

    システム特性

    • 注文テーブルに数百万件以上のデータ

    • ユーザーごとに注文履歴を表示

    • 最新の注文から順に表示

    • 注文データの追加は頻繁に発生

    SQL例

    SELECT order_id, ordered_at, total_amount
    FROM orders
    WHERE customer_id = 12345
    ORDER BY ordered_at DESC;

    推奨:B-tree系の複合インデックス

    CREATE INDEX idx_orders_customer_date
    ON orders (customer_id, ordered_at);

    顧客IDで対象行を絞り込み、注文日時の順序を利用できます。ただし、降順検索への対応は索引の並び順やDBMSの実装によります。必要に応じて降順索引も検討します。

    ケース② 金融システム:取引IDによる照会

    システム特性

    • 取引件数が非常に多い

    • 特定の取引IDを使った照会が頻繁

    • 更新処理の性能も重要

    • 検索対象は通常1件

    SQL例

    SELECT *
    FROM transactions
    WHERE transaction_id = 987654;

    推奨:取引IDの一意索引(一般的にはB-tree系)

    主キーなどの一意索引を利用するのが基本です。ハッシュ方式も等値検索には適しますが、ハッシュ索引を明示的に採用できるか、また有利になるかは製品と運用条件次第です。

    ケース③ 小売業のデータ分析:属性を組み合わせた集計

    システム特性

    • 数千万件規模の販売・顧客データ

    • 日々の更新よりも分析処理が中心

    • 地域や会員ランクなどで絞り込む

    • 複数条件を組み合わせた分析が多い

    SQL例

    SELECT COUNT(*)
    FROM customers
    WHERE region = 'KANTO'
      AND member_rank = 'GOLD';

    推奨候補:ビットマップインデックス

    地域や会員ランクのビット列を組み合わせることで、対象行を効率よく絞り込める可能性があります。ただし、ビットマップ索引に対応していない製品では、B-tree系の複合索引や別の分析用データ構造を検討します。

    ケース④ 製造業・IoT:センサーデータの期間検索

    システム特性

    • センサーから継続的にデータを収集

    • 時系列データが大量に蓄積

    • 設備単位・期間単位で検索

    • 新規データの追加が多い

    SQL例

    SELECT measured_at, temperature
    FROM sensor_logs
    WHERE device_id = 100
      AND measured_at >= '2026-10-01'
      AND measured_at <  '2026-11-01';

    推奨:B-tree系の複合インデックス

    CREATE INDEX idx_sensor_device_time
    ON sensor_logs (device_id, measured_at);

    設備IDによる等値検索と日時による範囲検索を組み合わせられます。また、ログの物理的な格納順と日時に強い相関がある非常に大きなテーブルでは、BRINのようなブロック範囲型索引も候補になります。BRINは一部のDBMSが提供する方式で、すべてのRDBMSに共通する機能ではありません。

    ケース⑤ ニュースサイト:キーワード検索

    システム特性

    • 大量の文章データ

    • 記事タイトルと本文を検索

    • 複数キーワードで検索する

    • キーワードを含む記事を一覧表示

    検索条件の例

    SELECT article_id, title
    FROM articles
    WHERE body LIKE '%database%';

    推奨:全文検索向けの転置索引

    先頭にワイルドカードを置いた部分一致検索は、一般的なB-tree索引では効率化しにくい条件です。本文を単語などに分解して索引化する全文検索機能を利用する方が適しています。

    ケース⑥ 不動産サービス:地図上の物件検索

    システム特性

    • 物件に緯度・経度情報がある

    • 指定した地点の周辺物件を検索

    • 地図表示やエリア検索が頻繁

    • 地理的な距離や領域が重要

    推奨:空間インデックス

    R-tree系などの空間索引を利用すれば、領域の重なりや位置関係に基づいて、検索候補を効率的に絞り込めます。単純な数値の大小だけでなく、空間的な位置関係を扱える点が特徴です。

    ケース⑦ 業務システム:未処理データだけを抽出

    システム特性

    • 処理済みデータが大部分を占める

    • 未処理データはごく少数

    • バッチ処理で未処理データを定期取得

    • 更新が頻繁に発生

    SQL例

    SELECT *
    FROM jobs
    WHERE status = 'PENDING';

    推奨:B-tree系索引、または部分インデックス

    単純なB-treeでも、未処理データが十分に少なければ効果が期待できます。さらに、部分インデックスに対応しているDBMSでは、未処理データだけを索引に登録する方法もあります。

    例えばPostgreSQLでは次のように定義できます。

    CREATE INDEX idx_jobs_pending
    ON jobs (created_at)
    WHERE status = 'PENDING';

    5. インデックスが逆効果になるケース

    インデックスにはメリットだけでなく、デメリットもあります。

    ① INSERT・UPDATE・DELETEが遅くなる

    索引はテーブルとは別に管理される検索用データです。そのため、データの追加・変更・削除に伴い、索引の更新も必要になります。特に更新頻度が高いシステムでは、索引を増やしすぎると更新性能が悪化します。

    ② ストレージ容量が増加する

    索引は追加の記憶領域を消費します。対象列が多い索引や大量の重複索引は、容量面でも運用面でも負担になります。

    ③ 検索対象が多すぎる

    例えば100万件のテーブルから80万件を取得するようなSQLでは、索引経由のランダムアクセスより、全表走査の方が効率的な場合があります。

    ④ 索引を使いにくいSQLになっている

    以下は代表的な注意例です。

    -- 列に関数を適用
    WHERE UPPER(customer_name) = 'TANAKA'
    -- 前方にワイルドカード
    WHERE customer_name LIKE '%TANAKA'

    前者は通常の列索引がそのまま利用されにくくなる場合があります。
    後者はB-treeでの通常の前方一致探索ができません。

    対策として、SQL条件の見直し、式に対する索引、全文検索機能などを検討します。ただし、関数適用や部分一致検索で必ず索引を使えないわけではなく、利用可能な方式はDBMSによって異なります。


    6. 実務での索引設計チェックリスト

    インデックスを作る前に、次の観点を確認しましょう。

    • どのSQLを高速化したいのか明確になっているか

    • WHERE句で何件まで絞り込めるか

    • 等値検索か範囲検索か

    • ORDER BYの並び順を考慮したか

    • 複合インデックスの列順序は適切か

    • 主キーや既存索引と重複していないか

    • INSERT・UPDATE・DELETEへの影響を考慮したか

    • データ分布や統計情報を確認したか

    • 実行計画で索引の利用を確認したか

    • 実データに近い件数で性能を測定したか

    最終的には、実行計画(EXPLAINなど)と実測結果を使って評価します。


    7. 試験直前に覚えておきたい重要ポイント

    画像

    試験対策として特に覚えておきたいのは、次の5点です。

    ① B-treeは等値検索にも範囲検索にも利用できる。
    ② ハッシュ索引は基本的に完全一致検索向け。
    ③ ビットマップ索引は少種類の値を組み合わせる分析処理に適する。
    ④ 複合インデックスでは列の順序が重要。
    ⑤ 索引の有効性は、カーディナリティだけでなく、選択率・データ分布・更新頻度で判断する。

    この5点を理解しておけば、単なる用語問題だけでなく、SQLとテーブル定義を読んで適切な索引を選ぶ問題にも対応しやすくなります。


    まとめ

    インデックス設計で重要なのは、索引の種類を暗記することではありません。実行するSQL、検索対象のデータ量、値の分布、システムの更新特性を踏まえて、適切な索引を選ぶことです。

    基本情報・応用情報ではまずB-treeとハッシュの違い、範囲検索と等値検索、カーディナリティの考え方を押さえましょう。さらに応用情報の科目Bやデータベーススペシャリスト対策では、SQLの検索条件、複合インデックスの列順序、実行計画まで理解を深めると効果的です。

    索引を「検索の仕組み」と「実務の設計判断」の両面から理解して、得点につなげていきましょう。


    関連記事


    参考資料

     
     
    IT資格の勉強法・合格ノウハウを発信。 書籍では追いにくい最新技術や最新動向まで。 試験対策だけでなく実務にも活きる知識をお届け。 【保有資格】 ・IPA:FE、AP、SC ・DB:OracleDB-Gold、OSSDB-Gold ・Cloud:AWS-SAP、OCI-AP

    あなたへのおすすめ