ディスク上のバイナリツリーを回転させる方法

Question

私はディスク上のavlツリーライブラリを設計しています。

ツリーの各ノードは次のとおりです。

struct node 
{ 
    int key; 
    unsigned char height; 
    int64 left; 
    int64 right; 
}; 

各ノードは作成時にファイルに保存されます。

左右のフィールドは、左右の子ノードが存在するファイル のファイルへのオフセットです。

これまでのところ、ツリーの回転を除いてすべて正常に動作します。

ノードがメモリ上にあった場合、次のようになります。

node* rotateright(node* p) 
{ 
    node* q = p->left; 
    p->left = q->right; 
    q->right = p; 
    fixheight(p); 
    fixheight(q); 
    return q; 
} 

ただし、メモリの代わりにファイルにオフセットを使用しています。

int64 rotateright(int64 p) 
{ 
    node q_node; 
    node p_node; 

    seek(fp,p*sizeof(node)); 
    read(fp,sizeof(node),&p_node); 

    seek(fp,p.left*sizeof(node)); 
    read(fp,sizeof(node),&q_node); 

    p.left=q_node.right; 

    // etc... 
} 

この機能は正しく動作しません。あなたは、ディスクからのデータのほんの少しを読み取ることができません

1）：ので

Answer 1

ディスクは、AVL木のための適当な培地ではありません。あなたはいつも少なくともセクターを手に入れます。あなたはもっと自由に少しでも多くを得ることができます。

2）ディスク上の任意の位置からの読み取りは非常に高価です。

これらの理由から、ディスクベースの検索ツリー（たとえば、データベースインデックスに使用される）では、異なるデータ構造が使用されます。 Bの+ツリーは一般的です：

https://en.wikipedia.org/wiki/B%2B_tree

あなたが代わりにそのような何かを行う必要があります。

ディスクベースのAVLツリーで項目を検索すると、B +ツリーで検索する場合の約10倍のアクセスになります。