B tree structure and method

Claim 1

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.

Claim 6

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.

Claim 7

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 20

A method of storing and retrieving data using a computer having a processor, a read-only memory and a read/write memory, comprising the steps of: (A) creating a B tree of nodes interconnected having non-terminal nodes and terminal nodes; (B) in each terminal node: storing in a first pointer keys corresponding to data buckets stored in said read-only memory; storing in a second pointer keys corresponding to data buckets stored in said read/write memory; storing a third pointer to point to a sequential terminal node; setting a bit mask for each of said data buckets having a size corresponding to a number of records stored in a data bucket in said read-only memory and providing data regarding at least one of the presence and validity of records in said data buckets in said read-only memory; and storing data in a Bloom filter representing whether a specific record is stored in said read-only memory or in said read/write memory.

Claim 21

A method of storing and retrieving data using a computer having a processor, a read-only memory and a read/write memory, comprising the steps of: (A) creating a B tree of nodes interconnected having non-terminal nodes and terminal nodes; (B) in each terminal node: storing in a first pointer keys corresponding to data buckets stored in said read-only memory; storing in a second pointer keys corresponding to data buckets stored in said read/write memory; storing a third pointer to point to a sequential terminal node; setting a bit mask for each of said data buckets having a size corresponding to a number of records stored in a data bucket in said read-only memory and providing data regarding at least one of the presence and validity of records in said data buckets in said read-only memory; and storing data in a Bloom filter representing whether a specific record is stored in said read-only memory or in said read/write memory.