Modeling and analysis of data base organization: The doubly chained tree structure

The doubly-chained tree data base (file) organization is modeled and analyzed to obtain estimates of average access time (read-only) and total storage requirements. Macroscopic expressions are derived relating such performance measures to characteristic parameters of the specific data base, query or transaction traffic, storage devices and particular doubly-chained storage structure chosen. Important and generally applicable implementation-oriented aspects are considered. The model forms part of a prototype system for automatically analyzing and evaluating various data base organizations. The methodology and system are briefly outlined. Results for the doubly-chained structure using several real data bases are summarized, showing the rather large variability of performance as a function of both data base contents and complexity of queries.