与えられたリストから効率的にB +ツリーを構築するには？

Question

サイズNの順序付けられていない要素のリストからB +ツリーを作成したいとします。

私は、それを行うための最適な境界は、ブロック転送であることを知っています。これはソートにも最適です。だから私は単純にアイテムを選択してツリー内に個別に挿入することはできません。なぜなら、ブロック転送をO(N logB(N))にするからです。

私はツリーを構築する最善の方法は、葉がとにかく順序付けされているので、最初に要素を並べ替えることだと思いました。それから、私は迷っています。

私はこのような何かについて考えた：彼らはどこかにあるとしてリスト

から

1. テイクB要素は、それらを書く（それは3の葉です）
2. ブロックの最後の要素を取ります（最大）。
3. 親にB-1ルーティングキーが存在するまで、次の要素に対してステップ1を繰り返します。
4. 親にルーティングキーがある場合、それはフル。だから、N/Bブロックは基本的に

を読み取られるまで、このように起こっておいてください新しいルーティングキーは（そうツリーは1つのレベルを増大する）代わりに、「祖父」を行くと、すべての新しい葉が新しい親

を持っていますこの問題は、内部ノードが持つことができる子の最小数を考慮していないことです。たとえば、ノードが1つの子のみで終わることは明らかですが、これは間違いです。

私はどこにでも見えましたが、実際にはは、Θ(N/B * logM/B(N/B))にツリーを構築する方法を説明するアルゴリズムを見つけることができませんでした。私が見つけたのは、B因子を利用することなく、リスト内の各項目のツリーへの挿入が簡単なアルゴリズムです。

私を助けてくれますか、私に正しい方向を教えてもらえますか？

Answer 1

RAMのブロック数が一定以上のレベルを同時に使用して、すべてのレベルを同時にビルドするのではなく、最下位にレベルを構築すると思います（つまり、最初）。リストを与えられたら、それを貪欲にサイズBのブロックに分割します。ブロックが1つしかない場合は、それがルートです。それ以外の場合は、最後のブロックの要素数が少なすぎる場合は、その要素をできるだけ均等に2番目のブロックの要素のバランスを再調整します。どちらも十分な要素を持っています。次のリストは、このレベルの各ブロックの最後の要素で構成されます。