Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the first structure are less than all keys in the second, then combines the two dictionaries into a single sorted dictionary in time $O(\log n)$, where $n$ is the total number of keys. However, this only works if there is no overlap in the ranges of keys stored in those trees.

Similarly, many priority queues (binomial heaps, Fibonacci heaps, etc.) support $O(\log n)$-time merges. These merges work regardless of what keys are stored, but given that the data structures are priority queues we can't do lookups for random elements in the resulting structure.

Is there a sorted dictionary structure that supports merges of arbitrary dictionaries in time $O(\log n)$ or a lower-bound proof that such structures can't exist?

Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the first structure are less than all keys in the second, then combines the two dictionaries into a single sorted dictionary in time $O(\log n)$, where $n$ is the total number of keys. However, this only works if there is no overlap in the ranges of keys stored in those trees.

Similarly, many priority queues (binomial heaps, Fibonacci heaps, etc.) support $O(\log n)$-time merges. These merges work regardless of what keys are stored, but given that the data structures are priority queues we can't do lookups for random elements in the resulting structure.

Is there a sorted dictionary structure that supports merges of arbitrary dictionaries in time $O(\log n)$ while simultaneously supporting normal sorted dictionary operations (insertions, deletions, lookups, successor/predecessor queries, etc.) in time $O(\log n)$, or a lower-bound proof that such structures can't exist?