B+木インデックス

B⁺木インデックス

B⁺木インデックスは、木の深さが一定で葉のみが値をもつ平衡木を用いたインデックスで、RDBMSのインデックス法として現在最も普及しています。

B⁺木は、根および節にはキー値の範囲と下層のブロックへのポインタ、葉にはキー値と表内の行の位置情報と前後の葉へのポインタが格納されていて、根から節をたどっていくことで目的のデータを検索します。すべてのキー値が同じ深さにあるので、データ量が増加してもパフォーマンスの低下が少なく、どのキー値に対してもランダム検索や範囲検索、挿入・更新・削除を効率よく行える特徴を持ちます。また葉に含まれている前後の葉へのポインタによって一致検索だけでなく、"<"，">"，"BETWEEN"などの範囲検索を効率よく行えます。しかしデータの分布に偏りがある場合や、NULL値及び否定を含む検索条件では効果を発揮できません。