Positional access using a b-tree

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

2006-01-26

2010-02-02

Jalil, Neveen Abel (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07657556

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: 5873118 (1999-02-01), Letwin
patent: 5878410 (1999-03-01), Zbikowski et al.
patent: 6553370 (2003-04-01), Andreev et al.
patent: 6711562 (2004-03-01), Ross et al.
patent: 6735595 (2004-05-01), Gobeille et al.
patent: 1211612 (2002-06-01), None
Jannink, Jan, “Implementing Deletion in B+ Trees,” Mar. 1995, SIGMOD Record, vol. 24, No. 1, pp. 33-38.
Freeston, Michael, “A General Solution of the n-dimensional B-tree Problem,” Jun. 1995, ACM SIGMOD '95 San Jose, CA, pp. 80-91.
Comer, Douglas, “The Ubiquitous B-Tree,” Jun. 1979, ACM, vol. 11, No. 2, pp. 1-17.
Bentley, Jon. “Multidimensional Binary Search Trees Used for Associative Searching,” ACM, vol. 18, No. 9, Sep. 1975, pp. 509-517.
Viana, Aline, et al, “Self-Organization in spontaneous networks: the approach of DHT-based routing protocols,” Sep. 15, 2004, ScienceDirect.com, pp. 1-18.
Yen, Chia Huang et al, “Solution of trim-loss problem by an integrated simulated annealing and ordinal optimization approach,” Feb. 2004, Journal of Intelligent Manufacturing, pp. 701-709.
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.
Tatham, S., “Counted B-Trees”, www.chiark.greenend.org.uk/˜sgtatham/algorithms/cbtree.html, May 4, 2001.

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-4213450