How to Implement SkipList

November 21, 2021 · 705 words · 4 min · DataStructure SkipList

Some time ago, I decided to implement a simple LSM storage engine model. As part of that, I implemented a basic SkipList and BloomFilter with BitSet. However, due to work demands and after-hours laziness, the project was put on hold. Now that I’m thinking about it again, I realize I’ve forgotten some of the details, so I’m writing it down for future reference. What is SkipList? SkipList is an ordered data structure that can be seen as an alternative to balanced trees.