Radix tree search logic

Details Radix tree search logic Radix tree search logic

1996-07-19

1999-02-16

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707102, G06F 1730

Patent

active

058730788

ABSTRACT:
In a search method for a radix search tree, a logic circuit for computing the actual offset of an entry in a node in a tree. The logic circuit accepts a pointer to a node in the tree, along with an associated bit mask indicating which entries are present in the node. The logic circuit further receives an entry value, the offset of which from the beginning of the node is to be computed by the logic circuit. The logic circuit utilizes Boolean AND gates to mask off higher order bits in the bit mask above the bit position corresponding to the entry value received by the logic circuit. The lower order bits in the bit mask, up to but not including the bit position corresponding to the entry value, are added together to determine the number of entries that exist at a lower offset in the node than the entry indicated by the entry value. The logic circuit combines the pointer received with the sum computed to calculate the offset memory address at which the entry is located in the node.

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: 5487164 (1996-01-01), Kirchhofer et al.
patent: 5546390 (1996-08-01), Stone
patent: 5557786 (1996-09-01), Johnson, Jr.
patent: 5651099 (1997-07-01), Konsella
patent: 5727201 (1998-03-01), Burke

Affiliated with

Also associated with

Rating

Radix tree search logic does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Radix tree search logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Radix tree search logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2072205