Importance

Loading Importance Indicators...

Abstract

A Client/Server Database System with improved methods for providing access to highly-concurrent data, such as of B-Tree data structures, is described. When the system receives a request to insert a key value into a B-Tree at page that does not have sufficient room, the system must split at the tree at the leaf level. This is done by allocating a new page, and moving some of the key values from the old page to the new page. The split itself propagates upward. To do the split itself, the system obtains address locks for the two pages, and marks both as undergoing 'split' (i.e., a split operation)--the system sets a Boolean flag or 'split bit' to 'true.' When the split is propagated up, a 'side entry' is added to the old page to point to the newly allocated page. The old page, however, may not have sufficient room for storing this new entry (e.g., when it is already full). Accordingly in such a case, the parent page must split also. This is done by allocating a new page, at that level. Both pages, old and new parents, are marked as undergoing split. As before, the system obtains address locks for these pages as well. At this point, a side entry is created in the old parent page. This information serves to let any client which is searching for key value (or greater) know that, instead of going directly down the tree from the old parent page, it should proceed to the parent's new neighboring page. In this manner, a client's traversal down the tree is not blocked by the split which is currently active. In effect, the client knows how to take a detour to arrive ultimately at the proper leaf-level page. After split propagation is complete, the system clears the split flags and releases address locks. Also at this point, the side entry is removed. Now, sufficient room now exists in the tree for inserting the key value.

Loading the Abstract Image...

First Claim