tail 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]):
                insert from root, store recursed nodes in temp array, if key > fp_leaf then change fp
ELSE:
    do the first and second inserts of the workload

IF last byte of key is greater than last byte of fp_leaf:
    do fast path insert
ELSE:
    insert from root, store recursed nodes in temp array, if key > fp_leaf then change fp

Bottlenecks:

• Minimal amount of fp inserts occur because key is rarely greater than fp_leaf
• During normal insertion, if the key is less than fp_leaf, storing temp fp path information is unnecessary