Comment by writebetterc

>Benchmarks show its about 25% faster than the raw pointer version. (I don't know why - but I suspect the reason is due to better cache locality.)

Cache locality matters, but so does having less allocator pressure. Use 32-bit unsigned ints as indices, and you get improvements on that as well.

>The original version of my b-tree works just like how you'd implement it in C. Each internal node / leaf is a raw allocations on the heap.

I'd always try to avoid that type of allocation pattern in C++, FWIW :-).