永続データ構造（えいぞくデータこうぞう、英: Persistent data structure）は、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である。 全バージョンにアクセス可能で、最新版だけを変更可能なデータ構造を半永続的（partially persistent）という。全バージョンにアクセスも更新も可能なデータ構造を全永続的（fully persistent）という。最新版以外の2つのバージョンから新たなバージョンを作成/マージする操作があるなら、そのデータ構造を融合永続的（confluently persistent）という。永続的でないデータ構造は短命（ephemeral）であるという。 このようなデータ構造の分類は、特に論理プログラミングや関数型プログラミングで典型的である。純粋関数プログラムでは全てのデータがイミュータブルであり、全てのデータ構造が自動的に全永続的である。永続データ構造はデータをその場で更新する方法でも構築可能であり、一般に純粋関数での実装よりも記憶領域や時間を必要としない。 永続性は単に変更のたびにデータ全体をコピーすることでも達成できるが、多くの操作はデータ構造のほんの一部しか変更しないので、時間と領域の効率が悪い。よりよい手法は、木構造を使ってバージョン間の類似性を表す方法である。しかし、バージョンが増えるにつれてバージョン間でどの部分が共通なのかを判断することが難しくなり、古いバージョンを捨てられるのが望ましい場合も多いため、ガベージコレクションが可能な環境が必要となる。 最も単純な永続データ構造は片方向連結リストや cons ベースのリストである（リスト上の次のオブジェクトへの参照のある単純なリスト）。このようなリストの尾部を共有し、変更部分だけを先頭のノードとして新たに追加することで永続性を実現できる。尾部がコピーされることはなく、新しいリストと古いリストで共有される。尾部の内容がイミュータブルであれば、この共有は振る舞いとして現れない。 赤黒木やキューのような多くの参照ベースのデータ構造は、容易に永続版にすることができる。配列の永続版として Phil Bagwell が 2002年に示した VList
概要
関連項目
永続性 (計算機科学)
ナビゲーショナルデータベース
外部リンク
⇒Making Data Structures Persistent （または ⇒筆者のサイトにある版）
⇒Persistent Data Structures (survey)
⇒Fully persistent arrays for efficient incremental updates and voluminous reads
この項目は、ソフトウェアに関連した書きかけの項目です。この項目を加筆・訂正
などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。