Esiste un modo per implementare un metodo di attraversamento veloce degli alberi che supporti il versioning datato?

6

Ho un catalogo al lavoro e voglio risvegliarlo un po 'perché sono stanco di essere estremamente lento. Vorrei supportare il metodo di archiviazione trasversale degli alberi preordinati modificato per l'albero delle categorie del catalogo, ma dovrei supportare il versionning precedente.

Ho pensato di creare versioni di alberi in base alle date, quindi non appena qualcosa cambia, creo una copia dell'albero alla data corrente e poi creo le mie modifiche. Ma il problema è che un'importazione di un catalogo che si verifica ogni notte creerebbe, a lungo raggio, una tabella estremamente pesante di elementi di attraversamento degli alberi. In combinazione con il fatto che un utente potrebbe andare e modificare una data in qualsiasi momento nell'amministratore, potrebbe quindi generare nuovamente un'altra versione ad albero.

La maggior parte dei nostri cataloghi è composta da 100-250 categorie, quindi alcune versioni non creerebbero più di qualche migliaio di elementi, ma mischiarlo a un anno di operazione, che potrebbe facilmente arrivare a 90000 voci solo per archiviare il albero che può cambiare.

Quindi la mia domanda è questa:

Esiste un modo per implementare un metodo di attraversamento rapido degli alberi (preferibilmente preorder modificato con colonne sinistra e destra) che supporterebbe il versioning datato?

    
posta Mathieu Dumoulin 14.02.2012 - 20:33
fonte

1 risposta

1

tentativi persistentemente coerenti per un controllo efficiente delle versioni
link

We consider a data-structural problem motivated by version control of a hierarchical directory structure in a system like Subversion. The model is that directories and files can be moved and copied between two arbitrary versions in addition to being added or removed in an arbitrary version. Equivalently, we wish to maintain a confluently persistent trie (where internal nodes represent directories, leaves represent files, and edge labels represent path names), subject to copying a subtree between two arbitrary versions, adding a new child to an existing node, and deleting an existing subtree in an arbitrary version.

    
risposta data 16.02.2012 - 01:50
fonte

Leggi altre domande sui tag