永続データ構造

2025年10月22日

永続データ構造

英語表記: Persistent Data Structure

概要

永続データ構造は、データ構造（リスト, スタック, キュー, ツリー）の分類の中でも、特に「特殊データ構造」に位置づけられる、非常に興味深い概念です。この構造の最大の特長は、一度構築されたデータに対して変更操作（要素の追加や削除など）を行った際、元の構造を一切破壊せず、変更部分のみを効率的に利用した新しいバージョンのデータ構造を生成することにあります。これにより、過去の任意の時点の状態にいつでもアクセス可能となり、データの「永続性」が保証されるのです。

詳細解説

永続データ構造が「特殊データ構造」として分類されるのは、それが基本的なデータ構造（リストやツリーなど）に「不変性（Immutability）」の特性を付与し、かつ効率的な方法で実現されているからです。通常のデータ構造では、リストの3番目の要素を書き換えると、元のリストは上書きされて失われてしまいます。しかし、永続データ構造では、この書き換え操作が新しいリストの生成として扱われます。

目的と不変性

この構造の主な目的は、データの不変性を徹底することです。不変性は、特に並行処理環境（マルチスレッド環境）において非常に重要となります。データが一度作成されたら二度と変更されないため、複数のスレッドが同時に同じデータを参照しても、競合状態（Race Condition）が発生する心配がありません。これは、プログラマにとって大きな安心材料となります。

構造共有（Structural Sharing）の仕組み

もし変更のたびにデータ構造全体をコピーしていたら、メモリ消費と処理時間が非現実的なものになってしまいます。永続データ構造が優れているのは、この問題を解決するために「構造共有（Structural Sharing）」という技術を採用している点です。

例えば、永続的な二分探索木を考えてみましょう。根（ルート）から葉まで、あるノードの値を変更したい場合、変更が必要なノードと、そのノードに至るまでの親ノード群だけを新しく作成します。変更の影響を受けない、ツリーの大部分のサブツリーについては、古いバージョンと新しいバージョンで同じノードを共有して再利用するのです。

この構造共有のおかげで、変更操作の計算量は、データ全体のサイズ（N）に比例するO(N)ではなく、変更点や深さに比例するO(log N)やO(1)（リストの先頭への追加など）に抑えられます。この効率性が、永続データ構造を実用的な「永続/純粋構造」たらしめている核心部分だと私は感じています。

永続性の種類

永続データ構造には、永続性の度合いによって主に二つの種類があります。

部分永続性 (Partial Persistence):
最新のバージョンのみが更新（変更）可能であり、過去のバージョンは参照することしかできません。履歴を参照する機能は提供しますが、過去を書き換えることは許されません。
完全永続性 (Full Persistence):
最新バージョンだけでなく、過去のどのバージョンに対しても変更を加え、そこから新しい履歴の流れ（ブランチ）を生み出すことが可能です。これは、バージョン管理システムにおける「フォーク」の概念と非常に近いです。

この分類を理解することで、データ構造がどのように状態を管理しているのか、その複雑な仕組みがよく見えてくると思います。

具体例・活用シーン

永続データ構造の概念は、私たちが日常的に利用するソフトウェアの裏側で、データの信頼性と効率性を支えています。

メタファー：図書館の蔵書管理

永続データ構造を理解するための良いメタファーは、「図書館の蔵書管理」です。

通常のデータ構造で蔵書リストを管理する場合、新しい本が入るたびに古いリストを修正し、上書きしてしまいます。しかし、永続データ構造を採用した図書館では、新しい本が追加される（または古い本が廃棄される）たびに、元の蔵書目録（過去の状態）はそのまま保管され、「本日の変更を反映した新しい目録」が作成されます。

変更のない書棚の情報は、古い目録と新しい目録で「共有」されています。もし利用者が「昨年の12月時点では、あの本はまだ蔵書にあったか？」と尋ねた場合、図書館員は古い目録を参照するだけで、現在の目録に影響を与えることなく、すぐに答えられるのです。この履歴を保ち続ける能力こそが、永続データ構造の真価です。

活用シーン

関数型プログラミング言語:
Haskell、Clojure、Scalaなどの関数型プログラミング言語では、副作用のない（状態を変更しない）プログラミングが基本です。そのため、内部のリストやマップといったコレクションは、永続データ構造として実装されていることがほとんどです。
バージョン管理システム（Gitなど）:
Gitのコミット履歴は、本質的に永続データ構造のツリー構造として扱われます。コミットごとにファイルシステムのスナップショット（ツリー）が作成されますが、変更のないファイルは前のコミットと共有されるため、非常に効率的に履歴が管理されています。
トランザクション管理:
データベースシステムにおいて、トランザクションのログや状態を管理する際に、過去の状態を確実に保持するために利用されることがあります。

資格試験向けチェックポイント

永続データ構造は、応用情報技術者試験や高度情報処理技術者試験において、データ構造の効率性や関数型プログラミングの文脈で出題される可能性があります。

最重要キーワードは「構造共有」:
永続データ構造が、データ全体をコピーせずに効率的に新しいバージョンを作成できる理由を問われた場合、「構造共有（Structural Sharing）」が答えとなります。これは、メモリ効率と処理速度を両立させるための鍵です。
不変性との関連:
「不変性（Immutability）」を保証し、特に並行処理において安全性を高める役割を理解しておきましょう。不変なデータ構造は、ロック機構なしに安全に共有できるというメリットがあります。
分類の確認:
この概念は「データ構造（リスト, スタック, キュー, ツリー）」という基本的な枠組みを基盤としつつ、その性質を拡張しているため、「特殊データ構造」に分類されます。この分類体系を意識することが、知識の整理に役立ちます。
計算量の違い:
通常の配列やリストではO(1)で可能な更新操作が、永続データ構造では新しいノードを構築する必要があるため、O(log N)やO(深さ)になることが多いです。この計算量のトレードオフを理解しているかが問われることがあります。