Reorganization in Persistent Object Stores

TitleReorganization in Persistent Object Stores
Publication TypeTechnical Report
Year of Publication1997
AuthorsSalama, R., Wegner L., & Thamm J.
Other Numbers1089
Keywordscomplex objects, file reorganizations, persistent storage, pointer swizzling

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. It can even be combined with pointer swizzling. Although simple in principle, its details are tricky and little has been released to the public. 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, pages can be deleted physically, but not logically. Therefore, there must be a mapping from "old" to "new" page numbers. If the self-contained nature is to be preserved, this is not to be achieved by a table but rather through some arithmetical "folding" similar to hashing schemes. Page numbers are meant to collide creating merged pages. The paper explains in detail an efficient division-folding method where f adjacent pages are merged into one

Bibliographic Notes

ICSI Technical Report TR-97-023

Abbreviated Authors

R. Salama, L. Wegner, and J. Thamm

ICSI Publication Type

Technical Report