alt Hacker NewsCould someone provide intuitive understanding for why the "express lanes" in a skip list are created probabilistically?
My first instinctive idea would be that there is an optimal distance, maybe based on absolute distance or by function of list size or frequency of access or whatever. Leaving the promotion to randomness is counter intuitive to me.
Replies
There likely is an optimal stride, as a function of the platform and the data you are storing. There is also a worst-case stride. You probably don't know what the good and bad strides are, and because they are data-dependent, they can change over time. Randomness gives you a very high probability of avoiding very bad case performance. And (to rephrase what another comment says) avoiding a constant stride avoids unlucky 'resonances' where the interval interacts with some other fixed property of your system or data.
If it has a constant stride then that stride can align with something upstream and result in horrible performance
The same reason naive BST tree (non self balancing one) doesn't work. You need to be able to add and remove elements without any knowledge of future operations and without malicious input being able to force a degenerate structure which is equivalent to a flat linked list. It's a bit similar how treap achieves somewhat balanced tree using randomness instead of deterministic rebalancing algorithms.
If you knew all the items ahead of time and didn't require adding/removing them incrementally you could build optimal skiplist without randomness. But in such situations you likely don't need a skip list or BST at all. Binary search on sorted list will do.