Patent ID: 7620640
Filing Date: 2009-11-17
Classification: G06F,Y10S

Abstract:
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.