5

B ツリーについて読み、その入力、削除メソッドを理解しました。私はこのような紹介で読んだ：

ディスク上に構造を構築する場合、アクセス時間と転送時間の特定の現実に対処する必要があります。

  1. 通常、ディスクへのランダム アクセスでは、ヘッドを配置してデータがその下に来るのを待つために、10 ～ 20 ミリ秒程度のアクセス時間が必要です。
  2. ヘッドの位置が正しければ、1 秒あたり 100 万バイトを超える速度でデータを転送できます。
  3. 次に、さまざまなサイズのブロックで合計転送時間がどのように動作するかを観察します (かなり高速な 10 ミリ秒のアクセス時間と 1 メガバイト/秒の転送速度を想定)。

そのため、B ツリー データ構造はディスクから提供するように作られています (これが、データベースに最適な理由です)。しかし、実装しようとすると、この問題にぶつかりました。

通常の B ツリー ダイアグラムは、子ノードへのポインターを示しており、子ノードはリーフに下降します。

しかし、ディスク上にポインタを作成するにはどうすればよいでしょうか? ファイル名のようなものですか？

4

2 に答える 2

6

オンディスク ポインタはoffsets、ファイルの先頭からのものです。

あなたがアドレスnkeyを指している場合、それはそれを意味します

  1. データファイルを開く
  2. nバイトを読み取りますが、それらを破棄します(または単にそれらを飛び越えます。これはシークと呼ばれます。方法については以下を参照してください)。
  3. 興味のあるデータの読み取りを開始します。

今、最適化として、

  1. プログラムの開始時など、データファイルはすでに開いている可能性があります。もちろん、部分的にメモリにキャッシュすることもできます。
  2. バイトを読み取って破棄するのではなく、ファイル内の特定の場所に移動するようフレームワークに具体的に指示できます。ほとんどの言語にはその機能があります。すべての OS が行います。これをシークと呼びます。のようなメソッドを呼び出しますfile.seek(1024)。ジャンプを実行するには、OS は、探しているデータがディスク内のどのポイントにあるかを認識している必要があります。これにはさらにルックアップとディスクの移動が必要ですが、それはすべて OS によって行われます。
  3. データの読み取りを開始できますが、いつ停止するかを知るには、固定幅のレコードを使用するか、レコードの最初の 4 バイトにレコード長を入れることができます。これによりheaders、複雑さとともに成長するメタデータが作成されます。

key興味深いのは、各ポイントにleft関連付けられたポインターright nodesがデータを格納する場所がないことです。したがって、教科書の例では

struct node {
    int key;                      //this generally is the primary key of the table
    node left;
    node right;

    long offsetOfDataInDataFile;  // <----------- we need to add this line.
}

nodeこの方法では、最初に で を見つけますtree。次に、 を見つけますkey。そこでoffset実際のデータを取得します。データ ファイル内の場所に移動し、内容を読み取ります。

テーブルに複数のインデックスがある場合、またはテーブル内の各インデックスの場合、そのようなツリーを 1 つ維持する必要があります。そのkeyツリーの は、インデックス付けされた列の内容になります。

于 2013-10-02T09:33:39.690 に答える
5

B ツリーの「ポインター」は、シークできるファイル内の単なるオフセットです。または、ブロックサイズを固定する場合は、シークする前にブロックサイズを掛けたブロック番号である可能性があります。

于 2013-10-02T08:18:33.860 に答える