Wie binäre Bäume auf der Festplatte zu drehen

Question

Ich entwerfe eine on-Festplatte nur Avl-Baum-Bibliothek.

Jeder Knoten des Baumes ist wie folgt.

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

und jeder Knoten, wenn er erstellt wird, in einer Datei gespeichert wird.

Die linken und rechten Felder sind ein Offset in die Datei , in der sich die linken und rechten untergeordneten Knoten befinden.

Bis jetzt funktioniert alles gut, außer wenn es um Baumrotationen geht.

Wenn Knoten im Speicher waren, ist die Rotation wie folgt.

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

Allerdings verwende ich Offsets in eine Datei anstelle von Speicher.

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... 
} 

Ich kann diese Funktion nicht richtig funktionieren.

Answer 1

Datenträger ist kein geeignetes Medium für die AVL-Bäume, denn:

1) Sie nicht nur ein wenig von Daten von der Festplatte gelesen werden können. Du wirst immer mindestens einen Sektor bekommen, und du kannst ein bisschen mehr umsonst bekommen; und

2) Lesen von einer beliebigen Position auf der Festplatte ist sehr teuer.

Aus diesen Gründen verwenden plattenbasierte Suchbäume (z. B. für Datenbankindizes) unterschiedliche Datenstrukturen. Die B + Baum ist gemeinsam:

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

Sie sollten stattdessen so etwas tun.

Wenn Sie ein Objekt mit einem festplattenbasierten AVL-Baum suchen, benötigen Sie etwa 10 Mal so viele Zugriffe wie bei einem B + Baum.