Optimizing Radix Trees: Efficient Prefix Search and Key Iteration

Hey Guys,

I hope you are doing well.

This article talks about how a modified Radix tree-based data structure is used in Treds.

Below is the new structure of the Modified Radix Tree -

The red links present in the image above are the modification of the Radix Tree.

Here are the details —

A radix tree is a compact and efficient data structure used to store keys with common prefixes. This structure helps reduce storage and lookup time by consolidating shared prefixes in a single node. Each node in the tree represents a portion of a prefix, allowing for efficient traversal when searching for a key.

Key Components:

• Internal Nodes: These nodes represent common prefixes shared among multiple keys. They have child nodes that branch into further subpaths or lead to leaf nodes. Internal nodes guide the traversal during searches by splitting based on prefixes.
• Leaf Nodes: Leaf nodes are the endpoints in the tree. They store the complete key and its corresponding value. A leaf node does not have children, signifying the end of a specific key’s path within the tree.

Prefix Iteration:

Prefix iteration allows for efficient searching of keys that share a common prefix. The tree structure enables rapid traversal of nodes with shared prefixes. Functions like SeekPrefix and Next are used to jump to the relevant prefix and iterate through all subsequent keys in sorted order. This makes it particularly efficient for scenarios where multiple key-value pairs with a common prefix need to be retrieved.

Example of Prefix Iteration:

Given keys such as foo/bar/baz, foo/baz/bar, foobar, and zipzap:

• Searching with the prefix "foo" would return keys like foo/bar/baz, foo/baz/bar, and foobar.

Proposal for Optimization:

The optimization introduces new pointers to speed up operations in the radix tree:

Internal Nodes: Now store two additional pointers:

• MinimumLeaf: Points to the leaf node with the smallest key in lexicographical order in the subtree.
• MaximumLeaf: Points to the leaf node with the largest key in lexicographical order in the subtree.

Leaf Nodes: Each leaf node has:

• Next: Points to the next leaf node in lexicographical order.
• Prev: Points to the previous leaf node in lexicographical order.

This effectively creates a doubly linked list of leaf nodes, which enables efficient prefix searches and key retrieval.

Updating Pointers During Insert/Delete:

When keys are inserted or deleted, the pointers need to be updated. The process involves:

1. Update Min/Max Leaves: Internal nodes’ minLeaf and maxLeaf pointers are updated in O(1) time. The minLeaf points to the smallest key leaf, and the maxLeaf points to the largest key leaf in the subtree.
2. Update Next/Prev Pointers: When inserting or deleting nodes, the Next and Prev pointers between leaf nodes are updated to maintain the lexicographical order. This operation runs in O(len(children)), where len(children) refers to the number of child nodes.

Enhanced Seek and Next Algorithms:

The optimization also improves the SeekPrefix and Next functions:

• SeekPrefix: Instead of maintaining a stack, the algorithm directly finds the relevant prefix and sets the iterator’s node field.
• Next: Once the correct node is found using SeekPrefix, the Next function moves from one leaf to the next in O(1) time using the Next pointer. This avoids the overhead of using a stack for navigation, making iteration through the leaves faster and more efficient.

Benefits of the Proposal:

• Efficient Traversal: The doubly linked list of leaf nodes allows for fast, lexicographically ordered traversal of keys, particularly when iterating over keys with a common prefix.
• Minimal Overhead: The time complexity of updating the tree during insert and delete operations remains low, ensuring that performance is not significantly impacted.
• Optimized Prefix Iteration: By eliminating the need for stack management during traversal, the SeekPrefix and Next functions perform better in terms of time complexity.

In conclusion, these optimizations enhance the radix tree’s efficiency for large-scale prefix-based key searches, making it ideal for applications requiring fast and ordered key retrievals.