【入門】インデックスにおけるB-Tree+とは？

はじめに

B+木とも呼ばれ、データベースの世界でよく聞く本用語ですが「B-Tree+とは何か？」と聞かれると答えに困る方もいると思います。というわけで、本用語を初めて聞いた方向けにデータベース関連の基礎知識を交えながら分かりやすく解説しました。

B-Tree+/インデックスとは？

B+木を簡潔に言えば「一般的なデータベースの中に採用されている多分木型のインデックス」です。

まずは話の前提である「インデックス」の部分を説明しますが、本の世界における索引にあたる機能でフルスキャンをせずにデータの探索をするためにテーブル毎に作成されます。

具体的な利用方法として以下の例が分かりやすいです。要は「検索するキー」を全てのデータからしらみつぶしに読むのではなく、事前に整理された階層構造に沿って値の探索を行うことで「効率よくデータを探索」できていることが分かります。

インデックスの例（ http://ossforum.jp/book/export/html/1029 より抜粋）

上の図は枝分かれが二本出ているので「二分木」と呼び、B-Tree+は二つ以上に枝分かれをしているため「多分木」となります。

B-Tree+の中身

B-Treeの具体的なデータ構造ですが、ルートブロック、ブランチブロック、リーフブロックによって構成されます。

上で挙げた二分木と同じで上から辿っていきますが、B-Treeの特徴として「末端（リーフブロック）でのみ値を管理する」というものがあります。

なぜリーフブロックでしか値を持たないのか？

いくつかメリットがありますが、その中の一つである「広範囲に跨った検索に強みがある」点で説明します。

例えば特定のキーで検索をかけるのではなく、不等号で検索をかけたりする場面を考えてみてください。
上の例でNo2～No4の値が欲しい場合、リーフ1だけでなくリーフ2の値も必要となりますが、B-Tree+ではリーフ1の隣のリーフブロックを探索範囲に含めることで探索が可能です。しかし、ブランチでも値を持っている場合は「ブランチを確認し、そこに値が含まれていなければ隣のリーフを確認する」といった条件分岐が発生するため、このロジックを排除するためにRDBMではB-Tree+が採用されています。

逆に＋がついていない”B-Tree”ではブランチでも値を保持します。こちらのメリットは、条件分岐ではなく特定キーの探索においてはB-Tree+より効率的だという点です。よって検索条件の主な使われ方によってどちらを採用するのかを判断していきます。