Как вращать двоичные деревья на диске

Я разрабатываю библиотеку дерева 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 ответ

  1. Диск не является подходящим носителем для AVL деревьев, потому что:

    1) Вы не можете прочитать только немного данных с диска. Вы всегда получите, по крайней мере, сектор, и вы можете получить немного больше бесплатно; и

    2) Чтение из произвольного положения на диске очень дорого.

    По этим причинам в дисковых деревьях поиска (например, в индексах баз данных) используются различные структуры данных. Дерево B+ является общим:

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

    Вы должны сделать что-то подобное вместо этого.

    Поиск элемента с дисковым деревом AVL займет примерно в 10 раз больше времени, чем поиск элемента с деревом B+.