Maintaining Physical Sequentiality of Dynamic Key-Associative Key-Sequential Computer Files
Original Publication Date: 1988-Feb-01
Included in the Prior Art Database: 2005-Feb-14
A technique is described whereby a dynamic key-associative computer file is maintained so that at all times: a) records may be inserted and deleted, b) records can be found directly by key, and c) records may be accessed sequentially in key order, such that the file is physically sequential. The concept is an improvement over approaches which used file reorganization methods and which resulted in poor system performance. Most dynamic key-associative key sequential file structures, as used in very large memory computer systems, have the property that the leaf nodes of the file are split into multiple nodes when an overflow occurs, resulting in an unpredictable splitting order.