可持久化資料結構

在計算機編程中，可持久化資料結構（Persistent data structure）是一種能夠在修改之後其保留歷史版本（即可以在保留原來數據的基礎上進行修改——比如增添、刪除、賦值）的資料結構。這種資料結構實際上是不可變對象，因為相關操作不會直接修改被保存的數據，而是會在原版本上產生一個新分支。這個術語是在1986年Driscoll、Sarnak、Sleator和Tarjans的文章中提出的。

如果一個資料結構包括當前版本在內的所有歷史版本都可以被訪問，但只有當前版本可以被修改，那麼該資料結構就是部分可持久化資料結構。如果該資料結構的所有版本都可以被查詢或修改，那麼這種資料結構就是完全可持久化資料結構。如果存在能夠創建基於兩個歷史版本的新版本（即合併兩個版本 meld() （澆鑄（？）混合（？））或 merge() （合併）操作），那麼這種資料結構就是可匯合的可持久化資料結構。不可持久化的資料結構被稱為短暫性資料結構。

這些類型的資料結構在邏輯編程和函數式編程之中非常常見。

部分可持久化與完全可持久化

在部分可持久化模型中，編程者可以查詢該類資料結構的任一歷史版本，但是只能修改（更新）最新版本。這意味著資料結構的每個版本之間是線性排序的。在完全持久化模型中，編程者可以查詢和修改（更新）該類資料結構的所有版本，在某些情況之下，允許查詢和或修改（更新）歷史版本的功能會削減，比如 Rope 資料結構就是如此。另外，如果一個資料結構除了完全可持久化外，還可以將同種資料結構的兩個版本合併成一個新的版本，且這個新版本仍然是完全持久化的，那麼這個資料結構就可以被稱為可匯合的持久化的。

保留歷史版本的方法

「Copy on Write」（寫入時複製）

創建可持久化資料結構的一種方式是使用平台提供的短暫資料結構（比如數組）來存儲資料結構中的數據，並對對於資料結構的任何更改使用複製整個資料結構的方式來記錄每次更改。這是一種效率低下的技術，因為每次寫入都必須複製整個資料結構，這使得對一個大小為 $n$ 的數組進行 $m$ 次修改時，出現最差情況下的時間複雜度為 ${\text{O}}(nm)$ 。

「Fat node」（胖節點）

「胖節點」的方法是將對於該節點的所有更改記錄在節點本身，但是在修改時不覆蓋節點上原來的數值。這就要求允許節點能任意「變胖」。換句話說，每一個胖節點都包含了與它的歷史版本的信息和指針欄位，同時還擁有任意數量的額外欄位值空間。每個額外的欄位值都有一個相關聯的欄位名和一個版本戳，它表示該節點在哪個版本中被更改和被改為值。此外，每個胖節點都有自己的版本戳，用於記錄該版本是在那個版本中被修改的。節點的版本戳的唯一目的是確保每個節點在被一個版本中的每一個欄位僅僅包含一個唯一的值。為了瀏覽結構，每個節點中每個原始欄位值的版本戳為零。

「胖節點」算法的時間複雜度

使用「胖節點」算法完成可持久化，每次修改需要 ${\text{O}}(1)$ 的空間：只需要存儲新數據。每一次修改都需要額外的 ${\text{O}}(1)$ 的時間來在歷史版本的結尾處存儲更改。這是均攤分析的（假設修改歷史存儲在一個可以擴大的數組之中）。在查詢時，必須遍歷整個結構以找到每個節點的正確的版本。如果要進行 $m$ 次修改，那麼每一次查詢操作都會遭到 ${\text{O}}(\log m)$ 的減速——這是在數組中尋找最近修改的版本造成的。

「Path copying」（路徑複製）

路徑複製算法，將即將被修改的點路徑上的所有節點克隆出一個新的。這些修改必須通過資料結構逐級連接：克隆而得的所有節點指向舊節點的指針必須被修改為指向新節點。這些修改會引起連鎖更改，直達根節點。