Wildcards in radix- search tree structures

• US 6,594,655 B2
• Filed: 01/04/2001
• Issued: 07/15/2003
• Est. Priority Date: 01/04/2001
• Status: Expired due to Term

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Ezchip Technologies Ltd. (NVIDIA Corporation)
• Inventors: Tiger, Roostam, Tal, Alex, Gabbay, Itzchak, Rachamim, Shifra
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US09/753,690
• Publication Number:
  US 20020143747A1
• Time in Patent Office: 922 Days
• Field of Search: 707/1, 707/100, 707/102, 370/408, 370/255
• US Class Current: 707/797
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system for storing and retrieving data using a radix-search tree having a plurality of sub-trees containing nodes and leaves, the system including: (a) a data storage module designed and configured for storing the plurality of sub-trees, wherein at least one of the leaves contains at least one entry having at least one wildcard in a primary position, and (b) a processor that is operative to perform operations including: (i) building the radix-search tree in the data storage module, and (ii) retrieving data from the radix-search tree in the data storage module.

Claims

1. A system for storing and retrieving data using a radix-search tree having a plurality of sub-trees containing nodes and leaves, the system comprising:

(a) a data storage module designed and configured for storing the plurality of sub-trees, wherein at least one leaf of the leaves contains at least two entries, at least one entry of which has at least one wildcard, and

(b) a processor that is operative to perform operations including;

(i) building the radix-search tree in said data storage module,

wherein at least two of said entries contain a different number of bits with respect to one another.

2. The system of claim 1, wherein said data storage module is further designed and configured such that said at least one wildcard is locatable at any location within said entry.

3. The system of claim 1, wherein said at least two entries within said leaf have an identical prefix.

4. The system of claim 3, wherein said at least two entries are indistinguishable by a node.

5. The system of claim 1, said processor being further operative to perform:

(ii) retrieving data from the radix-search tree in said data storage module.

6. The system of claim 1, wherein said at least one wildcard is followed by a bit forming a pseudo-node.

7. The system of claim 1, wherein said at least one wildcard is followed by a split bit.

8. The system of claim 1, wherein said at least one wildcard is in a middle position.

9. The system of claim 1, wherein said at least one wildcard is in a suffix position.

10. The system of claim 1, wherein said at least one entry having at least one wildcard in a primary position has a split bit preceding said at least one wildcard and a split bit following said at least one wildcard.

11. The system of claim 1, wherein at least one bit is checked out of order of appearance.

12. The system of claim 1, wherein said building of the radix-search tree in said data storage module includes ordering the nodes of at least one of the sub-trees, said ordering the nodes being performed by examining a bit having a minimum number of wildcards.

13. The system of claim 1, wherein said building the radix-search tree in said data storage module includes ordering the nodes of at least one of the sub-trees, said ordering the nodes being performed by examining a bit providing a best-balanced split of single keys in the sub-tree.

14. The system of claim 13, wherein said bit is selected according to a combination of selection criteria including:

(a) a minimum number of wildcards in the sub-tree, and

(b) a best-balanced split of single keys in the sub-tree.

15. The system of claim 12, wherein if at least two bits have said minimum number of wildcards, the nodes are ordered at least according to a bit providing a best-balanced split of single keys in said sub-tree.

16. The system of claim 1, wherein at least one of said entries disposed in said leaf is a sub-set of another one of said entries.

17. The system of claim 1, wherein said leaf contains at least three of said entries.

19. The method of claim 11, wherein said at least one wildcard is locatable at any location within said entry.

18. A method of storing and retrieving data using a radix-search tree having a plurality of sub-trees containing nodes and leaves, the method comprising the steps of:

(a) providing a system including;

(i) a data storage module for storing the plurality of sub-trees, wherein at least one leaf of the leaves contains at least two entries, at least one entry of which has at least one wildcard, and

(ii) a processor, operatively connected to data storage module, and

(b) building the radix-search tree in said data storage module,

wherein at least two of said entries contain a different number of bits with respect to one another.

20. The method of claim 18, wherein said at least two entries within said leaf have an identical prefix.

21. The method of claim 20, wherein said at least two entries are indistinguishable by a node.

22. The method of claim 18, further comprising the step of:

(c) retrieving data from the radix-search tree in said data storage module.

23. The method of claim 18, wherein said at least one wildcard is followed by a bit forming a pseudo-node.

24. The method of claim 18, wherein said at least one entry having at least one wildcard in a primary position has a split bit preceding said at least one wildcard and a split bit following said at least one wildcard.

25. The method of claim 18, further comprising the step of:

(c) checking at least one bit out of order of appearance.

26. The method of claim 18, wherein said building of the radix-search tree in said data storage module includes ordering the nodes of at least one of the sub-trees, said ordering the nodes being performed by examining a bit having a minimum number of wildcards.

27. The method of claim 18, wherein said building the radix-search tree in said data storage module includes ordering the nodes of at least one of the sub-trees, said ordering the nodes being performed by examining a bit providing a best-balanced split of single keys in the sub-tree.

28. The method of claim 27, wherein said bit is selected according to a combination of selection criteria including:

(a) a minimum number of wildcards in the sub-tree, and

(b) a best-balanced split of single keys in the sub-tree.

29. The method of claim 26, wherein if at least two bits have said minimum number of wildcards, the nodes are ordered at least according to a bit providing a best-balanced split of single keys in said sub-tree.

30. The method of claim 18, wherein at least one of said entries disposed in said leaf is a sub-set of another one of said entries.

31. The method of claim 18, wherein said leaf contains at least three of said entries.