Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the points $p_1\rightarrow p_2\rightarrow p_3$ is stored as $\{0\Rightarrow p_1,1\Rightarrow p_2,2\Rightarrow p_3\}$. The key-value store is implemented with a data structure which allows the operations split and join in $O(\log n)$ time.
I want to join the chain $P = p_1\rightarrow p_2\rightarrow p_3$ and the chain $Q = q_1->q_2->q_3$ to a chain $p_1\rightarrow p_2\rightarrow p_3\rightarrow q_1\rightarrow q_2\rightarrow q_3$.
Is there a way to join two polygon chains in logarithmic time without updating the keys? If I do a simple join, I get a problem with duplicated keys, so the keys of $Q$ have to be updated before the join, but this destroys my logarithmic time approach as I need linear time for updating the keys.
Am I wrong here already?
If not, is there a way to keep the logarithmic time?