Appeal No. 2002-1758
Application No. 09/121,791
comprising a B-Tree having a root page, a plurality of internal
pages, and a plurality of leaf-level pages, each page storing one
or more key values from said data records, a method for providing
highly-concurrent access to the B-Tree for multiple clients, the
method of comprising:
(a) receiving a request from a client which requires insertion of a
new key value into the B-Tree in order to satisfy the request;
(b) traversing the B-Tree for locating an existing page in the B-
Tree appropriate for storing the new key value; and
(c) if said existing page does not contain sufficient room for
storing the new key value, splitting the existing page into two
pages by:
(i) 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,
(ii) moving some of the key values from the
existing page to the new page, and
(iii) 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.
The examiner relies on the following references:
Ishak et al. (Ishak) 5,475,837 Dec. 12, 1995
Roy 5,644,763 Jul. 1, 1997
Claims 1-30 stand rejected under 35 U.S.C. §103 as unpatentable over Roy in view of
Ishak.
-2-
Page: Previous 1 2 3 4 5 6 7 8 9 10 Next
Last modified: November 3, 2007