B+木
B+木の葉ノードは連結リストで相互にリンクされていることが多い。これにより範囲クエリが簡単かつ効率的に行える(上述の上限は連結リストがなくとも実現できる)。これによって領域消費量が大幅に増えたり、手間が大幅に増えるということはない。
記憶装置のブロックサイズが B バイトの場合、格納されるキーのサイズを k バイトとすると、最も効率的なB+木では b = ( B / k ) − 1 {\displaystyle b=(B/k)-1} となる。理論的には1を引く必要はないが、実際にはインデックスブロックには何らかの余分な空間が必要になることが多い(例えば、葉ブロックでの連結リスト用参照)。インデックスブロックがその記憶装置の実際のブロックより若干大きい場合、性能は大幅に低下する。
B+木のノードが配列として構成される場合、挿入や削除で配列の要素をずらす必要が生じ、性能が悪くなる。そのため、ノード内の要素は2分木やB+木で構成するのが望ましい。
B+木はメモリ上のデータ格納にも使われる。その場合、ブロックサイズはプロセッサのキャッシュラインに合わせるのがよい。ただし、キャッシュのプリフェッチ機能がある場合、キャッシュラインの何倍かをブロックサイズとした方が性能がよいことが研究で証明されている。
B+木の次数は木構造内のノードの容量の尺度である。次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる。例えば、次数7のB+木があるとき、根ノード以外の内部ノードは7個から14個のキーを格納する。根ノードは1個から14個のキーを格納する。
さらに各内部ノードは、最低でも d+1 個、最高でも 2d+1 個の子ノードを持つ。