r/algorithms • u/Max_Arbuzov • 1d ago
Discussion An idea of deletion-only sorted array
It can be used as a building block for insertion-only (write-optimized) data structures composed of multiple sorted arrays.
Properties:
- Type of keys – any comparable type, like numbers, strings or comparable objects.
- Instant deletion of a key, it is zeroed-out immediately and no more accessed later for comparison during subsequent searches.
- Zero latency, freeze-free, cheap rebuilding. Deletion of a key takes no more than O((log N)^2).
- Search takes O(log N). It is similar to binary search. Deleted items are not compared during the search.
- Stability – equal keys keep the same order.
- Updating is possible, but new key must be equal to old key. It is for "key-value" pairs.
The task: Array should allow deletion, and search should be always performed in O(log N).
It is simple to do with numbers – just use bit mask to mark deleted items. If a number is deleted, it can still be compared with another items.
But in case of objects, comparing a deleted object might be tricky or impossible. The idea is to avoid any comparison of deleted items.
The idea: Empty and non-empty items should be placed in a specific way. If some item is empty (deleted) and its index divides by 2^k, it is assumed that all 2^k items are empty. This approach allows that search will remain in O(log N) complexity.
Data organizing.
Items in the array are considered as blocks of size 2^k. Blocks are composed of 2 smaller blocks – left and right.
The array is fit into one larger block. For example, an array of length 375 is considered to be placed into block of length 512. It can be also considered as placed into larger block of length 4096.
If a block contains any data, its first item must be non-empty. If first item of the block is empty, entire block considered empty. If a block contains data and its first item is empty, such block is inconsistent.
Searching. It is done recursively.
At the beginning we have a single block, for example its size is 512 for an array of 375 items.
We call a function SearchItemInBlock(item, block_512). The function checks if a block can contain the item; if not then return not_found. If the block can contain the item, then the block is split into 2 smaller blocks – left block_256 and right block_256, the function checks which one can contain searched item and recursively calls SearchItemInBlock(item, block_256) one or two times.
And so on. The complexity is O(log N).
Deletion.
An item is replaced with delete_marker, for example MIN_INT, -INF, default(T) or null_ptr.
After such deletion some block may become inconsistent. To restore consistency (rebuilding) one non-empty item should be moved to the beginning of the block. Any move is performed only inside the block. Finding the next non-empty item is O(log N) in worst-case.
After moving an item another block may become inconsistent. That block will be twice smaller then the previous one. Restoring its consistency requires O(log N). And so on, up to O(log N) blocks.
Totally, restoring consistency requires up to O(log N) searches per O(log N) blocks, that gives compexity O((log N)^2) for worst-case.
Packing/compressing/compaction.
It is optional, not necessary. It might increase the performance of searching and deletion.
After deletion of an item up to O(log N) items moved to more left position. I don't know if it helps in worst-case.
Worst scenario is deleting the items from the very beginning of the array each time, as I understand. It will definetely cause worst-case at least once, I believe.