Adaptive Radix Tree - Question regarding child indexing
The red values in the image shows key values associated with a location.

Node4 works by performing a linear search for the key byte in the 4-element key array. If we were looking for key value 255 in the image you posted, we'd find at array index 3. We then find the corresponding child by looking at index 3 in the child pointer array.

Node256 is just an 256-element array of child pointers indexed by key byte, yes.

The problem with Node256 is that it wastes a lot of space if most of the array is empty. Node48 uses much less space by exploiting the fact that a pointer is much larger than a byte (typically 8 bytes). We have an 256-element array of bytes (the child index array), one for each key value. When we index into this array, we get a byte that is an index into the 48-element child pointer array. So the lookup is something like this (the actual implementation is slightly different):

Node *find(Node *node, byte key) {
    idx = node-&gt;child_indexes[key];
    // Index == 255 is element missing
    if idx == 255 { return null; }
    return node-&gt;children[idx];
}


Since the child index array has 256 elements we can just index it with the key byte, no need to search like in Node4 and Node16. But as you say, we only have 48 child pointers, so at most 48 positions in the child index array will be in use at any one time. The elements are small though, so it is not much of a waste.