My data model requires an array with insert and delete capabilities. In the FDB documentation there is a description of how to model an array, but it doesn’t include insertion and deletion. I have not been able to find mention of any good algorithms for this. Here is what I’m going to do and would appreciate any feedback if anyone has a better way.
My API needs to do the following:
Read entire array
For this, just do a range read to access all array elements
Delete at index
Clear the element at an offset from the first array element
Append items with this key: [array key] + [version stamp]. Since the version stamps are increasing values, this will sort the array elements in the correct order.
Insert at index
This is the tricky one. When an element needs to be inserted between two other elements, generate a key with a version stamp that is halfway between the previous element and the following one. If inserting at location zero, use a version stamp that is somewhat less than the former first element. If inserting at the end, just do an append as explained above.
My main concern is how quickly I could run out of space between two existing elements and not have room to insert an element. It appears that, including the
UserVersion field at the end of the version stamp there are about 4 bytes of least-significant bytes between successive version stamps. That would appear to be plenty since there are over 4 billion values in 4 bytes. However, because this algorithm is choosing a key halfway between the previous and next key, it’s using up an entire bit of the 32 available bits each time you insert at the same index. So there is potential for a collision after 32 inserts at the same index. The only solution at that point seems to be to rewrite every key in the array, spacing them out appropriately.