About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
In this paper, we study the problem of maintaining a file in magnetic bubble memories. A memory structure with a special loop ordering scheme is proposed, in which records are stored in a balanced tree form. Algorithms for searching, insertion, and deletion areproposed. They have the property that, after each operation, the file is restored to a balanced tree form. The searching operation takes time log22 n/(2 log2 log2 n) + O(log2 n) where n is the number of records in the file, while insertion and deletion take additional log2 n + O(1) time each. This scheme, however, requires that each switch be individually settable. In the latter part of the paper, the memory is slightly modified, and a new loop ordering scheme proposed. With only two controloperations, we show that searching, insertion, and deletion of records in the tree can still be done although the tree can no longer be kept in balanced form. If the tree is balanced, then searching, insertion, and deletion take only 5/2 log2 (n + 1) + O(1) time each. Copyright © 1980 by The Institute of Electrical and Electronics Engineers, Inc.