Reduced split/merge propagation in a modified B-link tree design
Issue title: Special Supplement Issue in Section A and B: Selected Papers from the ISCA International Conference on Software Engineering and Data Engineering, 2010
Affiliations: Department of Computer Science, Arkansas State University, Jonesboro, AR, USA. Tel.: +1 870 9723978; Fax: +1 870 9723950; E-mail: e.t.hammerand@cs.astate.edu, suh@cs.astate.edu | Department of Computer Science, Winona State University, Winona, MN, USA
Abstract: For concurrent database access, the B-link tree is a well-suited data structure; this paper describes a modification of the B-link tree to reduce the expense associated with splits and merges while moving down the tree. The modification is keyed to the concept of stability in each B-link tree node. Being stable amounts to a node having somewhere between a small percentage more than the minimum number and a small percentage fewer than the maximum number of child links such a node may have. When additions or deletions lead to instability in a node, either an overflow or underflow is considered to be imminent. Upon visiting a node, an update process will determine if the node's content is at the B-link maximum or minimum; if this is the case, the process performs whatever split or merge and redistribution operations necessary to make this and any related node stable. As a result of this action, there will always be room for an overflowed child to insert an entry in its parent and likewise room for an underflowed child to remove an entry from its parent; backward propagation of insertions or deletions further up the B-link tree are thus eliminated, improving the possible degree of concurrency. Further, no node will be left without a parent, obviating horizontal traversal within the tree in all but highly infrequent process scheduling scenarios.
