Lookup with key sequence skip for radix trees

• US 9,396,286 B2
• Filed: 05/07/2014
• Issued: 07/19/2016
• Est. Priority Date: 05/07/2014
• Status: Active Grant

• Current Assignee: Red Hat Israel Ltd. (International Business Machines Corporation)
• Original Assignee: Red Hat Israel Ltd. (International Business Machines Corporation)
• Inventors: Tsirkin, Michael
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/272,445
• Publication Number:
  US 20150324485A1
• Time in Patent Office: 804 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

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.

Claims

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; and

skipping a second number of elements after the second chunk in the key.

2. The method of claim 1, further including:

when the first chunk is determined to not match any of the prefixes included in a set of containers, sending a message indicating that the key is not stored in the radix tree.

3. The method of claim 1, wherein the first chunk is a prefix of the key.

4. The method of claim 1, wherein the first chunk includes a fourth sequence of elements and is the first element of the fourth sequence of elements, and the second prefix is the first element of the first sequence of elements.

5. The method of claim 1, further including:

receiving an instruction to determine whether the key is stored in the radix tree.

6. The method of claim 1, further including:

when the second chunk is determined to not match the second prefix, sending a message indicating that the key is not stored in the radix tree.

7. The method of claim 1, further including:

when the first chunk is determined to match the first prefix, determining a length of the remainder sequence included in the identified container, the first number of elements being the length of the remainder sequence.

8. The method of claim 7, further including:

when the first chunk is determined to match the first prefix, determining a length of a remainder sequence in the key, the remainder sequence being a sequence of one or more elements after the first chunk in the key, wherein the skipping a first number of elements, the identifying a first child container, the determining whether a second chunk of the key matches the second prefix, the traversing a second child container, and the skipping a second number of elements includes when the length of the remainder sequence in the key is greater than the length of the remainder sequence included in the container, skipping the first number of elements, identifying the first child container, determining whether the second chunk of the key matches the second prefix, traversing the second child container, and skipping the second number of elements.

9. The method of claim 1, further including:

when the second chunk is determined to match the second prefix, determining a length of the remainder sequence included in the first child container, the second number of elements being the length of the remainder sequence.

10. The method of claim 1, wherein the identifying a first child container of the identified container includes identifying an immediate child container of the identified container, and wherein the traversing a second child container includes traversing an immediate child container of the first child container, and wherein a length of the first prefix of the first sequence of elements is the length threshold.

11. The method of claim 1, wherein the second chunk is determined to match the second prefix, the method further including:

determining whether the first immediate child container is a leaf container, wherein the traversing a second immediate child container includes when the first immediate child container is determined to not be a leaf container, traversing the second immediate child container; and

when the first immediate child container is determined to be a leaf container, sending a message indicating that the key is stored in the radix tree.

12. The method of claim 11, wherein the first immediate child container is determined to be a leaf container, the method further including:

determining a key range for the leaf container;

determining whether the key falls within the key range, wherein the sending a message indicating that the key is stored in the radix tree includes when the key is determined to fall within the key range, sending the message indicating that the key is stored in the radix tree; and

when the key is determined to not fall within the key range, sending a message indicating that the key is not stored in the radix tree.

13. The method of claim 11, further including:

when the first immediate child container is determined to be a leaf container, sending a value stored in the leaf container.

14. A system for determining whether a key is stored in a radix tree, comprising:

a traverser that traverses a radix tree including a plurality of containers and identifies, based on the traversal, a container including a first sequence of elements, the first sequence of elements having a prefix;

a match module that identifies, based on a number of skipped elements in a key, a chunk of the key and determines whether the chunk matches the prefix included in the traversed container, wherein the chunk includes a second sequence of elements; and

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,

wherein 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.

15. The system of claim 14, wherein the first chunk is a prefix of the key.

16. The system of claim 14, wherein when a first chunk is determined to match a first prefix included in a container, the match module determines whether the identified container is a leaf container, wherein when the identified container is determined to be a leaf container, the match module accesses an auxiliary data structure to determine whether the key is stored in the auxiliary data structure, and wherein when the key is determined to be stored in the auxiliary data structure the match module sends a message indicating that the key is stored in the radix tree, and when the key is determined to not be stored in the auxiliary data structure the match module sends a message indicating that the key is not stored in the radix tree.

17. The system of claim 14, wherein when the second chunk is determined to not match the second prefix, the match module sends a message indicating that the key is not stored in the radix tree.

18. The system of claim 14, wherein when the first chunk is determined to match the first prefix, the skipping module determines a length of a remainder sequence included in the identified container, wherein the number of elements is the length of the remainder sequence of the identified container.

19. The system of claim 14, wherein for one or more traversed child containers of the identified container, the traverser identifies a first child container of the identified container, the first child container includes a third sequence of elements, and the third sequence of elements has a second prefix, wherein the match module determines whether a second chunk of the key matches the second prefix, the second chunk of the key is a fourth sequence of elements after the skipped number of elements in the key, wherein when the second chunk is determined to match the second prefix, the traverser traverses a second child container, the second child container is a child of the first child container, and wherein the skipping module skips a second number of elements after the second chunk in the key.

20. A non-transitory machine-readable medium comprising a plurality of machine-readable instructions that when executed by one or more processors is adapted to cause the one or more processors to perform a method 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; and

skipping a second number of elements after the second chunk in the key.