3 ms·

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: http

• vlovich123 2y ago
  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.
  • anonymoushn 2y ago
    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.
• rebanevapustus 2y ago
  That's how it's done in the rust stdlib alternative https://github.com/brurucy/indexset 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).