We present an access method designed to provide a single integrated index structure for a versioned timestamped database with a non-deletion policy. Historical data (superceded versions) is stored separately from current data. Our access method is called the  Time-Split B-tree . It is an index structure based on Malcolm Easton's Write Once B-tree.  The Write Once B-tree was developed for data stored entirely on a Write-Once Read-Many or  WORM  optical disk. The Time-Split B-tree differs from the Write Once B-tree in the following ways:   Current data  must  be stored on an  erasable  random-access device.    Historical data  may  be stored on  any  random-access device, including WORMs, erasable optical disks, and magnetic disks. The point is to use a faster and more expensive device for the current data and a slower cheaper device for the historical data.    The splitting policies have been changed to reduce redundancy in the structure—the option of pure key splits as in B + -trees and a choice of split times for time-based splits enable this performance enhancement.    When data is migrated from the current to the historical database, it is consolidated and appended to the end of the historical database, allowing for high space utilization in WORM disk sectors.
['David Lomet', 'Betty Salzberg']
Access methods for multiversion data