3 ms·

So he's comparing the AVL tree he wrote himself to a B-tree optimized to death by someone else? Out of interest though, does he mention somewhere which actual

So he's comparing the AVL tree he wrote himself to a B-tree optimized to death by someone else? Out of interest though, does he mention somewhere which actual implementation he used?

aldonius 6y ago
Yes, and I suppose that's some of the point: a performant library ecosystem is one hell of a feature.
- jstimpfle 6y ago
  It sure must be a nice feature - for fast results. Counterpoint, though. I barely used Rust, but when I wanted to play with the Xi editor I got to see the bad places that buying into such an ecosystem can get you to - places formerly pioneered by NPM. I had to download 100s of packages, (IIRC?) there were some build problems, all for something where I don't really see the value of noteworthy dependencies. If you really need a Btree (like, if you want to make a fair benchmark for a presentation) then you'll absolutely find a reasonable implementation in C. After all, why would you need dependency management for something that should have 0 dependencies? As an example of library data structures implemented in C - if you want, check out my Red-black tree (not a Btree): https://github.com/jstimpfle/rb3ptr/blob/master/rb3ptr.h https://github.com/jstimpfle/rb3ptr/blob/master/rb3ptr.h . It's really easy to integrate into your project. I think the API (found in rb3ptr.h) is totally usable, and it might also be faster than what you can get with safe Rust - unless you can easily use intrinsically linked data structures in safe Rust.