...
- This has "sweet" semantics.
- Key values increase strictly with time.
- "Append" operations are simple: just create a new object. The order of events can be determined by comparing key values.
- 64-bit keys mean we don't have to worry about running out of the key space and wrapping around.
- If keys are never deleted in a table then it's easy to enumerate the table's objects in chronological order. However, if keys are deleted the enumeration is not so easy: the obvious approach of stepping through each of the key values in order may spend a lot of time looking for objects that no longer exist.
- Berthas would be the data structure of choice for tables that never have deletes. With deletes, other options are not so easy:
- Berthas with leaves collapsed to hash tables when they become sparse
- Older objects that have many nearby deletes now incur a performance penalty.
- Inner nodes of the Bertha still grow over time.
- This option feels complicated because it combines a couple of different modes of operation.
- Berthas with leaves reused as they become sparse (JO--
)I don't understand how this option works
-JO
This one would be a little tricky to get right, and it's easier to explain with a diagram. Say there's a leaf of 8 entries that's only using entries 1,2, and 6 for keys 1201, 1202, and 1206. I can reuse this leaf starting at 2700 for 2700, 2703, 2704, 2705, and 2707 if I burn the keys 2701, 2702, and 2706. -Diego
- Now a leaf can have multiple pointers coming into it
- Some fraction of keys will have to be skipped over and not used
- Splitting a key range to another server now requires unmerging the leaf.
- Inner nodes of the Bertha still grow over time.
- Hash tables
- Berthas with leaves collapsed to hash tables when they become sparse
...