Reduced split/merge propagation in a modified B-link tree design

摘要

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.