Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?
How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at most $\mathcal O(\log\log n)$? (For clarity, I am considering equality == and inequality < tests to be the only "costly" operations and considering things like dereferencing pointers to have negligible cost.)
My attempt so far is as follows. We can design a kind of "hybrid" data structure that consists of an (unordered) linked list of binary trees such that as we continue adding elements, the number of nodes in each binary tree grows asymptotically to some function $s(n)$, and the number of trees in the list grows asymptotically to $n/s(n)$, where $n$ is the total number of elements. 864
Inserting new elements in this structure will have a worse-case complexity of $\log(s(n))$ in the long run, and looking up elements will have a worst-case complexity of $(n/s(n))\cdot \log(s(n))$ if we iterate through the trees one by one and employ binary search on each tree until we find the desired element. This general method gives us $$I(n) = \Theta\big(\log s(n)\big), ~ ~ ~ L(n) = \Theta\big(\frac{n\log s(n)}{s(n)}\big)$$ where $I(n)$ measures insertion complexity and $L(n)$ measures lookup complexity. Fixing an exponent $p>0$ and choosing $s(n) = (\log n)^p$ gives us the desired maximum insertion time of $\log\log n$, and a lookup time of $$L(n)=\Theta\big(\frac{n\log\log n}{(\log n)^p}\big)$$ so we can conclude that this lookup complexity is achievable for any $p>0$ in a way that satisfies the constraint $I(n)=\mathcal O(\log\log n)$.
Can we do better than this? For instance, can we achieve, say, a lookup time of $L(n)=\mathcal O(n^{1-\epsilon})$ for some $\epsilon > 0$ while still meeting the $I(n) = \mathcal O(\log\log n)$ insertion requirement? (My intuition tells me the answer is "no".) Are there any applicable strategies for proving that the best possible complexity has been found? 864