Array-like data structure with O(1) worst-case concatenate/join? I am looking for a data structure $D$ which supports the following operations 
(preferably a (binary) tree-like structure): 


$D$ is indexed, i.e. 
there is a mapping from $\{1, \ldots, n\}$ to items in $D$, 
where $n$ is the size of $D$ (the number of items in $D$).
$k$-th item in $D$ can be accessed in $\mathcal{O}(\lg n)$ worst-case (non-amortized).
The operation should not modify the data structure, 
it should be completely "read-only" 
(e.g. no finger searches are allowed). 
(Once the pointer to the $k$-th item is obtained, 
further changes should be supported in $O(1)$ 
without modification to the state of the data structure apart from the actual stored item (e.g. if it is a tree-like data structure, this means no rotation is allowed).
two instanced $D$ and $D'$ can be merged in time $\mathcal{O}(1)$ worst-case (non-amortized). Destruction of $D$ and $D'$ is fine.
The result should contains the union of the elements; 
those that come $D$ retain their indices, 
while indices of those coming from $D'$ get incremented by the size of $D$, 
e.g. if we are merging 
$D=\{ 1 \to x_1, 2 \to x_2 \}$ with 
$D'=\{ 1 \to y_1, 2 \to y_2, 3 \to y_3 \}$ 
we should get 
$\{ 1 \to x_1, 2 \to x_2, 3 \to y_1, 4 \to y_2, 5 \to y_3 \}$.


In essence, this data structure should have the properties of 
the fast-mergeable array/vector with asymptotically slower random-access, 
but extremely fast merge/concatenation ($\mathcal{O}(1)$). 
It would also be cool if elements could be listed in order in linear time.

I would be mostly interested in the references to existing work / papers 
which describe such a data structure or algorithm on an existing data structure.
I think Purely Functional Worst Case Constant Time Catenable Sorted Lists by Brodal et al. supplies what you want.