B tree structure and method

Details B tree structure and method B tree structure and method

1996-03-14

1998-09-22

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

G06F 1730

Patent

active

058130004

ABSTRACT:
A novel B tree data structure is taught and implemented for use in conjunction with a tertiary storage system. The tertiary storage system utilizes three levels of memory hierarchy: primary memory, such as RAM; read-write secondary storage, such as disk memory; and lower speed, and less expensive mass storage, for example a CD-ROM. A novel B tree is utilized to access data stored in two or more types of memory, such as a CD-ROM memory and a disk drive memory, and adapts for the provision of updated data stored on the hard disk which either replaces or supplements data stored on the CD-ROM. The B tree includes, for each data bucket, a pointer for both a CD-ROM and a disk drive location, and are, in certain embodiments, used in conjunction with a bit mask to indicate the presence of valid data in a first one of the memories, such as CD-ROM, and, if desired, a bloom filter associated with data stored in the second memory type, such as a magnetic disk, in order to speed accesses. The B tree of this invention is capable of being split, as needed, when entries are inserted into memory.

REFERENCES:
patent: 4827419 (1989-05-01), Selby, III
patent: 4974197 (1990-11-01), Blount et al.
patent: 4987533 (1991-01-01), Clark et al.
patent: 5040110 (1991-08-01), Miki et al.
patent: 5222235 (1993-06-01), Hintz et al.
patent: 5276867 (1994-01-01), Kenley et al.
patent: 5287473 (1994-02-01), Mohan et al.
patent: 5408630 (1995-04-01), Moss
patent: 5446857 (1995-08-01), Russ
patent: 5454101 (1995-09-01), Mackay et al.
"The UiniTree Virtual Disk System An Overview", General Atomics/DISCOS Division, pp. 1-25, Dec. 1991.
A Dynamic Storage Allocation Algorithm Suitable for File Structures, Information Systems, vol. 15, No. 5, pp. 515-521, 1990 Barza-Yates.
Space/Time Trade-off in Hash Coding with Allowable Errors, Burton H. Bloom Cummunications of the ACM, vol. 13, No. 7, Jul. 1970.
File Organizations and Access Methods for CLV Optical Discs, Christodoulakis et al. Dept of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Jun. 1998.
An Analysis of B-Trees and Their Variants, Chu et al., Information Systems, vol. 14, No. 5, pp. 359-370, 1989.
The Ubiquitious B-Tree, Computing Surveys, vol. 11, No. 2, Jun. 1979, Douglas Comer.
Bit-Tree: A Data Structure for Fast File Processing, David E. Ferguson, Communications of the ACM/Jun. 1992/vol. 35, No. 6, pp. 116-120.
Adaptive Hasing, Hsiao et al., Information Systems, vol. 13, No. 1, pp. 111-127, 1988.
The Art of Computer Programming, vol. 3, Searching and Sorting, pp. 473-479, 1973.
A New Method for Fast Data Searches with Keys, IEEE Software, pp. 16-24. Letwter, et al., 1987.
A Quasi-distributed Architectire for Database Management Systems, A. Tharp, Computer Science Department, North Carolina State University, Raleigh, N.C. 1989.
B+ Trees, Bounded Disorder and Adaptive Hashing, Tharp et al., Information Systems, vol. 16, No. 1, pp. 65-71, 1991.
CD-ROM Reaches for Critical Mass, Lee The', Datamation, 1992, pp. 47-50.

Affiliated with

Also associated with

Rating

B tree structure and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with B tree structure and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and B tree structure and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1635165