A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these bounds only hold as long as the structure of the SkipList is sufficiently "balanced". In particular, with probability $1/n^c$ for some constant $c>0$, the balanced structure might be lost after inserting an element.
Let's say I want to use a skip list as a storage backend in a web application that potentially runs forever. So after some polynomial number of operations, the balanced structure of the SkipList is very likely to be lost.
Is my reasoning correct? Do such probabilistic search/storage data structures have practical applications and if so, how is the above problem avoided?
Edit: I'm aware that there are deterministic variants of the SkipList, which, are much more complicated to implement in comparison to the (classic) randomized SkipList.