Get the latest tech news

Fine, I'll Play With Skiplists

Follow me on Bluesky! A Log-Structured Merge tree, or LSM, is a popular data structure for storage engines. It’s what is used by RocksDB, which is sort of...

You’re going to be inserting tombstones to represent removed keys anyway (which are interpreted externally), and when it gets full you just discard the whole thing, so you don’t have to dedicate any complexity to deletions. To support multiple writers, what can go wrong is that in between finding prev and curr, another thread can come in and insert a different element in between them, which means you're no longer looking at two adjacent nodes in the list. After giving up on trying to figure out why this might be true analytically (a friend found a closed form for me but the result was numerically unstable and hard to evaluate and analyze which is beyond my expertise) I turned to the succor of modern computing machines and ran some simulations:

Get the Android app