>Eventually I rewrote my btree on top of Vecs. My node & leaf pointers are now array indices. The result? There is no longer any unsafe code. The code has become significantly simpler and it now runs ~10% faster than it did before, which is shocking to me. I guess bounds checks are cheaper than memory fragmentation on modern computers.

Optimizations are very complex and potentially fragile in Rust, LLVM has to sort through tons of generated IR, so it might be just that native Rust structures are optimized better for compilation. Particulary, Rust is able to optimize out some bound checks.

Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly. I mean you could have written similar code in C++ using std::vector or std::dequeue and get the bounds checking too.

>Everyone talks about memory safety but IMO rust’s best features are enums, traits, cargo, match expressions and so on

C++20 with concepts mostly reproduce the traits. C++17 with std::variants emulate enum/tagged union. Match is unmatched by C++, that's true.

Cargo is good for as long as there are few packages in there. Large projects already suffer from five versions of serde in one build and dependencies on FFI-connected libs that cargo itself cannot build. I mean look at the NPM nightmare — and they've mostly dodged FFI-s.

> Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly. I mean you could have written similar code in C++ using std::vector or std::dequeue and get the bounds checking too.

As a sibling comment said, its a b-tree not a binary tree. B-trees are - as far as I know - the fastest data structure on modern computers for the class of problems they solve.

And yes, I think if I ever go back to C/C++ I'll try this approach out. It might also work great in GC languages like JS/TS/C#/Go because there's fewer pointers to keep track of.

> Cargo is good for as long as there are few packages in there. Large projects already suffer from five versions of serde in one build and dependencies on FFI-connected libs that cargo itself cannot build. I mean look at the NPM nightmare — and they've mostly dodged FFI-s.

I haven't run into the "five versions of serde" problem, but I can easily imagine it. I've lived NPM nightmares more times than I can count. But I'd still prefer that to all the problems you get from CMake, autotools and Makefiles. At this rate we're going to get self driving cars before we have a single sane build system for C.

> Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly

BTree is not Binary Tree. It's B-Tree and is cache-friendly

> C++20 with concepts mostly reproduce the traits.

C++20 concepts are not the same as traits. Concepts are structural and awkward to use compared to Traits which are nominal. There are other important differences, too.