Practical Applications of Skiplists: From Niche Data Structure to Real-World Problem Solving
By
mfiguiere
Pure flour-power. Hearty enough to carry you through lunch.
Summary
The article explores skiplists, a data structure often considered niche, and reveals their practical applications through the author's personal experience. The author initially viewed skiplists as having limited real-world use but discovered their value when facing an intractable problem at Antithesis, where a generalization of skiplists provided the solution. The article discusses the structure's theoretical background and practical implementation challenges, highlighting how skiplists can be particularly useful for concurrent programming and database operations involving complex JOIN operations.
Key quotes
· 3 pulledFor most of my career, skiplists had always seemed like a niche data structure, with a rabid cult following but not a whole ton of applicability to my life.
Then six or so years ago, we encountered a problem at Antithesis that seemed intractable until it turned out that a generalization of skiplists was exactly what we needed.
A while back, I joined Phil Eaton's book club on The Art of Multiprocessor Programming, and the topic of skiplists came up.
You might also wanna read
Combining Cuckoo Hashing with SIMD-Accelerated Probing for Improved Hash Table Performance
This technical article explores how cuckoo hashing, traditionally avoided in industry hash table implementations like Google's Swiss Tables
reiner.org·7mo ago
A Formal Proof That Jira Is Turing-Complete via Minsky Machine Implementation
This article provides a formal proof that Jira (Atlassian's project-tracking tool) is Turing-complete by demonstrating how to build a Minsky
A Formal Proof That Jira Is Turing-Complete via Minsky Machine Implementation
This article provides a formal proof that Jira (Atlassian's project-tracking tool) is Turing-complete by demonstrating how to build a Minsky
How Shamir's Secret Sharing Algorithm Enables Threshold Cryptography
This article explains Adi Shamir's Secret Sharing algorithm, a cryptographic method published in 1979 that splits a secret into multiple pie
ente.com·6d agoThe History of Pipes, Forks, and Zombies in Unix Systems
This article discusses the history and concept of pipes in Unix systems, focusing on Doug McIlroy's original vision of coupling programs lik
Demystifying Floating Point Numbers: An Interactive Guide
An in-depth technical blog post that demystifies floating point numbers, explaining their internal representation and behavior. The author i
ciechanow.ski·1mo ago