US6029170A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hybrid tree array data structure and method
Assignee: International Business Machines Corp
•
Filing: 1997-11-25
•
Granted: 2000-02-22
•
Expires: 2017-11-25
Abstract
Abstract The preferred embodiment of the present invention provides a method and apparatus for storing and accessing data. The preferred embodiment hybrid tree-array database provides the ability to perform fast searching using tree database search techniques and the ability to search all user data fields using array search techniques. In particular, fast key searching as a typical tree database and sequential array searching of all data fields as a typical array database are provided in a single database, without requiring the user data be duplicated and stored in two separate databases. Thus, the preferred embodiment provides searching flexibility without the excessive storage requirements and complexity inherent in managing separate array and tree databases. The preferred embodiment also provides the advantage of allowing individual users of the database to search the data using either tree or array search techniques without requiring any detailed knowledge of the dual nature of the hybrid tree-array database.
Inventors
- 👤 Valery I. Garger
- 👤 Ann Marie Shepherd
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 08:28
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 60
Claim 1
Independent Claim
131 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a program residing in the memory, said program providing a hybrid tree-array database, said hybrid tree-array database storing an array of user data portions searchable by a tree key search and by a sequential array search, wherein each user data portion corresponds to a node on a tree and wherein the hybrid tree-array database includes tree node data corresponding to each user data portion, wherein the tree node data corresponding to each user data portion includes an index pointer to other of the user data portions in said array that correspond to children nodes of said corresponding node, said tree node data thereby facilitating said tree key search of said array of user data portions.
Claim 2
Independent Claim
131 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a program residing in the memory, said program providing a hybrid tree-array database, said hybrid tree-array database storing an array of user data portions searchable by a tree key search and by a sequential array search, wherein each user data portion corresponds to a node on a tree and wherein the hybrid tree-array database includes tree node data corresponding to each user data portion, wherein the tree node data corresponding to each user data portion includes an index pointer to other of the user data portions in said array that correspond to children nodes of said corresponding node, said tree node data thereby facilitating said tree key search of said array of user data portions.
Claim 3
Dependent Claim
14 words
The apparatus of claim 1 wherein said hybrid tree-array database comprises an unordered array.
Claim 4
Dependent Claim
32 words
The apparatus of claim 2 wherein said user data portion and said tree node data corresponding to said user data portion are both stored together in said array of user data portions.
Claim 5
Dependent Claim
19 words
The apparatus of claim 1 wherein said tree node data includes a key to facilitate said tree key search.
Claim 6
Dependent Claim
19 words
The apparatus of claim 1 wherein said tree node data further includes index-pointers to said corresponding user data portions.
Claim 7
Dependent Claim
22 words
The apparatus of claim 1 wherein said tree node data further includes an index-pointer to any parent node of said corresponding node.
Claim 8
Dependent Claim
69 words
The apparatus of claim 1 wherein said hybrid tree-array database comprises an unordered array, said unordered array including a plurality of elements, each of said plurality of elements storing one of said user data portions and said corresponding tree node data, wherein said corresponding tree node data includes a key to facilitate said tree key search and further includes an index-pointer to any parent node of the corresponding node.
Claim 9
Dependent Claim
18 words
The apparatus of claim 7 wherein said unordered array manages storage of said elements to minimize storage fragmentation.
Claim 10
Dependent Claim
29 words
The apparatus of claim 7 wherein said user data portion includes an array key, said array key facilitating said sequential array search of said array of user data portions.
Claim 11
Dependent Claim
13 words
The apparatus of claim 7 wherein said unordered array comprises a relocatable array.
Claim 12
Dependent Claim
28 words
The apparatus of claim 1 wherein said hybrid tree-array database provides said tree key search and said sequential array search with a single array of user data portions.
Claim 13
Independent Claim
124 words
A method for providing data storage in a computer system, the method comprising the steps of: a) providing an array of user data portions searchable by sequential array search, and wherein each user data portion in said array corresponds to a node on a tree; and b) providing a plurality of tree node data, each of said plurality of tree node data corresponding to one of said user data portions, and each of said plurality of tree node data including an index-pointer to other of said user data portions that correspond to children nodes of said corresponding node on said tree, said plurality of tree node data combining to implement said tree for searching said plurality of user data portions stored in said array.
Claim 14
Independent Claim
124 words
A method for providing data storage in a computer system, the method comprising the steps of: a) providing an array of user data portions searchable by sequential array search, and wherein each user data portion in said array corresponds to a node on a tree; and b) providing a plurality of tree node data, each of said plurality of tree node data corresponding to one of said user data portions, and each of said plurality of tree node data including an index-pointer to other of said user data portions that correspond to children nodes of said corresponding node on said tree, said plurality of tree node data combining to implement said tree for searching said plurality of user data portions stored in said array.
Claim 15
Dependent Claim
58 words
The method of claim 12 further comprising the step adding a new user data portion to said array and further comprising the step of creating new tree node data corresponding to said new user data portion, wherein the step of creating new tree node data comprises creating a new node and placing said new node in said tree.
Claim 16
Dependent Claim
71 words
The method of claim 13 wherein the step of adding a new user data portion to said array comprises determining if a vacant user data portion exists and adding said new user data portion to said vacant user data portion if said vacant user data portion exists and adding said new user data portion to a previously never used user data portion if said vacant user data portion does not exist.
Claim 17
Dependent Claim
17 words
The method of claim 12 wherein the step of providing an array comprises providing an unordered array.
Claim 18
Dependent Claim
21 words
The method of claim 12 wherein said plurality of tree node data are stored in said array of user data portions.
Claim 19
Dependent Claim
24 words
The method of claim 12 wherein each of said plurality of tree node data includes a key to facilitate key searching of said tree.
Claim 20
Dependent Claim
12 words
The method of claim 12 wherein said array comprises a relocatable array.
Claim 21
Dependent Claim
21 words
The method of claim 12 wherein said tree provides tree key search capability with said single array of user data portions.
Claim 22
Dependent Claim
124 words
A program product comprising: (A) a program, said program providing a hybrid tree-array database, said hybrid tree-array database storing an array of user data portions searchable by a tree key search and by a sequential array search, wherein each user data portion corresponds to a node on a tree and wherein the hybrid tree-array database includes tree node data corresponding to each user data portion, wherein the tree node data corresponding to each user data portion includes an index pointer to other of the user data portions in said array that correspond to children nodes of said corresponding node, said tree node data thereby facilitating said tree key search of said array of user data portions; and (B) signal bearing media bearing said program.
Claim 23
Dependent Claim
124 words
A program product comprising: (A) a program, said program providing a hybrid tree-array database, said hybrid tree-array database storing an array of user data portions searchable by a tree key search and by a sequential array search, wherein each user data portion corresponds to a node on a tree and wherein the hybrid tree-array database includes tree node data corresponding to each user data portion, wherein the tree node data corresponding to each user data portion includes an index pointer to other of the user data portions in said array that correspond to children nodes of said corresponding node, said tree node data thereby facilitating said tree key search of said array of user data portions; and (B) signal bearing media bearing said program.
Claim 24
Dependent Claim
14 words
The program product of claim 20 wherein said signal bearing media comprises recordable media.
Claim 25
Dependent Claim
14 words
The program product of claim 20 wherein said signal bearing media comprises transmission media.
Claim 26
Dependent Claim
15 words
The program product of claim 20 wherein said hybrid tree-array database comprises an unordered array.
Claim 27
Dependent Claim
33 words
The program product of claim 23 wherein said user data portions and said tree node data corresponding to said user data portion are both stored together in said array of user data portions.
Claim 28
Dependent Claim
20 words
The program product of claim 20 wherein said tree node data includes a key to facilitate said tree key search.
Claim 29
Dependent Claim
20 words
The program product of claim 20 wherein said tree node data further includes index-pointers to said corresponding user data portions.
Claim 30
Dependent Claim
23 words
The program product of claim 20 wherein said tree node data further includes an index-pointer to any parent node of said corresponding node.
Claim 31
Dependent Claim
70 words
The program product of claim 20 wherein said hybrid tree-array database comprises an unordered array, said unordered array including a plurality of elements, each of said plurality of elements storing one of said user data portions and said corresponding tree node data, wherein said corresponding tree node data includes a key to facilitate said tree key search and further includes an index-pointer to any parent node of the corresponding node.
Claim 32
Dependent Claim
19 words
The program product of claim 28 wherein said unordered array manages storage of said elements to minimize storage fragmentation.
Claim 33
Dependent Claim
30 words
The program product of claim 28 wherein said user data portion includes an array key, said array key facilitating said sequential array search of said array of user data portions.
Claim 34
Dependent Claim
14 words
The program product of claim 28 wherein said unordered array comprises a relocatable array.
Claim 35
Dependent Claim
29 words
The program product of claim 20 wherein said hybrid tree-array database provides said tree key search and said sequential array search with aid single array of user data portions.
Claim 36
Independent Claim
148 words
An apparatus comprising: a) at least one processor; b) a memory coupled to the at least one processor; and c) a computer program residing in the memory, said computer program including a hybrid tree-array database including: i) an unordered array ii) a plurality of elements in said unordered array; iii) a plurality of user data portions, each of said plurality of user data portions stored in one of said plurality of elements; iv) a plurality of tree node data, said plurality of tree node data implementing a tree having a plurality of tree nodes, each of said plurality of tree node data corresponding to one of said plurality of tree nodes and one of said plurality of user data portions, each of said tree node data including a key to facilitate key tree searching and an index-pointer to any child and parent nodes of said corresponding tree nodes.
Claim 37
Independent Claim
148 words
An apparatus comprising: a) at least one processor; b) a memory coupled to the at least one processor; and c) a computer program residing in the memory, said computer program including a hybrid tree-array database including: i) an unordered array ii) a plurality of elements in said unordered array; iii) a plurality of user data portions, each of said plurality of user data portions stored in one of said plurality of elements; iv) a plurality of tree node data, said plurality of tree node data implementing a tree having a plurality of tree nodes, each of said plurality of tree node data corresponding to one of said plurality of tree nodes and one of said plurality of user data portions, each of said tree node data including a key to facilitate key tree searching and an index-pointer to any child and parent nodes of said corresponding tree nodes.
Claim 38
Dependent Claim
29 words
The apparatus of claim 33 wherein each of said plurality of tree node data is stored in one of said plurality of elements with said corresponding user data portion.
Claim 39
Dependent Claim
18 words
The apparatus of claim 33 wherein said unordered array manages storage allocation of said memory to avoid fragmentation.
Claim 40
Dependent Claim
27 words
The apparatus of claim 33 wherein said hybrid tree-array database comprises a single copy of said plurality of user data portions to minimize utilization of said memory.
Claim 41
Dependent Claim
44 words
The apparatus of claim 33 wherein said unordered array includes an array header, said array header including an index-pointer to a list of vacated elements, wherein said vacated elements comprise elements of said unordered array having no user data and no corresponding tree node.
Claim 42
Dependent Claim
12 words
The apparatus of claim 33 wherein said tree comprises a Patricia tree.
Claim 43
Dependent Claim
32 words
The apparatus of claim 33 wherein said each of said plurality of user data portions include an array key, said array key facilitating an array key search of said user data portions.
Claim 44
Dependent Claim
90 words
The apparatus of claim 33 further comprising a second plurality of tree node data, said second plurality of tree node data implementing a second tree having a second plurality of tree nodes, each of said second plurality of tree node data corresponding to one of said second plurality of tree nodes and one of said plurality of user data portions, each of said second tree node data including a key to facilitate key tree searching and an index-pointer to any child and parent nodes of said corresponding second tree nodes.
Claim 45
Independent Claim
194 words
A method for providing data storage in a computer system, the method comprising the steps of: a) providing an unordered array having a plurality of elements, each of said plurality of elements including a user data portion, said unordered array providing sequential array search capability of said plurality of user data portions; b) providing a plurality of tree node data, each of said plurality of tree node data including a key, said plurality of tree node data combining to implement a tree having a plurality of tree nodes, each of said plurality of tree node data corresponding to one of said user data portions and each of said plurality of tree nodes corresponding to one of said plurality of elements, said plurality of tree node data facilitating tree key searching of said plurality of user data portions stored in said array; c) adding a new user data portion to one of said plurality of elements in said array; and d) creating new tree node data corresponding to said new data, wherein the step of creating new tree node data comprises creating a new tree node and placing said new tree node in said tree.
Claim 46
Independent Claim
194 words
A method for providing data storage in a computer system, the method comprising the steps of: a) providing an unordered array having a plurality of elements, each of said plurality of elements including a user data portion, said unordered array providing sequential array search capability of said plurality of user data portions; b) providing a plurality of tree node data, each of said plurality of tree node data including a key, said plurality of tree node data combining to implement a tree having a plurality of tree nodes, each of said plurality of tree node data corresponding to one of said user data portions and each of said plurality of tree nodes corresponding to one of said plurality of elements, said plurality of tree node data facilitating tree key searching of said plurality of user data portions stored in said array; c) adding a new user data portion to one of said plurality of elements in said array; and d) creating new tree node data corresponding to said new data, wherein the step of creating new tree node data comprises creating a new tree node and placing said new tree node in said tree.
Claim 47
Dependent Claim
63 words
The method of claim 41 wherein the step of adding a new user data portion to one of said plurality of elements comprises determining if a vacant element exists and adding said new data portion to said vacant element if said vacant element exists and adding said new data portion to a previously never used element if said vacant element does not exist.
Claim 48
Dependent Claim
25 words
The method of claim 41 wherein said plurality of tree node data are stored in said plurality of elements with said corresponding user data portions.
Claim 49
Dependent Claim
14 words
The method of claim 41 wherein said unordered array comprises a relocatable unordered array.
Claim 50
Dependent Claim
139 words
A program product comprising: (A) a program, said program providing a hybrid tree-array database, said hybrid tree-array database including: i) an unordered array ii) a plurality of elements in said unordered array; iii) a plurality of user data portions, each of said plurality of user data portions stored in one of said plurality of elements; iv) a plurality of tree node data, said plurality of tree node data implementing a tree having a plurality of tree nodes, each of said plurality of tree node data corresponding to one of said plurality of tree nodes and one of said plurality of user data portions, each of said tree node data including a key to facilitate key tree searching and an index-pointer to any child and parent nodes of said corresponding tree nodes; and (B) signal bearing media bearing said program.
Claim 51
Dependent Claim
139 words
A program product comprising: (A) a program, said program providing a hybrid tree-array database, said hybrid tree-array database including: i) an unordered array ii) a plurality of elements in said unordered array; iii) a plurality of user data portions, each of said plurality of user data portions stored in one of said plurality of elements; iv) a plurality of tree node data, said plurality of tree node data implementing a tree having a plurality of tree nodes, each of said plurality of tree node data corresponding to one of said plurality of tree nodes and one of said plurality of user data portions, each of said tree node data including a key to facilitate key tree searching and an index-pointer to any child and parent nodes of said corresponding tree nodes; and (B) signal bearing media bearing said program.
Claim 52
Dependent Claim
14 words
The program product of claim 45 wherein said signal bearing media comprises recordable media.
Claim 53
Dependent Claim
14 words
The program product of claim 45 wherein said signal bearing media comprises transmission media.
Claim 54
Dependent Claim
30 words
The program product of claim 45 wherein each of said plurality of tree node data is stored in one of said plurality of elements with said corresponding user data portion.
Claim 55
Dependent Claim
19 words
The program product of claim 45 wherein said unordered array manages storage allocation of said memory to avoid fragmentation.
Claim 56
Dependent Claim
28 words
The program product of claim 45 wherein said hybrid tree-array database comprises a single copy of said plurality of user data portions to minimize utilization of said memory.
Claim 57
Dependent Claim
45 words
The program product of claim 45 wherein said unordered array includes an array header, said array header including an index-pointer to a list of vacated elements, wherein said vacated elements comprise elements of said unordered array having no user data and no corresponding tree node.
Claim 58
Dependent Claim
13 words
The program product of claim 45 wherein said tree comprises a Patricia tree.
Claim 59
Dependent Claim
33 words
The program product of claim 45 wherein said each of said plurality of user data portions include an array key, said array key facilitating an array key search of said user data portions.
Claim 60
Dependent Claim
91 words
The program product of claim 45 further comprising a second plurality of tree node data, said second plurality of tree node data implementing a second tree having a second plurality of tree nodes, each of said second plurality of tree node data corresponding to one of said second plurality of tree nodes and one of said plurality of user data portions, each of said second tree node data including a key to facilitate key tree searching and an index-pointer to any child and parent nodes of said corresponding second tree nodes.
References Cited (Backward Citations)
US3596258A
Cited
US3938105A
Cited
US4468728A
Cited
US5303367A
Cited
US5649191A
Cited
US5530957A
Cited
US5600826A
Cited
US5497485A
Cited
US5446888A
Cited
US5504890A
Cited
US5611076A
Cited
US5829004A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-21 | 2003-08-23 | 2004-02-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-21 | 2007-08-23 | 2008-02-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-21 | 2011-08-23 | 2012-02-22 | $7700.00 | Window Closed / Lapsed |