2023-04-07

Bツリーインデックス

Bツリーインデックスとは

Bツリー（Balanced Treeの略）は、データベース領域で一般的に使用されるデータ構造であり、インデックス化のために利用されます。Bツリーインデックスは、データを階層的な形式でソートされた構造で保持することで、データベース内での効率的なデータの検索と取得を支援します。

最上部をルート、下端をリーフ、その間をブランチまたは内部ノードと呼ぶツリーを想像してください。B-Treeでは、各ノードが一定数のキーと子ポインタを持ちます。ノード内のキーはソートされており、各ポインタは子ノードを指しています。B-Treeの主な特徴は、バランスが取れていることです。つまり、全てのリーフノードが同じ深さにあり、どのリーフに到達するにも同数のトラバーサルを確保することができます。

Bツリーインデックスの利点

Bツリーインデックスには、データベースのインデックス化において人気のある選択肢となるさまざまな利点があります。

対数時間のデータアクセス
Bツリーは高さがバランスされているため、データに対して対数時間でアクセス、挿入、削除が行えます。
効率的なディスク読み取り
データベースは通常、ディスク上にデータを格納するため、Bツリーのツリー構造はディスク読み取りを最小限に抑えるために効率的です。
範囲クエリ
Bツリーは範囲クエリに特に効果的であり、開始位置を素早く特定し、その後データを線形にスキャンすることができます。

インデックスを作成する列の選択

データベースでインデックスを作成する列または列セットを決定する際に考慮すべき事項を説明します。適切な考慮なしにインデックスを作成すると、最適なパフォーマンスが得られない場合があります。テーブルのサイズ、カーディナリティ、およびクエリのWHERE句の使用など、いくつかの要素を考慮する必要があります。

テーブルのサイズ

テーブルのサイズに関しては、インデックス化が常に有益ではないことを理解することが重要です。小さなテーブルの場合、インデックスのオーバーヘッドが利益を上回る場合、フルテーブルスキャンの方が速くなることがあります。しかし、テーブルが成長するにつれて、インデックスは効率的なデータの取得にますます重要になります。

一般的な指針として、テーブルのサイズが大きい場合にはインデックスが有益です。テーブルの成長を定期的に監視し、クエリのパフォーマンスに性能の低下が観察される場合にはインデックスを作成することが推奨されます。

カーディナリティ

カーディナリティは、列に含まれる一意の値の数を指します。カーディナリティが高い場合、列には多数の一意の値が含まれていることを意味し、インデックスを使用することでクエリに必要なディスク読み取りの数を大幅に減らすことができます。

一方、カーディナリティが低い列の場合、インデックスの効果はそれほど高くありません。一意の値が少ないため、テーブルの大部分を読み取る必要があるため、インデックスの利点は限定的です。

WHERE句

クエリのWHERE句で頻繁に使用される列は、インデックスを作成する良い候補です。WHERE句は行をフィルタリングするために使用されるため、インデックスはデータベースエンジンが関連する行をより迅速に特定するのに役立ちます。

例えば、特定の日付範囲に基づいてデータをフィルタリングするクエリを頻繁に実行する場合、日付列にインデックスを作成することが有益であるかもしれません。

Bツリーインデックスの作成方法

単一の列にBツリーインデックスを作成する一般的なSQL構文は次のようになります。

sql

CREATE INDEX index_name ON table_name (column_name);

複数の列に対して複合インデックスを作成する場合、構文は少し異なります。

sql

CREATE INDEX index_name ON table_name (column1_name, column2_name, ...);

一部のデータベースでは、作成するインデックスのタイプ（Bツリーなど）を明示的に指定することもできます。例えば、PostgreSQLでは次のように指定できます。

sql

CREATE INDEX index_name ON table_name USING btree (column_name);

Bツリーインデックスで意味のないパターン

Bツリーインデックスを使用してもパフォーマンスの利点が得られない、または効率が悪くなる場合がある特定のシナリオやパターンを紹介します。

インデックス列に対して演算が行われる場合

比較する値の前に列に対して関数や演算を適用する場合、データベースはBツリーインデックスを効果的に使用できない場合があります。

sql

SELECT * FROM employees WHERE age * 2 > 60;

この例では、データベースはage列に対して比較を行う前に2を乗算するため、age列のインデックスを効率的に使用することはできません。

インデックス列に対してSQLが適用される場合

演算の適用と同様に、インデックス列にSQL関数を適用すると、インデックスが効果を発揮しなくなります。

sql

SELECT * FROM employees WHERE UPPER(last_name) = 'SMITH';

このクエリでは、last_nameにインデックスがある場合でも、データベースは各エントリにUPPER()関数を適用する必要があるため、効率的に使用することができません。

IS NULL述語を使用する場合

Bツリーインデックスは、NULL値の数が多い列に対して、特にNULL値をクエリする場合には常に効率的ではありません。

sql

SELECT * FROM employees WHERE middle_name IS NULL;

もしmiddle_nameに多数のNULL値が含まれる場合、この列に対するBツリーインデックスは、このクエリに対して有意なパフォーマンスの利益を提供しないかもしれません。

ORを使用する場合

OR演算子を使用する場合、データベースはインデックスではなくフルテーブルスキャンを実行することがあります。特に関与する列のカーディナリティが低い場合にこれが起こります。

sql

SELECT * FROM orders WHERE status = 'SHIPPED' OR status = 'PROCESSING';

この例では、status列に非常に少数の一意の値がある場合、インデックスは効果的ではありません。

後方一致や中間一致のLIKE述語を使用する場合

文字列の一部に一致するパターンを持つLIKEを使用する場合、Bツリーインデックスは効率的に使用されません。

sql

SELECT * FROM products WHERE product_name LIKE '%laptop%';

このクエリでは、product_nameにインデックスがあっても、パターンの先頭にワイルドカードを使用しているため、インデックスを効果的に活用することができません。

暗黙の型変換が行われる場合

暗黙の型変換はインデックスの効率的な使用を妨げます。

sql

SELECT * FROM employees WHERE department_id = '10';

department_idが整数型の場合、データベースは値の比較前に型変換を行わなければならず、効率的なインデックスの使用が妨げられる可能性があります。

プライマリキーと一意制約とBツリーインデックス

ここではデータベースにおけるプライマリキー、一意制約、およびBツリーインデックスの関係について説明します。

プライマリキーとBツリーインデックス

プライマリキーは、テーブル内の各行を一意に識別するための列または列のセットです。リレーショナルデータベースでは、プライマリキーは重複する行がなく、全ての行が一意に識別されることを保証します。

列または列のセットにプライマリキー制約を定義すると、データベース管理システムは自動的にその列に対して一意なBツリーインデックスを作成します。これは、プライマリキー制約が一意性を保証し、プライマリキーに基づいて行を迅速に検索する必要があるためです。Bツリーインデックスはそのような目的には適しており、対数時間の検索特性を持っています。

したがって、すでにプライマリキーとして定義された列に対して手動でインデックスを作成する必要はありません。一意なBツリーインデックスはデータベースによって自動的に作成および管理されます。