Patent US5418947A successfully refreshed from Google Patents.
US5418947A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Locating information in an unsorted database utilizing a B-tree
Assignee: AT&T Inc
•
Filing: 1992-12-23
•
Granted: 1995-05-23
•
Expires: 2012-12-23
Abstract
Abstract A binary search tree is created having a plurality of linked tree nodes, each of which store a key generated using a predetermined hashing function for each record in a database based upon a predetermined set of fields of each record. Tree nodes consist of such keys and the address of the corresponding record. The keys are arranged on the tree relative to the numerical value of keys previously entered in the tree. To locate a particular record, the key is generated for the record and the tree is traversed to locate a tree node having an identical key value. The address stored with the matching node in the tree is utilized to access the record.
Inventors
- 👤 Gordon K. Hsu
- 👤 Liheng M. Su, deceased
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 07:14
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/42; H04Q3/47; G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; G06F16/9027; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
287 words
In a telecommunications switching system having a database that stores records containing operating parameters, a method for locating a certain record in the database comprising the steps of: generating a key for each record using a hash function based on data in a predetermined set of fields in each record; creating and storing a search tree having a plurality of linked tree nodes, each tree node comprising one of said keys and an address of a corresponding record, said keys arranged on the tree relative to the numerical value of keys previously entered in the tree; generating a certain key corresponding to said certain record to be located in the database using said hash function based on known data in said predetermined set of fields; determining if a new key to be added to the tree equals an existing key on the tree, determining if the record associated with the new key is a modified version of the record associated with said existing key, and if former and the later determinations are true, replacing the address stored with the existing key with the address associated with the new key, if said former determination is true and said later determination is not true, storing said new key and the record associated with the new key in a duplicate key list; searching the nodes of said tree to find a matching key with a value equal to the value of the certain key; if said searching fails to find a key with a value equal to the value of the certain key, sequentially searching said duplicate key list to find a matching key; utilizing the address stored with the matching key to locate the certain record in the database.
Claim 2
Dependent Claim
287 words
In a telecommunications switching system having a database that stores records containing operating parameters, a method for locating a certain record in the database comprising the steps of: generating a key for each record using a hash function based on data in a predetermined set of fields in each record; creating and storing a search tree having a plurality of linked tree nodes, each tree node comprising one of said keys and an address of a corresponding record, said keys arranged on the tree relative to the numerical value of keys previously entered in the tree; generating a certain key corresponding to said certain record to be located in the database using said hash function based on known data in said predetermined set of fields; determining if a new key to be added to the tree equals an existing key on the tree, determining if the record associated with the new key is a modified version of the record associated with said existing key, and if former and the later determinations are true, replacing the address stored with the existing key with the address associated with the new key, if said former determination is true and said later determination is not true, storing said new key and the record associated with the new key in a duplicate key list; searching the nodes of said tree to find a matching key with a value equal to the value of the certain key; if said searching fails to find a key with a value equal to the value of the certain key, sequentially searching said duplicate key list to find a matching key; utilizing the address stored with the matching key to locate the certain record in the database.
Claim 3
Dependent Claim
67 words
The method according to claim 1 wherein said searching step comprises the steps of searching a binary search tree beginning at a vertex node of the tree and selecting one tree branch to follow from a plurality of tree branches based on the value of said certain key relative to the value of the key contained in the node to which the plurality of branches are coupled.
Claim 4
Dependent Claim
21 words
The method according to claim 1 wherein each of said keys comprise a digital word having the same number of bits.
Claim 5
Dependent Claim
20 words
The method according to claim 1 wherein said parameters comprise data that can be modified by users of the system.
Claim 6
Dependent Claim
22 words
The method according to claim 1 further comprising the step of reading said located record to obtain said operating parameters stored therein.
Claim 7
Independent Claim
272 words
A method for locating the records in a database comprising the steps of: generating a key for each record using a hash function based on data in a predetermined set of fields in each record; creating and storing a search tree having a plurality of linked tree nodes, each tree node comprising one of said keys and an address of a corresponding record, said keys arranged on the tree relative to the numerical value of keys previously entered in the tree; generating a certain key corresponding to a certain record to be located in the database using said hash function based on known data in said predetermined set of fields; determining if a new key to be added to the tree equals an existing key on the tree, determining if the record associated with the new key is a modified version of the record associated with said existing key, and if former and the later determinations are true, replacing the address stored with the existing key with the address associated with the new key, if said former determination is true and said later determination is not true, storing said new key and the record associated with the new key in a duplicate key list; searching the nodes of said tree to find a matching key with a value equal to the value of the certain key; if said searching fails to find a key with a value equal to the value of the certain key, sequentially searching said duplicate key list to find a matching key; utilizing the address stored with the matching key to locate the certain record in the database.
Claim 8
Independent Claim
272 words
A method for locating the records in a database comprising the steps of: generating a key for each record using a hash function based on data in a predetermined set of fields in each record; creating and storing a search tree having a plurality of linked tree nodes, each tree node comprising one of said keys and an address of a corresponding record, said keys arranged on the tree relative to the numerical value of keys previously entered in the tree; generating a certain key corresponding to a certain record to be located in the database using said hash function based on known data in said predetermined set of fields; determining if a new key to be added to the tree equals an existing key on the tree, determining if the record associated with the new key is a modified version of the record associated with said existing key, and if former and the later determinations are true, replacing the address stored with the existing key with the address associated with the new key, if said former determination is true and said later determination is not true, storing said new key and the record associated with the new key in a duplicate key list; searching the nodes of said tree to find a matching key with a value equal to the value of the certain key; if said searching fails to find a key with a value equal to the value of the certain key, sequentially searching said duplicate key list to find a matching key; utilizing the address stored with the matching key to locate the certain record in the database.
Claim 9
Dependent Claim
67 words
The method according to claim 6 wherein said searching step comprises the steps of searching a binary search tree beginning at a vertex node of the tree and selecting one tree branch to follow from a plurality of tree branches based on the value of said certain key relative to the value of the key contained in the node to which the plurality of branches are coupled.
Claim 10
Dependent Claim
21 words
The method according to claim 6 wherein each of said keys comprise a digital word having the same number of bits.
Claim 11
Independent Claim
303 words
An apparatus for locating a certain record in a database containing a plurality of records comprising: means for generating a key for each record using a hashing function based on data in a predetermined set of fields in each record; means for creating and storing a binary search tree having a plurality of linked tree nodes, each tree node comprising one of said keys and an address of a corresponding record, said keys arranged on the tree relative to the numerical value of keys previously entered in the tree; means for generating a certain key corresponding to a certain record to be located in the database using said hashing function based on known data in said predetermined set of fields; means for determining if a new key to be added to the tree equals an existing key on the tree and if the record associated with the new key is a modified version of the record associated with said existing key, means responsive to the former and the later determinations being true for replacing the address stored with the existing key with the address associated with the new key, means responsive to said former determination being true and said later determination being not true for storing said new key and the record associated with the new key in a duplicate key list; means for searching the nodes of said tree to find a matching key with a value equal to the value of the certain key; means responsive to said searching means failing to find a key in said nodes with a value equal to the value of the certain key for sequentially searching said duplicate key list to find a matching key; means for utilizing the address stored with the matching key to locate the certain record associated with said certain key.
Claim 12
Independent Claim
303 words
An apparatus for locating a certain record in a database containing a plurality of records comprising: means for generating a key for each record using a hashing function based on data in a predetermined set of fields in each record; means for creating and storing a binary search tree having a plurality of linked tree nodes, each tree node comprising one of said keys and an address of a corresponding record, said keys arranged on the tree relative to the numerical value of keys previously entered in the tree; means for generating a certain key corresponding to a certain record to be located in the database using said hashing function based on known data in said predetermined set of fields; means for determining if a new key to be added to the tree equals an existing key on the tree and if the record associated with the new key is a modified version of the record associated with said existing key, means responsive to the former and the later determinations being true for replacing the address stored with the existing key with the address associated with the new key, means responsive to said former determination being true and said later determination being not true for storing said new key and the record associated with the new key in a duplicate key list; means for searching the nodes of said tree to find a matching key with a value equal to the value of the certain key; means responsive to said searching means failing to find a key in said nodes with a value equal to the value of the certain key for sequentially searching said duplicate key list to find a matching key; means for utilizing the address stored with the matching key to locate the certain record associated with said certain key.
Claim 13
Dependent Claim
58 words
The apparatus according to claim 9 wherein said searching means searches a binary search tree beginning at a vertex node of the tree and selects one tree branch to follow based on the value of said certain key relative to the value of the key contained in the tree node to which the plurality of branches are coupled.
Claim 14
Dependent Claim
21 words
The apparatus according to claim 9 wherein each of said keys comprise a digital word having the same number of bits.
References Cited (Backward Citations)
US4215402A
Cited
US4611272A
Cited
US4677550A
Cited
US4527239A
Cited
US4922417A
Cited
US5319779A
Cited
US5204958A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-22 | 1998-11-21 | 1999-05-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-22 | 2002-11-21 | 2003-05-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-22 | 2006-11-21 | 2007-05-23 | $7700.00 | Window Closed / Lapsed |