Appeal No. 2002-1758
Application No. 09/121,791
for storing the new entry, the parent page must split also. The parent page split is performed by
allocating a new page at that level and then both pages, old and new parents, are marked as
undergoing split. The system still obtains address locks for these pages but, at this point, a side
entry is created in the old parent page. This information lets any client searching for a key value
know that, instead of going directly down the tree from the old parent page, it should proceed to
the parent’s new sibling node or page.
As explained, at page 5 of the specification,
...the traversal is not blocked by the split which is currently active. In
effect, the client knows how to take a detour to arrive at the proper leaf-level
page. Similarly, if the client is searching for a lesser key value, it will
traverse to the proper page, without being blocked. Again, even though
the page is undergoing a split, the client is not blocked from accessing the
sought-after key value. 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.
The key elements of allocating a new page “at a level in the B-Tree which is the same as
the existing page and marking both pages as undergoing a split” and “creating a reference in the
existing page which points to the new page, so that any client which is traversing the B-Tree will
not be blocked by the split which is currently occurring” are clearly set forth in instant
independent claim 1. Independent claim 21 clearly sets forth that the means for inserting a new
key value includes “means for splitting the existing page into the existing page and a new page,
said new page being at a level in the B-Tree which is the same as the existing page” and claim 21
-4-
Page: Previous 1 2 3 4 5 6 7 8 9 10 Next
Last modified: November 3, 2007