append only finger tree

Append-only finger tree!

Ok, so we start with the empty tree.

When we insert an element into the empty tree, we get a bucket with one element.

In this example, i've set bucket size to 4, for clarity.

Nothing surprising happens when you add three more elements.

As the bucket overflows though, it gets split up into a finger structure.

A finger structure keeps track of the first and the last elements in the sequence.

The space between first and last elements, is 'the rest' of the sequence. At this point it's just the empty tree again.

Again, adding three more elements brings no surprises.

This time, when we add an extra element, the full bucket gets pushed down the middle of the tree, and wrapped in a branch.

Buckets that overflow, keep getting pushed down, until the branch node is full.

After which, it also splits into a finger, with first, rest, and last

And also gets filled up through buckets getting pushed down the middle (rest).

For the next insert, we will get second-order branching, since what is pushed down are now full 'branches', we wrap them in an extra layer as well.

Since at each step down the 'spine' of the structure, another layer of branching is added, the lookups will be worst case logarithmic time, and best case constant time (for the first and last elements).

Since this structure requires no balancing, it should be simple to implement as well.