(O+P)ut

アウトプット



(O+P)ut

Output Log

【入門】B-Tree+とは?

スポンサーリンク

はじめに

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

B-Tree+とは?

簡潔に言えば「多くのデータベースで採用されている多分木型のインデックス」です。

まずは「インデックス」の部分を説明します。

インデックスとは?

本の世界における索引にあたる機能がインデックスです。
データベース検索の高速化に用いられており、例えば以下の例が分かりやすいです。「検索するキー」があった際にデータを片っ端から読むのではなく、事前に整理された階層構造に沿って値の探索を行うことで「効率よくデータを探索」できていることが分かります。

f:id:mtiit:20200801182228p:plain
インデックスの例( http://ossforum.jp/book/export/html/1029 より抜粋)

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

B-Tree+の構造

以下が構造でルートブロック、ブランチブロック、リーフブロックで構成されます。

f:id:mtiit:20200801183955p:plain
B-Tree+のインデックス構造

上の二分木と同じで上から辿っていきますが、特徴として「末端(リーフブロック)でのみ値を管理する」というものがあります。
確かに二分木の例では途中でも値を持っているので、最下層まで行くことなく探索が終わることもありますが、B-Tree+では必ず最後まで行きます。場合によっては探索回数が増える、一見デメリットともとれる構造です。

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

いくつかメリットがありますが、大きな特徴である「広範囲に跨った検索に強みがある」点で説明します。

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

ちなみに、B-Treeというデータ構造ではブランチでも値を保持します。こちらのメリットは、特定キーの探索においてはB-Tree+より効率的だという点です(最下層まで行く必要がないケースがあるから)。

終わりに

データベースだけでなくファイルシステムのインデックスにも採用されるB-Tree+ですが、ポイントは「多分木で末端でのみ値を管理する」という構造です。ここを抑えていると、書籍で本用語を見つけた場合も頭に入ってくるので覚えておくことをおススメします。


他の記事を読む