DATA SEARCH AND STORAGE WITH HASH TABLE-BASED DATA STRUCTURES
First Claim
Patent Images
1. A method of searching a query key in a data storage, comprising:
- (a) Accessing, by a computer, a binary tree comprising a plurality of nodes,wherein at least one of the nodes is a root node, each node has no more than two child nodes, a left child node and a right child node, and at least one node that is not the root node has both child nodes, andwherein each node comprises a hash table to store one or more keys, all of which are greater than all keys stored in the left child node, if any, thereof, and are smaller than all keys stored in the right child node, if any, thereof;
(b) determining, starting at the root node, whether the query key is between the largest key and the smallest key stored in the node; and
(c) if the query key is greater than the largest key in the node, (i) repeating steps (b) and (c) at the right child node thereof or (ii) terminating the search if no right child node exists, thereby determining that the query key does not exist in the binary tree,if the query key is smaller than the smallest key in the node, (i) repeating steps (b) and (c) at the left child node thereof or (ii) terminating the search if no left child node exists, thereby determining that the query key does not exist in the binary tree,if the query key is not greater than the largest key and not smaller than the smallest key in the node, searching the node to (i) find the query key or (ii) determine that the query does not exist in the binary tree if the query key is not found in the node.
1 Assignment
0 Petitions
Accused Products
Abstract
Provided are computer devices and methods for improved data storage, indexing and search. The methods entail the use of hash tables incorporated into nodes of search trees so as to increase the capacity of the nodes and reduce the size of the tree; hence reducing the time to identify a node while searching in the tree. The hash tables are so structured to maintain the hierarchy of the search tree and speed up the search within the hash table.
-
Citations
14 Claims
-
1. A method of searching a query key in a data storage, comprising:
-
(a) Accessing, by a computer, a binary tree comprising a plurality of nodes, wherein at least one of the nodes is a root node, each node has no more than two child nodes, a left child node and a right child node, and at least one node that is not the root node has both child nodes, and wherein each node comprises a hash table to store one or more keys, all of which are greater than all keys stored in the left child node, if any, thereof, and are smaller than all keys stored in the right child node, if any, thereof; (b) determining, starting at the root node, whether the query key is between the largest key and the smallest key stored in the node; and (c) if the query key is greater than the largest key in the node, (i) repeating steps (b) and (c) at the right child node thereof or (ii) terminating the search if no right child node exists, thereby determining that the query key does not exist in the binary tree, if the query key is smaller than the smallest key in the node, (i) repeating steps (b) and (c) at the left child node thereof or (ii) terminating the search if no left child node exists, thereby determining that the query key does not exist in the binary tree, if the query key is not greater than the largest key and not smaller than the smallest key in the node, searching the node to (i) find the query key or (ii) determine that the query does not exist in the binary tree if the query key is not found in the node. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer system comprising a processor, memory and program code which, when executed by the processor, configures the system to:
-
(a) access a binary tree comprising a plurality of nodes, wherein at least one of the nodes is a root node, each node has no more than two child nodes, a left child node and a right child node, and at least one node that is not the root node has both child nodes, and wherein each node comprises a hash table to store one or more keys, all of which are greater than all keys stored in the left child node, if any, thereof, and are smaller than all keys stored in the right child node, if any, thereof; (b) determine, starting at the root node, whether the query key is between the largest key and the smallest key stored in the node; and (c) if the query key is greater than the largest key in the node, (i) repeat steps (b) and (c) at the right child node thereof or (ii) terminate the search if no right child node exists, thereby determining that the query key does not exist in the binary tree, if the query key is smaller than the smallest key in the node, (i) repeat steps (b) and (c) at the left child node thereof or (ii) terminate the search if no left child node exists, thereby determining that the query key does not exist in the binary tree, if the query key is not greater than the largest key and not smaller than the smallest key in the node, search the node to (i) find the query key or (ii) determine that the query does not exist in the binary tree if the query key is not found in the node.
-
-
9. A method of searching a query key in a data storage, comprising:
-
(a) accessing, by a computer, a hash structure in the storage, which hash structure comprises (1) a first array (O[m]) that comprises m keys where the keys are sorted in the first array, (2) a second array (E[m]) of at least the same size (m) as the first array, which second array comprises, at each position (i), hash value of the key (O[i]) located at the same position (i) in the first array with a hash function (hash_f), that is, E[i]=hash_f(O[i]), and (3) a third array (I[n]) having a size (n) that is larger than the size (m) of the first array, wherein the values (E[i]'"'"'s) in the second array (E) are non-negative integers, and wherein the third array comprises, at the E[i]th position, the position (i) of the key O[i] in the first array; (b) obtaining the hash value (h) of the query key with the hash function; (c) obtaining the value at position (h) of the third array, I[h]; and (d) locating the query key at position (I[h]) of the first array. - View Dependent Claims (10, 11, 12, 13, 14)
-
Specification