Adaptive Radix Tree - Question regarding child indexing

Question

i have to write an exam in a course given by one of the contributing professors of this paper: http://www-db.in.tum.de/~leis/papers/ART.pdf

Of course this could also be a possible topic in the exam. Now i understand the basic advantages and structure of this tree, but i just cannot fathom some details. Maybe someone here can help me with that:

• So Node4 store up to 4 partial keys (of 1 byte each) and up to 4 child pointers. The child pointer used is determined by the position of the partial key, right?
• Starting at Node48 the child pointer is indexed by using the partial key itself as index into the "key"-array and using that value as index into the child-pointer array, right? But why do we have a 256-element array for the key-bytes although there are only 48 child pointers?
• Node256 is just an 256-element array indexed through the key byte.

And at last what are those red numbers depicted in this image?

Thanks a lot!

Answer 1

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->child_indexes[key];
    // Index == 255 is element missing
    if idx == 255 { return null; }
    return node->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.