Technical Report CS0621

Authors: G. Mats1iach and o. Shmue1i
Abstract: A Bounded Disorder file [9] [11] is a mechanism for maintaining files in traditional. systems. It guarantees good performance for single-key operations (e.g. search, insert, and delete), similar to that of hash based methods, and in addition, good performance for subrange operations, and reasonable performance for sequential-key operations (Le. subrange operations for which the output must be produced in key order). To obtain these capabilities, some main memory space is required. In this paper, we consider the problem of maintaining Bounded Disorder files in multiprocessor multi-disk systems which consist of P processor-disk pairs. The processors are either tightly coupled (communicate via shared memory) or loosely coupled (communicate via a local network). The straightforward solution is to equally partition the file records among processors, each of which maintains its part as a "local" Bounded Disorder file (stored in the processor's main memory and disk). This method is highly parallel (up to P single-key operations can be executed in parallel) and achieves good performance due to the use of Bounded Disorder files. We present an alternative method, called Conceptual Bounded Disorder file, whose major advantage is its very low consumption of main memory space. More specifically, depending on implementation details, the saving in main memory space (in comparison with the Bounded Disorder files used in the straightforward solution) may range from 41* K~Pt,. *100% to 41*100%, where P is the number of processors, K in the key size, and ptr is the size of a pointer that points to a disk page. This significant cut down in main memory space consumption has no negative effect on performance and parallel execution capabilities; sometimes performance is even improved.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion