Cascading index method and apparatus

1. A computer-implemented method to search a cascading index structure using a database management system comprising a processor and a memory, said processor configured to execute instructions stored in said memory, the method comprising the steps of:

providing a first index PATRICIA trie comprising a plurality of node labels, each node label referencing a block in a second index PATRICIA trie;

providing said second index PATRICIA trie comprising at least one index PATRICIA trie block, each index PATRICIA trie block comprising at least one key, each key corresponding to a prefix of a block in a PATRICIA trie structure, each key having a depth level;

providing said PATRICIA trie structure, said PATRICIA trie structure comprising a plurality of PATRICIA trie blocks, each PATRICIA trie block comprising at least one node that stores bits;

said processor receiving said first index PATRICIA trie to search said PATRICIA trie structure;

said processor checking if said first index PATRICIA trie comprises a first node label that references said second index PATRICIA trie in said cascading index structure;

if said first index PATRICIA trie references a second index PATRICIA trie, said processor checking an entire depth of said first index PATRICIA trie;

said processor checking whether a next node label matches said PATRICIA trie key;

if said next node label key matches said PATRICIA trie key, said processor adding said matched depths to said depth level;

if said next node label key is different than said second index PATRICIA trie key, said processor checking based on a second next node label of said index PATRICIA trie if said second next node label key matches said PATRICIA trie key and, if so, said processor adding a number of matched depths to said depth level; and

the processor returning said key and said depth level as results of said search if said second index PATRICIA trie key matches said PATRICIA trie structure key.

2. The method of claim 1 , further comprising the steps of:

comparing a returned value of said key and a returned value of said node label; and

performing a mismatch check if said comparing step results in inequality; otherwise, terminating said method.

3. The method of claim 1 , further comprising the step of:

initially setting said depth level to be empty.

4. The method of claim 1 , wherein said PATRICIA trie structure comprises a plurality of ternary PATRICIA trie blocks.

5. The method of claim 1 , wherein said index PATRICIA trie block comprises a ternary PATRICIA trie block.

6. The method of claim 2 , further comprising the step of:

performing a range search.

7. The method of claim 6 , said range search further comprising the steps of:

finding a first bit position of difference between said returned values; and

checking whether there is available an unlabeled branch from a first value in said depth level that is less than said first bit position and, if so, searching said unlabeled branch; otherwise, said key is not in said cascading index.

8. A computer program comprising computer executable code to search a cascading index structure, said computer program being stored on a computer readable storage medium and, when executed, said computer program implementing a method in a computer comprising the steps of:

providing a first index PATRICIA trie comprising a plurality of node labels, each node label referencing a block in a second index PATRICIA trie;

providing said second index PATRICIA trie comprising at least one index PATRICIA trie block, each index PATRICIA trie block comprising at least one key, each key corresponding to a prefix of a block in a PATRICIA trie structure, each key having a depth level;

providing said PATRICIA trie structure, said PATRICIA trie structure comprising a plurality of PATRICIA trie blocks, each PATRICIA trie block comprising at least one node that stores bits;

receiving said first index PATRICIA trie to search of said PATRICIA trie structure;

checking if said first index PATRICIA trie comprises a first node label that references said second index PATRICIA trie in said cascading index structure;

if said first index PATRICIA trie references a second index PATRICIA trie, said processor checking an entire depth of said first index PATRICIA trie;

checking whether a next node label matches said PATRICIA trie key;

if said next node label key matches said PATRICIA trie key, adding said matched depths to said depth level;

if said next node label key is different than said second index PATRICIA trie key, checking based on a second next node label of said index PATRICIA trie if said second next node label key matches said PATRICIA trie key and, if so,

adding a number of matched depths to said depth level; and

returning said key and said depth level as results of said search if said second index PATRICIA key matches said PATRICIA trie structure key.

9. The computer program of claim 8 , further comprising the steps of:

comparing a returned value of said key and a returned value of said node label; and

performing a mismatch check if said comparing step results in inequality; otherwise, terminating said code execution.

10. The computer program of claim 8 , further comprising the step of:

initially setting said depth level to empty.

11. The computer program of claim 8 , wherein said PATRICIA trie structure comprises a plurality of ternary PATRICIA trie blocks.

12. The computer program of claim 9 , wherein said index PATRICIA trie block comprises a ternary PATRICIA trie block.

13. The computer program of claim 9 , further comprising the step of:

performing a range search.

14. The computer program of claim 13 , said range search further comprising the steps of:

finding a first bit position of difference between said returned values; and

checking whether there is available an unlabeled branch from a first value in said depth level that is less than said first bit position and, if so, searching said unlabeled branch; otherwise, said key is not in said cascading index and returning such information.