Appeal No. 2002-1758
Application No. 09/121,791
Reference is made to the brief and answer for the respective positions of appellants and
the examiner.
OPINION
We begin our analysis with a definition of B-tree structures. Since neither appellants nor
the examiner define this term, and its meaning is not precisely known from the applied
references, we look at the definition supplied by the National Institute of Standards and
Technology (NIST):
A balanced search tree in which every node has between [m/2]
and m children, where m>1 is a fixed integer. M is the order. The
root may as few as 2 children [sic]. This is a good structure if much
of the tree is in slow memory (disk), since the height, and hence the
number of accesses, can be kept small, say one or two, by picking a
large m. [Google internet search on March 2, 2004, at
http://www.nist.gov/dads/HTML/btree.html].
Appellants seek to provide high-concurrency access to B-tree structures. By way of
explanation, page 4 of the instant specification indicates that when the system receives a request
to insert a key value into a B-tree at a page that does not have sufficient room, the system must
split at the tree at leaf level. This is performed by allocating a new page and moving some of the
key values from the old page to the new page. The specification explains that the split itself
propagates upward and to do the split itself, the system must obtain address locks for the two
pages, marking both as undergoing “split”. The system would then add the address locks as a
linked list of address locks. When the split is propagated up, a “side entry” is added to the old
page to point to the newly allocated page and, since the old page may not have sufficient room
-3-
Page: Previous 1 2 3 4 5 6 7 8 9 10 Next
Last modified: November 3, 2007