xtail insertion

main insert function

// key is an array of bytes

root <- tree.root
leafValue <- tree.fp_leaf
IF (root != NULL AND root is not a leaf node):
    FOR i = 0 to 2:
        leafByte <- i'th byte of leafValue
        IF (byte == key[i]):
                continue
        ELSE IF (byte == key[i]):
                insert from root, only update fp_path, fp_ref, and fp_depth information if they change
        ELSE:
                reset fp_path, insert from root, append to fp_path when recursing, change fp_leaf, fp_ref and fp_depth at the end
ELSE:
    do the first and second inserts of the workload

insert from fast path, only update fp_path, fp_ref, and fp_depth information if they change. We don't need to update fp_leaf information since only the bytes from 0 to 2 in the leaf matter.

Bottlenecks:

• Minimal amount of fp inserts occur because key is rarely greater than fp_leaf.

Possible Optimizations:

• A IQR method to change fp (similar to QuIT) would help more fast path insertions to happen.
• When the byte differs, we insert from root. Optimally we would like to insert from the point of difference.
• Deciding whether to fp insert or to normal insert takes some time, which can be optimized.