Rax — compressed radix tree

A trie that compresses chains of single-child nodes into a single multi-byte node. Used for stream id indexing and a few internal tables.

Source layout

File	Role
src/rax.c	Implementation (~82 KB).
src/rax.h	Public API and types.
src/rax_malloc.h	Allocation hooks.

Why a radix tree

For stream entry ids (which are 128-bit <ms-timestamp>-<sequence> values), the rax provides:

• Sorted iteration over ids in O(N) total.
• O(K) point lookup, where K is the key length in bytes.
• Range queries that prune subtrees efficiently.
• Insertion / deletion that doesn't reshuffle nearby keys.

Compared to a balanced BST, a rax has roughly the same big-O but better cache behaviour because the key bytes are stored compactly in the path.

Layout

A node is either a compressed node (storing N consecutive bytes shared by all descendants) or a normal node (storing a list of child pointers indexed by single byte). Both can hold a pointer to user data when the node corresponds to an inserted key.

typedef struct raxNode {
    uint32_t iskey:1;     /* This node has a value associated. */
    uint32_t isnull:1;    /* The associated value is NULL. */
    uint32_t iscompr:1;   /* Node is compressed. */
    uint32_t size:29;     /* Number of children (or compressed bytes). */
    /* followed by the data — children pointers + bytes */
} raxNode;

The compact representation packs the byte data and the child-pointer table inline after the header, so a small node is one allocation.

API

typedef struct rax {
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

rax *raxNew(void);
int  raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
int  raxRemove(rax *rax, unsigned char *s, size_t len, void **old);
void *raxFind(rax *rax, unsigned char *s, size_t len);
void  raxFree(rax *rax);
void  raxStart(raxIterator *it, rax *rt);
int   raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len);
int   raxNext(raxIterator *it);
int   raxPrev(raxIterator *it);
void  raxStop(raxIterator *it);

The iterator supports >=, >, <=, <, ^ (first), $ (last) seek operations. raxNext and raxPrev step in lexicographic order.

Use in streams

src/t_stream.c uses a rax keyed by entry id (a 16-byte big-endian encoding of the 128-bit id) with values pointing to listpacks. Each listpack holds a contiguous run of entries; the rax indexes by the first id in each run. Range queries find the listpack containing the start id, then walk forward via the listpack's internal sequencing.

graph TD
    Rax[rax keyed by stream id] --> LP1[listpack: ids 1-2..1-99]
    Rax --> LP2[listpack: ids 1-100..1-198]
    Rax --> LP3[listpack: ids 1-199..1-300]

Consumer-group state, pending entries, and the per-group last-id are stored in side raxes attached to the stream object.

Embedded tests

#ifdef REDIS_TEST — there is a comprehensive randomised test in src/rax.c exercising insertion, deletion, iteration, and the seek operators. Not registered in the dispatcher today; the tests are run via direct compile of a rax-test binary if needed.

Related pages

• Stream radix — the use of rax inside t_stream.c.
• Listpack & quicklist — the storage at each rax leaf.