En informática , una estructura de datos persistente o estructura de datos no efímera es una estructura de datos que siempre conserva la versión anterior de sí misma cuando se modifica. Estas estructuras de datos son efectivamente inmutables , ya que sus operaciones no actualizan (visiblemente) la estructura en el lugar, sino que siempre producen una nueva estructura actualizada. El término se introdujo en el artículo de 1986 de Driscoll, Sarnak, Sleator y Tarjans. [1]
Una estructura de datos es parcialmente persistente si se puede acceder a todas las versiones pero solo se puede modificar la versión más reciente. La estructura de datos es completamente persistente si se puede acceder a todas las versiones y modificarlas. Si también hay una operación de fusión o fusión que puede crear una nueva versión a partir de dos versiones anteriores, la estructura de datos se denomina persistente confluentemente . Las estructuras que no son persistentes se denominan efímeras . [2]
Estos tipos de estructuras de datos son particularmente comunes en la programación lógica y funcional , [2] ya que los lenguajes en esos paradigmas desalientan (o prohíben por completo) el uso de datos mutables.
En el modelo de persistencia parcial, un programador puede consultar cualquier versión anterior de una estructura de datos, pero solo puede actualizar la última versión. Esto implica un ordenamiento lineal entre cada versión de la estructura de datos. [3] En el modelo totalmente persistente, se permiten tanto las actualizaciones como las consultas en cualquier versión de la estructura de datos. En algunos casos , se puede permitir que se degraden las características de rendimiento de consultar o actualizar versiones anteriores de una estructura de datos, como ocurre con la estructura de datos de Rope . [4]Además, se puede hacer referencia a una estructura de datos como confluentemente persistente si, además de ser completamente persistente, se pueden combinar dos versiones de la misma estructura de datos para formar una nueva versión que aún sea completamente persistente. [5]
Un método para crear una estructura de datos persistente es utilizar una estructura de datos efímera proporcionada por la plataforma, como una matriz, para almacenar los datos en la estructura de datos y copiar la totalidad de esa estructura de datos utilizando la semántica de copia en escritura para cualquier actualización de los datos. estructura. Esta es una técnica ineficiente porque toda la estructura de datos de respaldo debe copiarse para cada escritura, lo que conduce al peor caso O (n · m) características de rendimiento para m modificaciones de una matriz de tamaño n. [ cita requerida ]
El método del nodo gordo consiste en registrar todos los cambios realizados en los campos de los nodos en los propios nodos, sin borrar los valores antiguos de los campos. Esto requiere que se permita que los nodos se vuelvan "gordos" arbitrariamente. En otras palabras, cada nodo graso contiene la misma información y punterofields como un nodo efímero, junto con espacio para un número arbitrario de valores de campo adicionales. Cada valor de campo adicional tiene un nombre de campo asociado y un sello de versión que indica la versión en la que se cambió el campo nombrado para tener el valor especificado. Además, cada nodo gordo tiene su propio sello de versión, que indica la versión en la que se creó el nodo. El único propósito de los nodos que tienen sellos de versión es asegurarse de que cada nodo solo contenga un valor por nombre de campo por versión. Para navegar por la estructura, cada valor de campo original en un nodo tiene un sello de versión de cero.