LOOKUP WITH KEY SEQUENCE SKIP FOR RADIX TREES

摘要

Systems and methods are disclosed for determining whether a key is stored in a radix tree. An example system includes a traverser that identifies a container including a sequence of elements. The system also includes a match module that identifies, based on a number of skipped elements in a key, a chunk of the key. The match module determines whether the chunk matches the prefix included in the traversed container. The system further includes a skipping module that when the chunk of the key is determined to match the prefix, skips a number of elements after the chunk in the key. When the chunk of the key is determined to match the prefix, the traverser traverses one or more immediate child containers of the identified container and the search module identifies, based on the number of skipped elements, the chunk of the key.

主权项

1. A method of determining whether a key is stored in a radix tree, comprising:
identifying a first chunk of a key; traversing a radix tree including a plurality of containers; identifying, based on the traversing, a container including a first sequence of elements, the first sequence of elements having a first prefix; determining whether the first chunk matches the first prefix; when the first chunk is determined to match the first prefix:
skipping a first number of elements after the first chunk in the key;for one or more traversed child containers of the identified container:
identifying, based on the traversing, a first child container of the identified container, the first child container including a second sequence of elements, and the second sequence of elements having a second prefix;determining whether a second chunk of the key matches the second prefix, the second chunk of the key being a third sequence of elements after the skipped number of elements in the key;when the second chunk is determined to match the second prefix, traversing a second child container, the second child container being a child of the first child container; andskipping a second number of elements after the second chunk in the key.