Estructuras de datos persistentes

En computación, una estructura de datos persistente es una estructura de datos que siempre preserva sus versiones anteriores, después de ser modificada. Este tipo de estructura son objetos inmutables, ya que sus operaciones no modifican la estructura actual, en su lugar se crea una nueva estructura modificada. (Una estructura de datos persistente no es una estructura que almacena su información en un medio persistente, como un disco duro; aquí se utiliza un significado distinto de la palabra ""persistente."")Una estructura es parcialmente persistente si se puede acceder a todas sus versiones, pero solo se puede modificar la última. Una estructura es completamente persistente si todas las versiones pueden ser accedidas y modificadas. Si también existe la posibilidad de mezclar dos versiones de la estructura, se dice que esta es confluently persistent. Las estructuras que no son persistentes son llamadas transitorias.Este tipo de estructuras son comunes particularmente en programación lógica y programación funcional. En un lenguaje de programación puramente funcional todos los datos son inmutables, así que todas las estructuras son completamente persistentes.La persistencia se puede lograr simplemente copiando las estructuras completas, pero esto puede ser muy ineficiente en cuanto a cálculos del CPU y consumo de memoria RAM, debido a que generalmente solo se hacen pequeños cambios. Lo mejor sería explotar la similitud que existe entre la nueva versión y sus versiones anteriores, y compartir parte de su estructura con ellas, como por ejemplo, utilizar algunos sub-árboles que no se modificaron para el caso de las estructuras formadas por árboles. De todas formas, debido a que rápidamente se vuelve no factible determinar cuantas versiones anteriores comparten partes en común con la estructura actual y a que a veces se hace necesario descartar versiones anteriores, es necesario contar con recolector de basura.