最も一般的なインデックスのデータ構造は「B-Tree（B木：Balanced Tree）」と呼ばれる木構造です。B-Treeインデックスでは、データが常にソート（整列）されたツリー形式で保持されます。検索する際は、根（ルート）ノードから順に値を比較し、枝分かれをたどることで、目的のデータ（リーフノード）へ最小限のステップで到達できます。例えば、100万件のデータであっても、B-Tree構造を使用すれば、わずか数回〜十数回の比較処理（計算量はO(log N)）で目的のデータを見つけ出すことができます。インデックスがない状態では、最初から最後まで順番に調べる「テーブルフルスキャン（計算量はO(N)）」を行うため、劇的な速度差が生まれます。

ただし、インデックスには以下のような重大なデメリット（トレードオフ）も存在します。