インデックスとアクセス方式

インデックスとアクセス方式は、主にB+-ツリーとハッシュインデックスからなる補助的なデータ構造であり、データベースがテーブル全体をスキャンすることなく一致するタプルを特定できるようにし、オプティマイザが依拠する高速なアクセスパスを提供する。

Definition

インデックスとは、リレーションの1つ以上の属性に対する補助的なデータ構造であり、キー値を一致するタプルの位置にマッピングすることで、テーブルサイズに対して劣線形時間での検索を可能にする。アクセス方式とは、クエリがデータを読み取るために使用するメカニズムであり、フルスキャンやインデックススキャンなどがある。

Scope

このトピックでは、データアクセスパスの背後にある構造と概念、すなわち、クラスター化インデックスと非クラスター化インデックス、主インデックスと副インデックスの区別、等価検索と範囲検索をサポートする主力となる順序インデックスとしてのB+-ツリー、等価検索のためのハッシュベースのインデックス、そして選択、結合、ソート回避におけるインデックスの役割について扱う。インデックスの選択がクエリコストと更新オーバーヘッドにどのように影響するかを論じる。コストベースのオプティマイザによる全体的なプラン選択は別のトピックであるため、ここでは扱わない。

Core questions

• B+-ツリーは等価クエリと範囲クエリの両方をどのように効率的にサポートするのか？
• クラスター化インデックスと非クラスター化インデックス、主インデックスと副インデックスの違いは何か？
• ツリーインデックスよりもハッシュインデックスが好ましいのはどのような場合か？
• インデックスは選択、結合、順序付けられた検索をどのように高速化するのか？
• 挿入、更新、削除におけるインデックスの維持コストはどのくらいか？

Key concepts

• B+-ツリーインデックス
• ハッシュインデックス
• クラスター化インデックスと非クラスター化インデックス
• 主インデックスと副インデックス
• 高密度インデックスと疎インデックス
• 範囲検索と等価検索
• 拡張可能ハッシュと線形ハッシュ
• インデックス維持コスト

Key theories

B+-ツリーインデックス

B+-ツリーは、バランスの取れた高ファンアウトの検索ツリーであり、キーをソートされた順序で格納し、すべてのデータ参照をリーフに保持する。等価クエリ、範囲クエリ、順序付けられたスキャンを対数的なI/Oでサポートし、挿入と削除の下でもバランスを維持する。

クラスター化インデックスと非クラスター化インデックス

クラスター化インデックスは、テーブルの行をインデックスキーによって物理的に順序付けて保持するため、範囲スキャンが非常に効率的である。一方、非クラスター化（副）インデックスは順序付けられていないファイルを指すため、一致する多くの行を取得するには、行ごとに1回のI/Oが必要となる場合がある。

ハッシュインデックス

ハッシュベースのインデックスは、キーをバケットにマッピングすることで、期待される定数時間での等価ルックアップを可能にするが、範囲クエリはサポートしない。拡張可能ハッシュや線形ハッシュなどの動的スキームにより、データとともに適切に成長できる。

Clinical relevance

インデックスはデータベースのパフォーマンスにとって最も一般的な実用的な手段である。適切なインデックスを選択することで、トランザクションクエリや分析クエリにおいて、フルテーブルスキャンをミリ秒単位のルックアップに変えることができる。一方で、インデックスを過剰に作成すると更新が遅くなるため、インデックス設計は実際のシステム運用において繰り返し行われる決定事項である。

History

BayerとMcCreightは1972年に、ディスク上の大規模な順序付けられたインデックスを維持するためにB-ツリーを導入した。すべてのデータをリーフに保持するB+-ツリーの派生形は、Comerの1979年の「Ubiquitous B-tree」で概説されているように、標準的なデータベースインデックスとなった。ハッシュベースのアクセス方式と動的ハッシュスキームは並行して発展し、両方のファミリーはすべてのリレーショナルエンジンの中核であり続けている。

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

データベースで二分探索木ではなくB+-ツリーが使用されるのはなぜですか？

データベースはデータをディスクに保存し、そのコストはページ読み取りの回数によって支配されます。B+-ツリーは高いファンアウトを持つため、各ノードがディスクページを埋め、ツリーは非常に浅くなり、任意のレコードに到達するために必要なI/Oはごくわずかです。二分木ははるかに深くなり、より多くのディスクアクセスを招くでしょう。

B+-ツリーではなくハッシュインデックスを使用すべきなのはどのような場合ですか？

等価ルックアップ（例：特定のIDを持つ行を検索する）のみが必要で、期待される定数時間アクセスを望む場合は、ハッシュインデックスを使用します。範囲クエリ、順序付けられたスキャン、またはプレフィックスマッチングも必要な場合はB+-ツリーを使用します。ハッシュインデックスはキーの順序を保持せず、範囲条件に効率的に応答できないためです。