Links

Tools

Export citation

Search in Google Scholar

Reorganization in Persistent Object Stores

Proceedings article published in 1997 by Reda Salama, Lutz Wegner, Jens Thamm
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

The Record Identifier (RID) storage concept was initially made popular through IBM' s System R. It remains in use for DEC' s Rdb and IBM' s DB2 and is attractive because of its self-contained nature. One particular problem is the reclamation of empty space when a RID-file becomes sparsely populated. Since RIDs, also called Tuple Identifiers (TIDs), are invariant by definition, empty pages can be deleted physically, but not logically. Therefore, there must be a mapping from "old" to "new" page numbers for which we propose some arithmetical "folding" similar to hashing schemes. Page numbers are meant to collide creating merged pages. The paper explains in detail an ef ficient division-folding method where f adjacent pages are merged into one. This process can be iterated should the load factor of the file continue to decrease. The algorithm is also designed for on-line and step-wise reor ganization whenever the system is idle. The paper closes with empirical data concerning the relationship between load factor before and after reorganization.