features/advantages of sorted collection

- O(N) ascending iteration
- O(log N) range query
- O(log N) closest neighbor query above/below
- O(log N) boolean contains() query
- O(1) min() max() queries
- deleteByKey is typically O(log N) but can be O(1) if we construct a hashtable of {key -> iterator} once the collection is built. This hashtable can also accept new items.

Q: insert is typically O(log N), but can we improve on it?

— A: if there’s only one insert, we can hold it in a hidden field of the collection, to be checked at the end of each operation above.

— A: if there are unlimited inserts but all 64-bit integers, then we can treat the incoming integer as a short radix array (8-elements for example). Take each element of the array as a lookup key, look up in an array to find a subtree.

Basically the entire sorted collection is an 8-level tree with fan_out=256

You may say that there are 8 lookups required so O(k) where K=8, but here we assume the size of the radix array is a constant equal to eight. Note the collection size is unlimited and far more than 2^64 if duplicates are permitted.