Хронологические деревья: способы представления в памяти

Abstract

Хронологические структуры данных используются для того, чтобы обеспечить хранение всех исторических состояний определенной структуры данных и быстрый доступ к ним. В настоящей работе рассматривается, как эффективно сделать хронологической такую важную на практике структуру данных, как дерево «левый ребенок - правый брат». Для хранения таких хронологических деревьев предлагается использовать реляционные таблицы особого вида. Предложен алгоритм восстановления хронологического дерева из таких таблиц за один проход.

Persistent data structures are widely used to store all historical states of some data structure and to provide a quick access to all these states. In this paper we show how to make persistent the "Left Brother/Right Child"-tree. A specific relational structure is proposed to store such persistent trees in a RDBMS. We propose an algorithm which allows one to restore a persistent tree from such a relational table in a single passage.