Jun Mukai:自分はデータベースやこういうことは専門的ではないので、詳しい人によるより詳細な解説してくれることを期待したいところです。 さて、まずB-treeとB+treeなんですが、どちらもほとんど同じ構造とアルゴリズムで、ごくわずかな違いしかありません。B+treeとB-treeの違いは次の2点であるとされます。 * B-treeは中間ノード（リーフでないノード）も値を持ちますが、B+treeは中間ノードはキーのみで、値はリーフからしか見えません * リーフノードは隣のリーフノードへのリンクを持っていて、リーフだけで連結リストのような構造になっています B+treeは中間ノードで値をもたないため、探索時にはかならずリーフまでたどる必要があります。直感的に効率はむしろ悪い可能性もありそうです。 これについては次のような解説がよくなされます。中間ノードからデータへのポインタを省くことによって、同じ大きさの記憶領域により多くの子ノードへのリンクを配置できるようになります。ノードごとのリンク数が増えると木の高さも減り検索効率が向上します。 またデータベースの場合にはインデックスがメモリではなくディスクなどの記憶領域にあったりするので、このことは探索時のIO操作数の減少にもつながり、結果的にはより効率よくインデックス上を探索できることにつながります。 値データがリーフにしかないこと、リーフが連結リストになっていることですが、これによってインデックスの要素を順番にスキャンしたい場合の操作が単純かつ効率的に行えます。中間ノードに値データを持つ場合、リーフのデータをスキャンし終えたらいったん親ノードに戻って、1個データを読んだら次の子ノードに戻って、みたいな操作になります。先程のようにインデックスがディスク等にある場合にはIO操作が発生する可能性もあり、効率は劣化します。 SQLでデータを処理する場合、ある値からべつな値までといった範囲指定は非常によくあり、インデックスの(部分的な)スキャンはめずらしいことではないので、スキャン操作が効率的に扱えることはデータベースでは重要であろうと思います。 こういうことからデータベースという条件においては総じてB+treeのほうが効率が良いという考えかたが一般的であると思います。ただし、IO操作を伴わないインメモリなデータベースであれば、また別の議論が成立する余地があるかもしれません(もっともキャッシュヒット効率などで同様の議論が可能な可能性はあります)。 B-treeは今日ではそれほど利用されることはないかなと思っていますが、たとえばRustではstd::collections::BTreeMap / BTreeSet などとして利用できます。