Boots – shoes – and leggings
Patent
1989-09-28
1993-04-13
Shaw, Gareth D.
Boots, shoes, and leggings
364DIG2, 3649743, 364963, 3649605, G06F 1540
Patent
active
052029867
ABSTRACT:
A prefix index tree structure for locating data records stored through keys related to information stored in data records. Each node includes a prefix field for a prefix string of length p of the longest string of key characters shared by all subtrees of the node and a data record field for a reference to a data record whose key is completed by the prefix string. A node may include one or more branch fields when the prefix string is a prefix of keys stored in at least one subtree of the node, with a branch field for each distinct p+1.sup.st key character in the keys, wherein each p+1.sup.st key character is a branch character. Each branch field includes a branch character and a branch pointer field for a reference to a node containing at least one key whose p+1.sup.st character is the branch character. Each node further includes a field for storing the number of key characters in the prefix string and a field for storing the number of branch fields in the node. Also disclosed are methods for constructing and searching a prefix index tree of the present invention, and for inserting nodes into the tree and deleting nodes from the tree.
REFERENCES:
patent: 3938105 (1976-02-01), Lechner
patent: 4086628 (1978-04-01), Woodrum
patent: 4267568 (1981-05-01), Dechant et al.
patent: 4464650 (1984-08-01), Eastman
patent: 4468728 (1984-08-01), Wang
patent: 4611272 (1986-09-01), Lomet
patent: 4611298 (1986-09-01), Schuldt
patent: 4677550 (1987-06-01), Ferguson
patent: 4774657 (1988-09-01), Anderson et al.
patent: 4814746 (1989-03-01), Miller et al.
patent: 4817036 (1989-03-01), Millett et al.
patent: 4821290 (1989-04-01), Hingorani et al.
patent: 4868743 (1989-09-01), Nishio
"Fundamentals of Data Structures", by E. Horowitz & S. Sahni Computer Science Press, 1976 (pp. 214-249; 422-429; 440-443; 494-525; 536-541).
"Organization and Maintenance of Large Ordered Indexes", R. Bayer & E. MacCreight, Acta Informatica, vol. 1, 1972.
"Prefix B-Trees", R. Bayer and K. Unteraurer, ACM Transactions on Database Systems, vol. 2, No. 1, 1977 (pp. 11-26).
"Performance Comparison Between B*-Tree and Prefix Binary Tree Index Organizations", N. Phuc, M. Becker & P. Sevray, Proceedings-Second International Conference on Databases, John Wiley & Sons Ltd., 1983 (Chapter 19, pp. 358-376).
Bull HN Information Systems Inc.
Chaki Kakali
Clapp Gary D.
Elbinger Lewis P.
Shaw Gareth D.
LandOfFree
Prefix search tree partial key branching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prefix search tree partial key branching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix search tree partial key branching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1161418