SingleStore’s Skiplist Indexes (2014)

by federicoponzion 9/20/2022, 8:00 AMwith 4 comments

by jph00on 9/22/2022, 8:26 PM

Cyrus IMAP has been using skiplists for its storage for around 20 years IIRC.

https://www.cyrusimap.org/imap/concepts/deployment/databases...

I was very excited to come across this when I was working at fastmail. We used Cyrus from the start, and I loved seeing such a cool data structure getting utilised in practice.

https://fastmail.blog/open-technologies/why-we-contribute/

by brd529on 9/22/2022, 6:02 PM

For those of you that think you've seen this before, MemSQL was rebranded to SingleStore, and this was the first blog post MemSQL made - skip list indexes were always a fundamental performance innovation of MemSQL. I am not sure if MemSQL/Singlestore is still the only commercially available db using skiplist indexes but I do think it was the first when they debuted in 2014.