Merging of two convex polygon chains in O(log n)
You are asking for a data structure for sequences (aka vectors or arrays) that permits efficient concatenation.  I suggest using any standard binary tree data structure, e.g., AVL tree, red-black tree, splay tree, treap, etc.  They support $O(\lg n)$ time concatenation and $O(\lg n)$ time lookups.  The differences between them come down to details related to implementation complexity and constant-factor differences in running time.

With these algorithms, the keys are not stored explicitly.  Instead, they are implicit.  To lookup key $i$, you search for the $i$th leaf from the left, but the key $i$ is never stored anywhere.  Thus, when concatenating two trees, there is no need to renumber the keys.  You can find the $i$th leaf in $O(\lg n)$ time: augment the data structure so that each node keeps a count of the number of leafs underneath it; then it's clear how to traverse the tree during a lookup (whether to go left or right at each node is an easy decision, given the information  stored in each node).