영속 자료 구조(영어: persistent data structures)는 변경이 가해질 때 이전의 모든 상태에 대한 접근을 유지하는 자료 구조입니다.
영속에는 몇 가지 「수준」이 있습니다:
- 부분 영속성 — 모든 버전에 쿼리를 수행할 수 있지만, 수정할 수 있는 것은 마지막 버전뿐입니다.
- 완전 영속성 — 모든 버전에 쿼리를 할 수 있고 모든 버전을 수정할 수 있습니다.
- 합류적(confluent) — 이에 더해 두 자료 구조를 하나로 합칠 수 있습니다(예를 들어 힙이나 탐색 트리를 병합할 수 있습니다).
- 함수형(functional) — 자료 구조를 순수 함수형 언어로 구현할 수 있습니다. 즉, 어떤 변수에든 값은 단 한 번만 할당될 수 있으며 변수의 값을 변경할 수 없습니다.
영속 자료구조는 텍스트 편집기, 버전 관리 시스템, 데이터베이스, 일부 병렬 알고리즘, 그리고 함수형 프로그래밍에서 사용됩니다.
이 외에도 영속 구조는 「일반적인」 알고리즘 문제를 해결하는 데에도 자주 사용되며, 이것이 바로 이 장의 주요 초점입니다.