Are "skip deltas" unique to svn?
- by echinodermata
The good folks who created the SVN version control system use a structure they refer to as "skip deltas" to store the revision history of files internally. A revision is stored as a delta against an earlier revision. However, revision N is not necessarily stored as a delta against revision N-1, like this:
0 <- 1 <- 2 <- 3 <- 4 <- 5 <- 6 <- 7 <- 8 <- 9
Instead, revision N is stored as a delta against N-f(N), where f(N) is the greatest power of two that divides N:
0 <- 1 2 <- 3 4 <- 5 6 <- 7
0 <------ 2 4 <------ 6
0 <---------------- 4
0 <------------------------------------ 8 <- 9
(Superficially it looks like a skip list but really it's not that similar - for instance, skip deltas are not interested in supporting insertion in the middle of the list.) You can read more about it here.
My question is: Do other systems use skip deltas? Were skip deltas known/used/published before SVN, or did the creators of SVN invent it themselves?
