Remix.run Logo
▲ reconditerose 3 days ago

Redis historically used a skiplist to keep a sorted index. Valkey showed its inefficient and slow on modern hardware, migrating to a B+ tree instead.

▲hinkley an hour ago | parent | next [-]

It all ends up back at B trees. Why does it always end up back at B trees?

At this point have we optimized hardware to assume B trees in a sort of self-fulfilling prophesy?

▲alfiedotwtf 35 minutes ago | parent | next [-]

B trees are more friendly to being cache oblivious

▲crest an hour ago | parent | prev | next [-]

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).

▲eventualcomp an hour ago | parent [-]

A b-tree isn't a binary tree. B doesn't officially stand for binary either, see History[0].

[0] https://en.wikipedia.org/wiki/B-tree

▲jjmarr an hour ago | parent [-]

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.

▲wrs an hour ago | parent | prev [-]

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.

▲tyre 2 hours ago | parent | prev [-]

Is this AI? Why do we need a summary of the actual article in a comment?

▲bertonvv 2 hours ago | parent | next [-]

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.

▲hinkley an hour ago | parent [-]

There aren't many commenters at the time you posted this. Which makes this conversation feel even more artificial...

▲bertonvv 14 minutes ago | parent [-]

I meant in general on this site. Dislike the insinuation that I'm generative AI.

▲WD-42 2 hours ago | parent | prev [-]

The actual article is AI too so this is just saving you time.

▲hinkley an hour ago | parent [-]

https://github.com/valkey-io/valkey-io.github.io/pull/665/co...

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.