În calcul , o structură de date persistentă este o structură de date care își păstrează versiunile anterioare la schimbare; o astfel de structură este imuabilă, deoarece operațiunile sale nu o modifică pe loc (într-un mod vizibil), ci dimpotrivă returnează noi structuri.
O structură este parțial persistentă dacă doar cea mai recentă versiune a acesteia poate fi modificată, celelalte fiind accesibile doar pentru citire. Se spune că structura este complet persistentă dacă fiecare dintre versiunile sale poate fi citită sau modificată. Dacă există o operațiune care permite fuzionarea a două versiuni anterioare, se spune că structura este confluentă . Se spune că structurile care nu sunt persistente sunt efemere .
Acest tip de structură de date este deosebit de comun în programarea logică și funcțională . Într-un program pur funcțional, unde toate datele sunt imuabile, structurile de date sunt automat complet persistente. Structurile persistente pot fi, de asemenea, obținute prin utilizarea modificărilor în loc ale datelor și, prin urmare, pot fi uneori mai eficiente, în timp sau spațiu, decât omologii lor pur funcționali.
Deși persistența poate fi obținută printr-o copie simplă, aceasta este de obicei o soluție ineficientă în ceea ce privește timpul și spațiul, deoarece majoritatea operațiilor efectuează doar câteva modificări la structura datelor. O soluție mai bună este să exploatezi asemănările dintre versiunile vechi și cea nouă, cum ar fi subarborii obișnuiți într-o serie de structuri de copaci . Deoarece devine rapid dificil să se determine ce părți ale structurii sunt de fapt partajate între mai multe versiuni și, deoarece este deseori de dorit să ștergeți versiunile care au devenit inutile, prezența unui colector de gunoi este necesară în mod natural.
Poate că cea mai simplă structură de date persistentă este o listă pur și simplu legată , în care fiecare articol conține o referință la următorul articol din listă. O astfel de structură este persistentă dacă operațiunile se limitează la extragerea unui sufix dintr-o listă, adică ultimele k elemente pentru un anumit k și la adăugarea de elemente noi la cap. Sufixul poate fi apoi partajat între lista veche și cea nouă, în loc să fie duplicat. Atâta timp cât elementele sunt imuabile, această partajare rămâne invizibilă.
Multe structuri de date, cum ar fi copaci sau cozi în două culori , pot fi ușor adaptate pentru a fi persistente. O versiune persistentă a structurii matrice este structura VList introdusă în 2002 de Phil Bagwell.