Hacker News Reader

I'd be curious to see how performance would change from storing b-tree entries in a semi-sorted array, and applying various other optimizations from here:

https://en.algorithmica.org/hpc/data-structures/b-tree/

The aggregate performance improvements Sergey Slotin gets from applying various "tricks" is insane.

View on HN

That's how it's done in the rust stdlib alternative https://github.com/brurucy/indexset

Faster reads, slower inserts, but then you get the capability of indexing by position in (almost) O(1). In regular B-Trees this can only happen in O(n).

Notably I believe his data structures tend to ignore string keys because it’s less amenable to SIMD. Would be interesting to see if his ideas about layout still show improvements to strings.

You can do strings. You probably want to store a bunch of string prefixes inline though, so that when the prefixes are not equal, you can use essentially the same code that he uses for integers.

Reply on news.ycombinator.com