stail insertion

In stail insertion , we are taking advantage of knowing the exact positions of each key.

main insert function

IF root is NULL // if it will be the first insert
    insert and change fp
FOR i = 0 to 2:
    leafByte <- i'th byte of leafValue
    IF (key[i] == leafByte):
        continue
    ELSE IF (key[i] < leafByte):
        insert and preserve fp
    ELSE:
        IF key is a bridge value:
            insert and change fp
        ELSE:
            insert and preserve fp

// If the algorithm reaches here, it means that fp insert will happen
// If depth is at 3, we do not need to worry about leaf expansion of prefix mismatch, we can directly insert the new leaf into fp node
IF (fp_depth == 3):
    directly insert into fp
// Else, we call the recursive function and let it handle leaf expansion or prefix mismatch if there is one. If not, it will directly insert into the fp
ELSE:
    insert and preserve fp, starting from the fp

By "bridge value", I mean any value in the next 256 values. Let's analyze the case where we are inserting [1, 982, 3, 4, ..., 253, 84921, 255, 256, 257, 38411, ...]:

When 1 is inserted, fp is changed because it is an edge case. When 982 is inserted, fp doesn't change because 982 is not in the range [256, 512] (the next 256 values). When 3, 4, ..., 253 is inserted, fp insert happens and fp is preserved. When 84921 is inserted, fp doesn't change because 84921 is not in the range [256, 512] (the next 256 values). When 255 is inserted, fp insert happens. When 256 is inserted, since 256 is a bridge values, fp changes. When 257 is inserted, fp insert happens. When 38411 is inserted, fp doesn't change because 38411 is not in the range [512, 768] (the next 256 values). The operation conitnues like this until the end.

Unless the L is really really small, there is a set amount fp changes and fp inserts for workloads with the same N value.