2

並べ替えられたデータセットがあり、シーケンシャル読み取りとランダムルックアップの両方に最適な方法でディスクに保存したい場合は、Bツリー（またはバリアントの1つが適切な選択です）のようです。 ..このデータセットがすべてRAMに収まるわけではないと仮定します）。

問題は、ページ分割を行わずに、ソートされたデータセットから完全なBツリーを構築できるかどうかです。ソートされたデータを順番にディスクに書き込むことができるようにします。

4

3 に答える 3

3

これらの仕様に合わせて「B+ツリー」を構築するのは簡単です。

  1. 分岐係数kを選択します。
  2. ソートされたデータをファイルに書き込みます。これは葉のレベルです。
  3. 次に高いレベルを作成するには、現在のレベルをスキャンして、k番目ごとの項目を書き出します。
  4. 現在のレベルのアイテム数がk以下になったら停止します。

k = 2の例：

0 1|2 3|4 5|6 7|8 9
0   2  |4   6  |8
0       4      |8
0               8

それでは、を探しましょう5。5二分探索を使用して、最上位レベル以下の最後の数値、またはを見つけます0。以下に対応する次に低いレベルの間隔を見てください0。

0       4

今4：

        4   6

今4再び：

        4 5

それを見つけた。一般に、j番目のアイテムは次のレベルの（j + 1）k-1のアイテムjkに対応します。葉のレベルを直線的にスキャンすることもできます。

于 2010-08-04T06:39:06.523 に答える
1

1回のパスでBツリーを作成できますが、最適な保存方法ではない場合があります。シーケンシャルクエリとランダムアクセスクエリの頻度によっては、シーケンシャルクエリを順番に保存し、バイナリ検索を使用してランダムアクセスクエリを処理する方がよい場合があります。

つまり、bツリーの各レコードが（m-1）個のキーを保持していると仮定します（ m > 2、バイナリの場合は少し異なります）。すべてのリーフが同じレベルにあり、すべての内部ノードに少なくとも（m --1）/2個のキーが必要です。高さkの完全なbツリーには（m ^ k-1）個のキーがあることがわかっています。合計n個のキーを保存するとします。kをm^k--1>nとなる最小の整数とします。ここで、2 m ^（k --1）-1 <nの場合、内部ノードを完全に埋め、残りのキーをリーフノードに均等に分散できます。各リーフノードは、（n + 1）の床または天井のいずれかになります。 --m ^（k-1））/ m ^（k-1）キー。それができない場合は、深さk-1のすべてのノードを少なくとも半分まで埋めて、各リーフに1つのキーを格納するのに十分であることがわかります。

ツリーの形状を決定したら、ツリーを順番にトラバースするだけで、キーを順番に所定の位置にドロップできます。

于 2010-08-03T21:53:26.203 に答える
0

最適な意味は、データの順序のないトラバースが常にファイル（またはmmapされた領域）を順方向にシークし、ランダムなルックアップが最小限のシークで実行されることを意味します。

于 2010-08-03T23:52:42.700 に答える