Algorithms and data structures for the implementation of a relational database system
Jack A. Orenstein · 1983
The problems of implementing a relational database are considered. In part 1, a new class of data structures for processing range queries is described. A member of this class is derived from a data structure which supports random and sequential accessing. We also describe two new data structures with this property that seem to have better performance than the Btree. In part 2, a new design for the physical database is proposed. This design is based on the separation of a relation into two parts: a static master file and a dynamic differential file which stores updates. Our design includes a new system for recovering from system failures and allows greater concurrency than is possible with existing systems.