B+木
次数 b、高さ h のB+木には以下の特徴がある。
格納できる最大レコード数は n = b h {\displaystyle n=b^{h}}
最小キー数は 2 ( b / 2 ) h − 1 {\displaystyle 2(b/2)^{h-1}}
この木構造を格納するのに要する領域は O ( n ) {\displaystyle O(n)}
1つのレコードの挿入に要する操作回数は最悪で O ( log b  n ) {\displaystyle O(\log _{b}n)}
1つのレコードを探すのに要する操作回数は最悪で O ( log b  n ) {\displaystyle O(\log _{b}n)}
位置がわかっているレコードの削除に要する操作回数は最悪で O ( log b  n ) {\displaystyle O(\log _{b}n)}
範囲クエリで k 個の要素が見つかる場合、要する操作回数は最悪で O ( log b  n + k ) {\displaystyle O(\log _{b}n+k)}