Persistent data structure 不可變數據結構
- 2022 年 10 月 16 日
- 筆記
- persistent data structure, 不可變數據, 計算機
持久性變數據不要和持久儲存相混淆
在計算機中持久性數據或非臨時數據是一種數據結構，在修改時始終保持其自身的先前版本。這些數據實際上是不可變的，因為對這類數據操作不會明顯的改變數據結構，而是始終產生新的數據結構。
部分持久性數據：如果可以訪問某個數據所有版本，但只能修改最新的版本，則數據是部分持久的。
匯合持久性數據：如果可以從之前的兩個數據版本通過合併或者融合，可以創建一個新版本數據，則數據是匯合持久的。
數據結構不是持久的則稱之為臨時的。
持久性數據結構在邏輯編程和函數式編程中特別常見，因為這些範式中的語言不鼓勵或者完全禁用可變的數據結構。
部分持久和完全持久
在部分持久數據結構中，開發者可以查看任意的之前的版本，但只能更新最新版本，這意味着數據結構每個版本之間呈線性排序的。
在完全持久數據中，可以在任何版本的數據上進行更新和查詢。
複製後重寫
創建持久數據結構的一種方法是使用平台提供的臨時數據結構（如數組）將數據存儲在數據結構中，並使用寫入時複製語義複製整個數據結構，以便對數據結構進行任何更新。這是一種低效的技術，因為每次寫入都必須複製整個後備數據結構，從而導致對大小為 n 的數組進行 m 次修改的最壞情況 O（n·m） 性能特徵。
擴展節點
擴展節點方法是在節點本身中記錄對節點字段所做的所有更改，而不擦除字段的舊值。這就要求允許節點變得任意「胖」。換句話說，每個節點都包含與臨時節點相同的信息和指針字段，以及任意數量的額外字段值的空間。每個額外的字段值都有一個關聯的字段名稱和一個版本標記，該標記指示命名字段更改為具有指定值的版本。此外，每個節點都有自己的版本標記，指示創建節點的版本。具有版本戳的節點的唯一用途是確保每個節點每個版本的每個字段名稱僅包含一個值。為了在結構中導航，節點中的每個原始字段值都有一個零的版本戳。
路徑重聯
使用路徑複製方法，將在路徑上創建所有節點的副本，以指向即將修改的任何節點。然後，這些更改必須通過數據結構級聯回來：必須將指向舊節點的所有節點修改為指向新節點。這些修改會導致更多的級聯更改，依此類推，直到到達根節點。
上述兩種的結合方式
在每個節點中，存儲一個修改框。此框可以保存對節點的一次修改（對其中一個指針的修改，或者對節點的鍵的修改，或者對某個其他特定於節點的數據的修改），以及應用該修改時的時間戳。最初，每個節點的修改框都是空的。每當訪問節點時，都會選中修改框，並將其時間戳與訪問時間進行比較。（訪問時間指定要考慮的數據結構的版本。)如果修改框為空，或者訪問時間早於修改時間，則忽略修改框，只考慮節點的正常部分。如果訪問時間晚於修改時間，則使用修改框中的值，覆蓋節點中的該值。
修改節點的工作方式如下所示。（假定每個修改都涉及一個指針或類似字段。)如果節點的修改框為空，則用修改填充該框。否則，修改框已滿。將創建節點的副本，但僅使用最新值。修改直接在新節點上執行，無需使用修改框。（新節點的某個字段將被覆蓋，其修改框將保持為空。) 最後，此更改將級聯到節點的父級，就像路徑複製一樣。（這可能涉及填寫父級的修改框，或以遞歸方式製作父級的副本。如果節點沒有父節點（它是根），則會將新根添加到排序的根數組中。
使用此算法，給定任何時間t，在時間t的數據結構中最多存在一個修改框。因此，時間 t 的修改將樹拆分為三個部分：一部分包含時間 t 之前的數據，一部分包含時間 t 之後的數據，一部分不受修改的影響。
