Positional access using a b-tree

Details Positional access using a b-tree Positional access using a b-tree

2006-10-10

2006-10-10

Gaffin, Jeffrey (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C711S170000

Reexamination Certificate

active

07120637

ABSTRACT:
A b-tree having information stored therein is utilized to facilitate positional access of elements stored in the leaves of the b-tree. The b-tree is structured such that for each non-leaf level value, a count is located to its immediate left and a value is located to its immediate right. These left and right counts indicate the number of leaf level values located in the leaves of the sub-trees to the immediate left and right of the value. The left and right counts are used to determine the path to take when descending the b-tree in search of a specific position. The counts can also be utilized to determine the total number of values in the leaf level of the b-tree.

REFERENCES:
patent: 5355473 (1994-10-01), Au
patent: 5613105 (1997-03-01), Zbikowski et al.
patent: 5878410 (1999-03-01), Zbikowski et al.
patent: 6553370 (2003-04-01), Andreev et al.
patent: 6735595 (2004-05-01), Gobeille et al.
patent: 1 211 612 (2002-06-01), None
Simon Tatham; Counted B-Trees: www.chiark.greenend.org.uk/˜sgtatham/algorithms/cbtree.html; May 4, 2001 (Earliest date in which the web page was published: Taken from Archive.org).
Dutton, G., “Handling Positional Uncertainty in Spatial Databases”,Proceedings, 5thIntl Symposium on Spatial Data Handling, 1992, 460-469.
“Counted B-Trees”, www.chiark.greenend.org.uk/˜sgtatham/algorithms/cbtree.html, 4 pages.
“The Art of Computer Programming”, 1988, vol. 3, 463-464, XP-002373347.

Affiliated with

Also associated with

Rating

Positional access using a b-tree does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Positional access using a b-tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Positional access using a b-tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3633714