Search code examples
algorithmdata-structuresredisskip-lists

Skip List in Redis why use p=1/4 not 1/e?

enter image description here

This is analysis of SkipList:https://eugene-eeo.github.io/blog/skip-lists.html

but i find the p in Redis is 1/4,from the table ,1/e should be more suitable.

So Skip List in Redis why use p=1/4 not 1/e?

Solution

  • Probably just because they did not know about this research when skip lists were first implemented in Redis.

    There are also some concerns about the increased memory requirements (though those do not seem to be dramatic).

    Here is the pull request to update to 1/e: https://github.com/antirez/redis/pull/3889