Function merge 

pub fn merge(
    left: &MergeLayerIterator<'_, ObjectKey, ObjectValue>,
    right: &MergeLayerIterator<'_, ObjectKey, ObjectValue>,
) -> MergeResult<ObjectKey, ObjectValue>

Merge function for items in the object store.

The most interesting behaviour in this merge function is how extents are handled. Since extents can overlap and replace one another, the merge function generally builds up the most recent view of the extents in the tree, so that the output of a full merge contains no overlapping extents. You can imagine looking down at the extents from the top-most layer.

A brief example:

Layer 0 |a-a-a-a| |b-b-b| Layer 1 |c-c-c-c-c| Layer 2 |d-d-d-d|

Merged |a-a-a-a|c| |b-b-b|d-d-d|

Adjacent or overlapping extent deletions in two adjacent layers can be merged into single records (since they do not have a physical offset, so there’s no need to keep the physical extents contiguous). We can’t merge deletions from non-adjacent layers, since that would cause issues in situations like this:

Layer 0 |X-X-X| Layer 1 |a-a-a-a-a-a| Layer 2 |X-X-X|

Merging the two deletions in layers 0 and 2 would either result in the middle extent being fully occluded or not at all (depending on whether we replaced on the left or right layer).