# 概述

用到的资料包括：

• 课程主页: 6.851: Advanced Data Structures
• 课程视频: 【MIT 公开课】6.851 高级数据结构（完结・中英字幕・机翻)

# 计算模型

数据结构的讨论基于 pointer machine 模型。该模型包括一个根节点 (root), 合法的操作包括

• 新建节点 x = new node
• 域查找 look up fields x = y.field
• 域设置 set up fields x.field = y
• 基本计算 x = y+z etc.

其中， x, y 是根节点的域。删除节点的操作暂时不讨论。

# Temporal DSs

• persistence 持续性
• retroactivity 可回溯性

# persistence

# general goals

• keep all versions of DS
• all Op.s are relative specified versions
• update makes and returns new versions

# 4 levels

• partial persistence model
  • only allowed update latest version (version are linear ordered)
  • can query old versions
• full persistence model
  • can update any version (generate a branch)
  • versions form a tree
• confluent persistence model
  • can combine two versions to create a new versions
  • versions form a DAG
• functional:
  • never modify nodes
  • only make new nodes
  • eg: search tree

# Partial Persistence