Method for storing a tree of potential keys in a sparse table

Details Method for storing a tree of potential keys in a sparse table Method for storing a tree of potential keys in a sparse table

1996-07-19

1999-01-05

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707 3, 707 7, 707104, G06F 1730

Patent

active

058571965

ABSTRACT:
A computer implemented method for searching for a key in a radix search tree in a memory of a computer system. A table of keys is organized in a radix search tree stored in a memory of a computer system. The keys are divided into a string of symbols. Each node in the tree corresponds to a symbol. A path from a root node to a leaf node at level n in the tree represents a string of n symbols comprising a key. Each node is capable of having m possible entries corresponding to m possible symbol values. Each entry comprises a pointer to a son node and an existence map indicating which entries exist in the son node. In the preferred embodiment, the existence map is a bit mask that indicates, based on bit positions enabled and disabled in the bit mask, which entries exist in the son node pointed to by the pointer. By providing an existence map along with the pointer to a son node, m memory locations for m entries are allocated for the son node only if all of the m possible entries are used. Memory locations for entries that would otherwise be empty are not allocated, thereby minimizing memory resources required by a radix search tree.

REFERENCES:
patent: 4468728 (1984-08-01), Wang
patent: 4774657 (1988-09-01), Anderson et al.
patent: 5261088 (1993-11-01), Baird et al.
patent: 5333317 (1994-07-01), Dann
patent: 5396622 (1995-03-01), Lee et al.
patent: 5440734 (1995-08-01), Wagar
patent: 5487164 (1996-01-01), Kirchhofer et al.
patent: 5490269 (1996-02-01), Cohn et al.
patent: 5546390 (1996-08-01), Stone
patent: 5557786 (1996-09-01), Johnson, Jr.
patent: 5651099 (1997-07-01), Konsella

Affiliated with

Also associated with

Rating

Method for storing a tree of potential keys in a sparse table does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for storing a tree of potential keys in a sparse table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for storing a tree of potential keys in a sparse table will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-869753