Concurrency control and recovery for multiversion database structures
Tuukka Haapasalo, Ibrahim Jaluta, Seppo Sippu, Eljas Soisalon-Soininen · 2008
In modern database applications access to historical versions of the dataset is becoming increasingly important. Several multiversion structures with corresponding concurrency-control and recovery algorithms exist, but none of these have optimal logarithmic execution times for all actions in all situations. The time-split B+tree by Lomet et al. (TSBT) is used in the Immortal DB database prototype, but it does not consolidate pages. The multiversion B+tree by Becker et al. (MVBT) is an asymptotically optimal multiversion structure that guarantees logarithmic execution times for all actions, but it lacks concurrency-control algorithms.