I have to say I was always on the fence about Bill Pugh (Mr Skiplist).
Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability.
It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple)
B+tree were designed around optimized IO in the era of magnetic storage, they're inherently cache-friendly. Skiplists are the same thing as a b+tree but the structure is inverted, which makes skiplists more to concurrent writer-friendly than b+trees. Different tradeoffs.
Binary trees have worse cache locality. The cost of accessing memory has grown so much compared to computation that supposedly slower "heavy weight" data structures are worth it now (as in the last 10-20 years).
I'm guessing their point is unlike binary trees which have two children per node, B trees can have as many children per node is best for cache locality/SIMD/etc. Which despite being "heavyweight" (wasted space if not all children per node are occupied) is faster in practice because it's cheaper to preload large unused blocks to cache rather than only access memory when it is needed.
Every node in a binary tree needs a value and two child pointers, though. That's asymptotically almost twice as many child pointers per value as a B-tree has.
Yes, that hardware is called "the memory cache". B-trees were invented because disk reads were very expensive. Now, memory cache fills are very expensive.
From what I've seen on here many commenters didn't read the article, only the title (I've been guilty of this too). OP is maybe just adapting to HN culture.
Like all things, it depends. If you don't need the latest and greatest features in upstream redis, and you don't want license headaches, Valkey is probably a good default. It's generally cheaper on hosting providers too - AWS will discount you ~20-35% for Valkey vs Redis.
As a coding exercise I implemented a redis that utilized skiplists. I was excited to read this article. Turns out it's ai slop. Seriously people, stop it. This hurts to read.
Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability.
It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple)
That cost varies from chip generation to generation, but it does seem to be the case that b trees win in more generations than they lose.
There is a reviewing guide with suggested reading order, clear design decisions, and scope boundaries for what is intentionally not included.
This is the type of thing LLMs are very good at and high ROI for human reviewers.
[0]: https://github.com/valkey-io/valkey/pull/4206
At this point have we optimized hardware to assume B trees in a sort of self-fulfilling prophesy?
[0] https://en.wikipedia.org/wiki/B-tree
The PR for the article. I'm not convinced it's AI, but I didn't do a deep dive on the commit tree just poked around a bit.