Method to Minimize Buffer Requirements in a Sort/Merge Task
Original Publication Date: 1987-Apr-01
Included in the Prior Art Database: 2005-Feb-01
A method is described which allows allocation of the minimum number of buffers (less than the total available) that can be used without causing an additional merge pass through the data file. The program using this method provides a capability to build lists of field-oriented data, retrieve them, and to sort them on compound data-type keys. Functions are also provided, while reading list data, to allow sequences of records to be accessed repetitively by marking the beginning and end point of the sequence and allowing the user to reposition the read cursor to the beginning of the marked sequence. As records are inserted into the (sorted) list, they are placed in a buffer or buffers. In addition, a record descriptor is inserted in a (Image Omitted) balanced binary sort tree (Fig. 1).