創屋ぷれす

B+木

アルゴリズムの一種
まずBTree(木構造)というのがあって、データを木構造で表現する
データ検索などDBMSに用いられることが多い
インデックス構造と考えれば良い

BTreeに対してB+Treeは構造は似ているが違いとして以下2点がある
・データはノードで持たずリーフで持っている
・各リーフからリーフへのポインタを持つ

概念としては上記の通りで何がうれしいかというとデータ検索における処理時間のオーダーを小さくしてくれるという恩恵がある
B+TreeはデータN個について、オーダーlogNということらしい
ということはNに比例して肥大していくわけではなく、ある程度の処理時間で頭打ちになる
つまりデータの個数に関係なく一定の処理時間が期待できる、ということです

Comments are closed.