基本情報のインデックスとは？検索の仕組み・更新コスト・複合索引

データベースのインデックスは、条件に合う行へ効率よくたどり着くための索引です。基本情報の学習では「検索を速くする」と覚えるだけでなく、どの列をどう探すと役立つのか、なぜ更新の負担が増えるのかまでつなげて理解すると、説明文の選択肢で迷いにくくなります。

索引は、表のデータを消したり、すべての処理を一律に速くしたりするものではありません。検索条件、取り出す行の割合、索引の種類、更新頻度によって効果は変わります。この記事では社員表を使い、全表走査との違い、B木・ハッシュの特徴、複合索引の列順を整理したうえで、自主例題で判断を確かめます。

この記事のポイント

索引の値から目的の行へ進む流れを社員表で理解できる
索引が役立つ検索と、全表走査が候補になる検索を見分けられる
登録・更新・削除で索引を保守する理由を説明できる
複合索引の列順と、選択肢の断定に注意する点が分かる

無料

基本情報技術者試験過去問アプリ

本番形式で繰り返し解ける。スキマ時間に1問から

2,000問以上収録

無料で過去問を解く

基本情報のインデックスの仕組み

索引は値と行の対応を持つ

インデックスは日本語では「索引」と呼ばれます。厚い本で用語を調べるとき、最初のページから全文を読む代わりに、巻末の索引で用語と掲載ページを探しますね。データベースでも、検索の手掛かりとなる値と、該当する行へたどり着くための情報を整理しておくことで、探す範囲を小さくできる場合があります。

たとえば、社員番号・氏名・部署を持つ社員表を考えます。説明用の小さな表には、社員番号340の佐藤さん、120の田中さん、560の鈴木さん、230の伊藤さんが格納されているとします。社員番号は並び順と一致していません。ここに社員番号の索引を用意すると、番号を手掛かりに対応する行を探すための別の入口ができます。

スクロールできます

社員番号の索引値	対応する行の情報	社員表で取得できる内容
120	田中さんの行へ進む	氏名：田中、部署：営業
230	伊藤さんの行へ進む	氏名：伊藤、部署：総務
340	佐藤さんの行へ進む	氏名：佐藤、部署：開発
560	鈴木さんの行へ進む	氏名：鈴木、部署：営業

この表は、索引の役割を示すための模式的な対応表です。実際の索引は、単純な二列の一覧とは限らず、木構造などで管理されます。また、行を示す情報の表し方もDBMSや索引の種類によって異なります。「索引には必ず物理アドレスがそのまま入る」とまで一般化する必要はありません。

社員番号340を指定する検索では、まず索引から340に対応する入口を見つけ、必要に応じて社員表の行を読み、氏名や部署を取得します。重要なのは、索引を付けても社員表の内容そのものは残ることです。索引は元の情報を置き換えるのではなく、目的の情報へ進む経路を用意します。

また、「キー」という語にも注意しましょう。索引を探すために使う値を検索キーと呼ぶ場合がありますが、その列が必ず主キーであるとは限りません。部署のように同じ値を持つ行が複数ある列にも、通常の索引を作れます。営業という値に対して、田中さんと鈴木さんの両方へ進む入口を管理するイメージです。

索引検索の基本的な発想は、PostgreSQL公式のインデックス入門でも、本の索引との対応で説明されています。ここでは細かな内部形式よりも、「検索値を手掛かりに、必要な行へ効率よく進む」という役割を押さえましょう。

全表走査と索引検索を比べる

全表走査は、表全体の行を順に調べて条件に合う行を探す方法です。先ほどの社員表で、社員番号340の行を探す入口が用意されていなければ、各行の社員番号を確認する方法が候補になります。表が大きいほど、少数の行を得るために多くのデータを読むことになりやすいですね。

索引が利用できる場合は、検索値の周辺へ絞り込んでから、該当する行を読みます。全員の情報を順に確認するのと、番号別の索引から該当箇所へ進むのでは、読み方が変わります。ただし、「表の行数と同じ回数だけ必ず比較する」「索引なら一回で終わる」という固定的な説明は避けてください。実際の処理量にはデータ構造や実行方法も関わります。

さらに、索引をたどる処理にも費用があります。索引の読み取りに加えて表の行も読むなら、その両方を行います。目的の行が表のあちこちに散らばっていれば、必要なデータへのアクセスが増えることもあります。索引があるという理由だけで、どの検索でも全表走査より速いとはいえません。

たとえば社員全員の氏名と部署を出す処理では、結局多くの行の内容が必要です。索引で一人ずつ行へ進むより、表をまとめて読んだ方が有利な場合があります。反対に、大きな社員表から特定の番号一件だけを取り出す検索では、適切な索引による絞り込みが役立ちやすくなります。どちらも「何件あるか」だけでなく「何件を読む必要があるか」が判断材料です。

索引は検索の候補となる経路です。DBMSは条件や統計情報などをもとに実行方法を選ぶため、索引が作成されていても毎回使われるとは限りません。

基本情報の問題を読むときは、「格納位置への効率的なアクセス」「検索速度の向上が期待できる」という説明と、「どんな処理も必ず高速になる」という説明を区別しましょう。前者は索引の目的を表し、後者は条件を省いた強すぎる断定です。速くなる仕組みを理解しておくと、この違いを言葉だけで判断せずに済みます。

なお、索引の中に検索と取得に必要な情報がそろうなど、条件が合えば表の行の読み取りを減らせる方式もあります。いわゆるカバリングインデックスに関係する考え方ですが、ここで覚える中心は「索引を読めば常に表を読まなくてよい」ではありません。格納内容やDBMSの仕組みによって成立条件が異なります。詳しい条件はPostgreSQL公式の索引のみのスキャンで確認できます。

B木とハッシュで探し方が違う

索引は一種類ではありません。基本情報で構造を見分けるときは、B木・B+木系の索引とハッシュ索引の違いを先に整理すると分かりやすいです。前者は大小関係を使って探索する範囲を絞り、後者はキーから計算した値を手掛かりに候補の場所を求めます。

B木系は、節でキーを比較しながら枝をたどる構造です。一つの節から複数の枝へ分かれ、偏りを抑えるように管理されるため、大きなデータでも木を深くしすぎずに探せるよう工夫されています。二分探索の「毎回ちょうど半分」と同じ構造ではありません。二分木とB木は、名前が似ていても同じものとして扱わないでください。

B+木では、検索対象へ進む情報を葉にまとめ、葉どうしをつなぐ構成が代表的です。ある値の場所を見つけたあと、その付近の値を順にたどれるので、「社員番号が200以上400以下」のような範囲を探す発想と相性がよいですね。索引の順序を利用できる検索では、並べ替えの負担を抑えられる場合もあります。

スクロールできます

索引の考え方	探し方の手掛かり	基本的に理解したい用途・注意
B木・B+木系	キーの大小関係を見て枝をたどる	一致検索や範囲検索。種類・条件によって順序も利用
ハッシュ	キーをハッシュ関数で変換する	等しい値を探す。異なるキーの衝突に注意
転置索引	語などから含まれる文書へ進む	全文検索など。文書側から語を読む順序を逆にする

ハッシュ索引では、社員番号340をハッシュ関数へ渡し、得られた値を手掛かりに候補を探します。ただし、違う社員番号から同じハッシュ値が得られる可能性があります。この衝突を処理し、元のキーも確認する必要があるので、「計算した場所にある行は必ず目的の行」とは考えません。

また、ハッシュ値の順序は元の社員番号の大小関係を表すとは限りません。そのため、通常のハッシュ索引を「200以上400以下」という範囲検索にそのまま適用する発想は不向きです。PostgreSQLのハッシュ索引も単純な等価比較を対象とし、B-tree索引は等価比較と範囲比較を扱います。これはPostgreSQL公式の索引の種類で確認できます。

転置索引は、文書から単語を順に読むのではなく、単語を入口に、その単語を含む文書などへ進む考え方です。試験の選択肢に出てきたら、通常の数値の大小比較やハッシュ計算と分けて考えましょう。すべての索引を同じ仕組みで説明するより、「何を入口にして何へ進むか」を見ると整理できます。

キーから位置を求める処理そのものが曖昧なら、基本情報の線形探索・二分探索・ハッシュ探索で探索の基礎を補えます。この索引の記事では配列の添字や擬似言語の追跡まで広げず、データベースで検索経路を準備する意味に注目します。

主キー・正規化と役割を分ける

主キー、索引、正規化は、すべてデータベースに関わる語ですが、答える疑問が異なります。主キーは「どの行かを一意に識別するための列は何か」、索引は「条件に合う行へどう効率よく進むか」、正規化は「データの重複や依存関係をどう整理するか」に注目すると区別しやすいです。

社員番号を主キーにするのは、社員表の一行を識別するためです。部署に通常の索引を付けるのは、部署を指定する検索に役立てるためです。同じ部署の社員が何人もいても、通常の索引だからという理由で登録を拒否されるわけではありません。索引一般に、値の重複を禁止する意味があると覚えないことが大切です。

スクロールできます

仕組み	主に注目する目的	索引との区別
主キー・一意性の制約	行を識別し、許される値のルールを守る	通常の索引がすべて一意性を保証するわけではない
インデックス	検索条件に合う行への経路を用意する	普通の索引には同じ値が複数あってもよい
正規化	データの依存関係を整理して表を設計する	検索経路を増やす処理とは別
外部キーの制約	表どうしの参照関係のルールを守る	索引を付けるだけで参照整合性を保証するわけではない

例外として、ユニークインデックスは一意性を保つためにも使われます。また、DBMSによっては主キーや一意制約を設定すると、対応する索引が自動で作られます。PostgreSQLでも主キーや一意制約のための索引を自動作成します。つまり目的は区別できますが、実装上は索引が制約を支える場合がある、という関係です。PostgreSQL公式の一意索引にこの関係が示されています。

選択肢では「索引の一般的な目的」を聞いているのか、「ユニークインデックスの性質」を聞いているのかを先に見ましょう。前者なら検索アクセスの効率化、後者なら一意性にも注目します。NULLの細かな扱いは製品や設定によって違うため、「ユニークならどのDBMSでも同じ扱い」と広げない方が安全です。

表設計やデータ操作を復習したい場合は、基本情報のSQL・データベースと正規化の基礎を参照してください。索引の理解では、表を分ける作業、行を選ぶ条件、行へ進む経路を別々に考えられれば十分です。

基本情報のインデックスの使いどころ

効果は件数より絞り込みで考える

索引を作る列を考えるとき、まず見るのは実際の検索条件です。よく社員番号を指定して社員を探すなら、社員番号を入口にする索引が候補になります。部署別に社員を取り出す処理が多いなら、部署にも検討する価値があります。表にある列すべてへ付けるのではなく、使われる検索と結び付けて考えます。

次に、条件に合う行が全体のどれくらいを占めるかを確認します。説明用に、10万行の社員関連データから番号で一件を探す場合と、ほぼ全員に当てはまる「在籍中」で9万件を取り出す場合を比べましょう。前者は読む必要のある範囲を大きく減らしやすい一方、後者は索引を使っても多数の行を読む必要があります。この数字は考え方を示す仮定で、速度の測定結果ではありません。

列に含まれる値の種類の多さを、カーディナリティという語で説明することがあります。社員番号は種類が多く、在籍状態は少ない、といった見方です。ただし「値の種類が少ない列には絶対に索引が効かない」も言い過ぎです。たとえば状態が二種類だけでも、一方の「確認待ち」がごく少数なら、その少数を探す処理に役立つ可能性があります。

このため、列全体の値の種類だけで結論を出さず、検索する値の分布を考えます。営業部署に大多数が集まっている表と、各部署へ均等に分かれている表でも事情は違います。試験問題に「ほとんどの行」「ごく少数の行」といった条件があれば、索引でどこまで読む範囲を減らせるかを考える材料にしましょう。

スクロールできます

検索の例	索引を検討する理由	判断するときの注意
大きな表から番号一件を検索	該当行を少数へ絞りやすい	対象列に適切な索引があるか
少数の確認待ちだけを取得	状態の種類が少なくても絞り込める可能性	値の種類より、その値の割合を見る
全員の一覧を取得	索引による絞り込みは小さい	全表走査なども候補になる
日付の狭い範囲を取得	B木系で範囲を限定できる可能性	範囲の広さと取り出す件数を見る
番号を使って別表と対応付ける	対応する行を探す経路に使える可能性	索引の存在だけで処理全体の速さは決まらない

並び順も、索引が役立つ場面の一つです。欲しい順序とB木系の索引の順序が合えば、並べ替えの処理を減らせる場合があります。特に、順番の先頭から少数を取得する処理では検討しやすいですね。ただし、表の大部分を出す場合は、まとめて読み取って並べ替える方法が有利なこともあります。条件はPostgreSQL公式の索引と並び替えにも説明されています。

もう一つの注意は、検索条件が索引の使える形になっているかです。列そのものに索引があっても、検索で別の式へ加工して比較すれば、同じ索引をそのまま活用できるとは限りません。対応する式の索引など別の仕組みもあるので、「関数が出たら必ず索引が使えない」と暗記せず、入口と検索条件が対応しているかを見てください。

実際のDBMSでは、実行計画を見て選ばれた経路を確認します。基本情報の学習なら、まず「適切な条件では役立つ」「作成しただけで使用は保証されない」の二点が中心です。性能改善をするときに、索引が使われた事実と処理が速くなった事実を分けて確認する、という考え方にもつながります。

更新と容量にも費用がかかる

索引の費用は、作成時だけでは終わりません。社員を新しく登録したら、その社員番号から行へ進めるように索引にも情報が必要です。社員番号を変更したら、古い番号と新しい番号の対応を整えます。社員を削除したら、検索で不要な行へ進まないようにするための管理も必要になります。

本の索引で考えると、本文の用語を追加・移動・削除したのに索引を放置すると、違うページを案内してしまいますね。データベースでも表と索引の対応を保つ処理が必要です。通常はDBMSが保守するので、利用者が一件ずつ索引表を書き直すわけではありません。この追加の管理が、登録・更新・削除の負担になります。

ただし、一行を変更するたびに索引全体を最初から作り直す、という意味ではありません。どこまで処理が必要かは索引の構造や変更内容、DBMSの実装によって異なります。特に、索引の対象になっている値を変える更新と、対象外の列だけを変える更新を、常に同じ費用として説明しないようにしましょう。

社員番号、部署、氏名、入社日へそれぞれ索引を用意すると、検索の入口は増えます。一方、登録する情報に対応する索引の管理も増え、保存領域も必要です。使わない索引を増やすと、費用に対して検索上の利益が得られません。読み取り中心の表と、頻繁に大量登録する表では、同じ列構成でも望ましい索引が変わり得ます。

ここで「索引は更新を遅くするから、更新処理には役立たない」と決め付けるのも誤りです。たとえば特定番号の社員の部署を変更する処理には、対象行を探す段階と、値を書き換える段階があります。索引は前者に役立つことがあり、後者では保守の負担が加わります。処理全体で得かどうかは両方を合わせて考えます。

更新対象を見つける利益と、索引を保守する費用は別の話です。「索引は検索に役立つ」と「索引の維持には負担がある」は両立します。

運用で性能を判断するなら、よく使う検索、取り出す件数、登録・更新の頻度、必要な容量を一緒に見ます。特定の検索一回だけが速くなっても、頻繁な書き込みが大きく重くなれば、全体として望ましくない可能性があります。基本情報の設問でも「アクセス効率」と「更新負荷」のどちらを説明しているかを分けると読みやすいです。

データを正しく確定することや、同時更新の矛盾を防ぐことは、索引の主な目的とは別です。その点を整理したい場合は、基本情報のトランザクション・ACID特性・排他制御を参照できます。索引があるだけで、更新のまとまりや同時実行の安全性まで保証されるわけではありません。

複合インデックスは列順に注目

複合インデックスは、複数の列を組み合わせた索引です。ここではB木系の索引として、部署を先に、同じ部署の中では社員番号順に並ぶ「部署、社員番号」の組合せを考えます。一つの列にそれぞれ別の索引を用意する場合と、二列を一組の入口として管理する場合は、同じ構成ではありません。

「部署が開発、社員番号が340」という検索なら、開発のまとまりへ進み、その中の340を探すイメージになります。また、部署だけを指定する検索でも、開発のまとまりを入口にできます。辞書の見出しを大分類、その中の項目を小分類と見ると分かりやすいですね。

スクロールできます

複合索引の並び	部署を指定した検索	社員番号だけを指定した検索
部署、社員番号	先頭の部署を手掛かりに範囲を絞りやすい	番号が部署ごとに分散し、同じ絞り方はしにくい
社員番号、部署	部署だけでは同じ絞り方はしにくい	先頭の番号を手掛かりに範囲を絞りやすい

一方、「社員番号340」だけでは、部署別の各まとまりに340があるかを確認する必要が出てきます。部署を最初に並べる索引と、社員番号を最初に並べる索引では、使いやすい入口が違います。同じ二列を使っていても、定義する列順を入れ替えれば性質が変わる点を押さえましょう。

ただし、「先頭列を指定しない索引は絶対に使われない」とは一般化できません。DBMSや索引方式によって扱いは異なります。PostgreSQL 18のB-treeでは、先頭列に通常の条件がなくても後続列の条件を使うスキップスキャンが有利になる場合があります。部署の種類が少なければ、各部署のまとまりから番号を探す方法が候補になる、と考えると例外の意味がつかめます。

この説明の根拠はPostgreSQL公式の複数列索引です。試験学習では、まず「B木系では先頭列からの条件が効率に大きく関わる」を基本にし、特定製品の実行方式をすべての索引へ広げないようにしましょう。問題文が方式や前提を指定していれば、その条件に従います。

また、「部署、社員番号」の索引と、「社員番号、部署」の索引の差は、検索条件を文章に書く順番とは別です。「部署は開発で番号は340」と説明しても、「番号は340で部署は開発」と説明しても、同じ条件なら索引の定義順が変わるわけではありません。列の並びという語が、索引内の並びを指しているのか、条件の記述順を指しているのかを区別してください。

複合索引を検討するときは、二列を同時に使う検索だけでなく、片方だけを使う検索も確認します。部署だけの検索が多いのか、番号だけの検索が多いのかで候補は違います。すべてに対応しようと索引を増やせば、更新と容量の費用も増えます。列順だけを暗記するより、実際の入口を言葉で説明できる状態を目指すと応用しやすいです。