IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 30, Number 3, Page 230 (1986)
Nontopical Issue
  Full article: arrowPDF   arrowCopyright info


Key-sequence data sets on indelible storage

by M. C. Easton
Methods for creating and maintaining key-sequence data sets without overwriting the storage medium are described. These methods may be applied to erasable or to write-once storage devices, and they are compatible with conventional device error-management techniques. All past values of data records are preserved in a data structure called a Write-Once B-Tree. Rapid random access is available to records by key value; rapid sequential access is available to records in key-sequence order. Moreover, queries requesting data as of a previous time are processed as rapidly as requests for current data. Access time is proportional to the logarithm of the number of current records in the database. Efficient methods for inserting, updating, and deleting records are described. Upper bounds for tree depth and for storage consumption are given and compared with results from simulation. It is concluded that, with rapidly improving storage technologies, indelible databases will become practical for many applications.
Related Subjects: Data, structures and accessing; Error detection and correction; I/O devices, systems, and technology; Storage (computer) devices and systems