US 5,813,000 A · B tree structure and method

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.

Claims18

Dependent claims

A data processing system for use with a computer having central processing unit and a memory system, said memory system having a first memory type and a second memory type where one of said memory types is a prerecorded read only memory, said data processing system comprising:

(A) a B tree structure for accessing data stored in said memory system, said B tree structure having non-terminal nodes and terminal nodes each of said terminal nodes including:
a plurality of keys each associated with corresponding data buckets stored within said memory system;
a plurality of first pointers, each said first pointer being associated with one of said keys of said B tree and corresponding to data stored in said first memory type;
and
a plurality of second pointers, each second pointer being associated with one of said keys of said B tree and corresponding to data stored in said second memory type;
and
(B) wherein said processor is configured to:
update said keys to associate each key with most recent data, wherein said update may associate a pointer with a different memory type;
locate within said B tree a key associated with a desired data bucket corresponding to desired data to be accessed;
determine if a first desired pointer exists indicating that said desired data bucket is stored in said first memory type and, if affirmative, to access said desired data from said desired data bucket within said first memory type;
and
when said processor determines that said first desired pointer exists is negative, to determine if a second desired pointer exists indicating that said desired data bucket is stored in said second memory type and, if affirmative, to access said desired data from said desired data bucket within said second memory type.

9 more elements

A method for accessing data from a memory system having a first memory type and a second memory type where one of said memory types is a prerecorded read only memory, said memory system employing a B tree having non-terminal nodes and terminal nodes, each of said terminal nodes including

a plurality of keys each associated with corresponding data buckets stored within said memory system;
a plurality of first pointers, each said first pointer being associated with one of said keys of said B tree and corresponding to data stored in said first memory type;
and
a plurality of second pointers, each second pointer being associated with one of said keys of said B tree and corresponding to data stored in said second memory type;
said method comprising the steps of:
updating said keys to associate each key with most recent data, wherein said updating step may associate a pointer with a different memory type;
locating within said B tree a key associated with a desired data bucket corresponding to desired data to be accessed;
determining if a first desired pointer exists indicating that said desired data bucket is stored in said first memory type and, if affirmative, accessing said desired data from said desired data bucket within said first memory type;
when said step of determining if said first desired pointer exists is negative, determining if a second desired pointer exists indicating that said desired data bucket is stored in said second memory type and, if affirmative, accessing said desired data from said desired data bucket within said second memory type.

6 more elements

A method of inserting a new record into a B tree using a memory system having a first read/write memory type and a second read-only memory type the B tree having non-terminal nodes and terminal nodes, each of the terminal nodes including;

a plurality of keys each associated with corresponding data buckets stored within the memory system;
a plurality of first pointers each the first pointer being associated with one of the keys of the B tree and corresponding to data stored in the first memory type and a plurality of second pointers each second pointer being associated with one of the keys of the B tree and corresponding to data stored in the second memory type the method comprising the steps of:
(a) setting a current node equal to a root node of the B tree;
(b) determining whether the current node is a data bucket;
(c1) if the current node is not a data bucket then retrieving a next given key in the current node and determining whether the given key is less than or equal to a node key
(c2) if the given key is less than or equal to the node key setting the current node equal to a left branch node and returning to step (b);
(c3) if the given key is not less than or equal to the node key determining whether there are any more keys in the node and if so returning to step (c1);
(c4) if there no more keys in the node, setting the current node equal to a right branch node and returning to step (b);
(d1) if the current node is a data bucket then ensuring that the terminal node has a pointer to a data bucket in said first memory and if not, allocating one;
(d2) determining if the data bucket has enough room for the new record and if so storing the new record in the data bucket;
(d3) if the data bucket does not have enough room for the new record allocating a new data bucket in said first memory type splitting an old data bucket moving a bottom half of data in the old data bucket into the new data bucket and selecting a middle key for insertion into a terminal node:
(d4) determining if the terminal node has enough room for one more key and if so, inserting the middle key into a sorted position in the terminal node updating the terminal node pointers to include the new data bucket and storing the new record in the new data bucket;
and
(d5) if the terminal node does not have enough room for one more key, allocating a new terminal node splitting on old terminal node, moving a bottom half of data in the old terminal node into the new terminal node, inserting the middle key into a non-terminal index, inserting the new key into the non-terminal index, inserting the middle key into its sorted position in the new terminal node, updating the new terminal node pointers to include the new data bucket and storing the new record in the new data bucket.

11 more elements

A method of retrieving a record from a B tree using a memory system having a first read/write memory type and a second read-only memory type, the B tree having non-terminal nodes and terminal nodes each of the terminal nodes including:

a plurality of keys each associated with corresponding data buckets stored within the memory system a plurality of first pointers each the first pointer being associated with one of the keys of the B tree and corresponding to data stored in the first memory type;
and a plurality of second pointers, each second pointer being associated with one of the keys of the B tree and corresponding to data stored in the second memory type the method comprising the steps of:
(a) setting a current node equal to a root node of the B tree;
(b) determining whether the current node is a data bucket;
(c1) if the current node is not a data bucket then retrieving a next given key in the current node and determining whether the given key is less than or equal to a node key;
(c2) if the given key is less than or equal to the node key setting the current node equal to a left branch node and returning to step (b);
(c3) if the given key is not less than or equal to the node key determining whether there are any more keys in the node, and if so returning to step (c1);
(c4) if there are no more keys in the node, setting the current node equal to a right branch node and returning to step (b);
(d1) if the current node is a data bucket determining whether the node has a corresponding first memory type data bucket;
(d2) if the current node does have a corresponding first memory type data bucket searching the data bucket for a record corresponding to the given key and if the record is located returning the located record, and if not moving to step (d3);
(d3) determining whether the node has a corresponding second memory type data bucket and if not, returning an unsuccessful search result;
(d4) if the node dots have a corresponding second memory type data bucket, determining whether the key has a corresponding bit representation in the Bloom filter and if not returning an unsuccessful search result;
and
(d5) if the node does have a corresponding bit representation in the Bloom filter searching the data bucket for the record corresponding to the given key and if found returning the located record and if not found returning an unsuccessful search result.

11 more elements

Dependencies are inferred from the claim text.

B tree structure and method

Life of this patent

B tree structure and method

Life of this patent

Abstract

Claims18