読み方：ビーツリーインデックス

B-Treeインデックス【B-Tree index】B木インデックス

概要

B-Treeインデックスとは、データベースで高速な検索や範囲検索を実現するために用いられる木構造型の索引（インデックス）の一つ。大量のレコードの中から目的の情報を少ない手順で見つけ出すことができ、多くの主要なデータベースシステムで標準的に採用されている。

「平衡多分木」と呼ばれる木構造の一種を使い、各ノードに複数のキーと子ノードへのポインタを保持する。データはキーの大小関係に基づいて階層的に整理され、常に木の高さがほぼ一定に保たれるよう、データの登録時に再調整される。検索、挿入、削除といった操作はいずれも木の高さに比例する計算量で実行でき、データ件数が増加しても性能の低下が緩やかである。

データベース管理システム（DBMS）では、テーブルの特定の列に対してB-Treeインデックスを作成することで、その列の値をキーとして並び替えられた索引構造が生成される。検索時にはルートノードから順に比較を行い、該当する範囲の子ノードへとたどることで目的のレコードに到達する。キーが順序を持つ構造のため、完全一致検索だけでなく、範囲検索や前方一致検索なども高速に処理できる。

一方、B-Treeインデックスを作成するとデータの更新や追加のたびに木構造のメンテナンスが必要となるため、書き込み処理の負荷は増大する。頻繁に検索条件として利用される列に対してB-Treeインデックスを設定し、検索よりも追加や更新の方が圧倒的に多い列にはハッシュインデックスなど別の方式を用いるなど、用途によって使い分ける場合もある。B-Treeインデックスは多くの商用およびオープンソースのデータベース製品で標準的なインデックス方式として採用され、多くの製品ではデフォルトのインデックス方式に指定されている。