alt Hacker NewsHigh-performance header-only container library for C++23 on x86-64
From the readme:
The B+tree implementation provides significant performance improvements over industry standards for large trees. For some workloads with large trees, we've observed:
- vs Abseil B+tree: 2-5× faster across insert/find/erase operations - vs std::map: 2-5× faster across insert/find/erase operations
Comments
There is also new Adaptive Radix Tree implementation - https://www.db.in.tum.de/~leis/papers/ART.pdf which is supposed to be faster than B-Tree
Also want to share B- tree implementation from the Algorithmica HPC book: https://en.algorithmica.org/hpc/data-structures/b-tree/
> History/Motivations This project started as an exploration of using AI agents for software development. Based on experience tuning systems using Abseil's B+tree, I was curious if performance could be improved through SIMD instructions, a customized allocator, and tunable node sizes. Claude proved surprisingly adept at helping implement this quickly, and the resulting B+tree showed compelling performance improvements, so I'm making it available here.
It seems the code was written with AI, I hope the author knows what he is doing. Last time I tried to use AI to optimize CPU-heavy C++ code (StackBlur) with SIMD, this failed :/
Ok, maybe someone here can clear this up for me. My understanding of B+tree's is that they are good for implementing indexes on disk because the fanout reduces disk seeks... what I don't understand is in memory b+trees... which most of the implementations I find are. What are the advantages of an in memory b+tree?
[dead]
2-5x faster than both abseil's b+tree and std::map means that abseil's b+tree had to be the same performance as std::map for the tested workload. This is... very unusual. I have only ever seen it be much faster or moderately slower.