はじめに

webエンジニアのためのデータベース技術[実践]入門を読み進めているのですが、なかなか腹に落ちる感じがないので少量ずつ文字にして理解を勧めていきたい

 

B+Treeインデックス

ルートブロック、ブランチブロック、リーフブロックという木のような構造をもっているデータベースのインデックス構造の一つ。リーフブロックに実際のデータの格納位置の情報があり、ルート、ブランチにはそれぞれ下のブロックの検索のキーに対して対象のブロックはどこにあるのかという情報のみある。

ハッシュインデックスの進化版？

                                                   出典 B+木 - Wikipedia

この図はルートとブランチが兼ねているが、d1を検索するにはまずルートブロックの3以下を選びリーフブロックから1をみつけだして(scanして)d1の場所を見つけるという流れになる。

分岐を多く作れるので枝分かれを2つしか作れない二本木構造より階層を浅くでき、アクセス回数を減らすことができる。

 

B+TreeとB-Tree

B-Treeというインデックス構造もあり、これは途中のブランチにも値を持つことがあるデータ構造です。リーフまでアクセスしなくても値を見つけることが利点ですが、このB-Treeと比較してB+Treeは範囲検索する時に大きなメリットを持ちます。

上の図を見ればわかりますがB+Treeでは目的の値がそのリーフだけではすべて見つからない時には隣のリーフへジャンプして値を探しに行っています。リーフにしか値はないので途中でブランチブロックに戻ったりする必要はありません。B-Treeはブランチにも値があるかもしれないのでブランチやリーフを行ったり来たりして値の存在確認をしなくてはならない

 

B+Treeインデックスのメリット

二本木（２又にのみ別れていく木の構造）よりも階層を浅くでき、さらにブランチにデータの格納場所を持たないため一度リーフにたどり着けば範囲検索でも隣のリーフのみ探せば良いので高速。

インデックスの”デファクト”とのこと。デファクトスタンダードってことかな？