Benchmarking C++ Trees and Hash Tables at Scale: What Actually Happens at 60 Million Ops

I pushed RBTree, AVLTree, BST, std::set, std::map, and unordered_set through 60 million operations. Sorted inserts. Sorted searches. Sorted deletes. This is what these structures really do under load — not in theory, but in code.

TL;DR

• RBTree → Best all-around. Stable. Predictable.
• AVLTree → Fastest lookups. Pays for it during inserts.
• unordered_set → For numbers, nothing touches it.
• std::set / std::map → Correct, but slow. Node-based overhead everywhere.
• BST → Dies instantly with sorted input.
• Strings → Hashing + comparison + allocation = pain.
• Sorted input → Harmless for hashing, worst case for unbalanced trees.

If you handle millions of operations, these differences matter. A lot.

Why This Benchmark Exists

In real systems — trading engines, telemetry, game loops, pipelines — you don’t do 1,000 inserts. You do millions.

Small benchmarks lie. They hide allocator cost, pointer chasing, cache misses, and the collapse of unbalanced trees.

So I ran the workload at a scale where data structures stop pretending.

Benchmark Setup

Everything is single-threaded. Pure compute. No magic tricks.

Data Structures Tested

• RBTree (custom)
• AVLTree (custom)
• BST (unbalanced)
• std::set
• std::map
• unordered_set

And four key types:

• int
• long
• float
• string

The Pipeline

1. Load 100k random values

Simulates “normal” real-world initial state.

2. Insert 10M sorted values

Worst case for BST. Normal for balanced trees. Irrelevant for hashing.

3. Search 10M sorted values

Pure lookup cost at scale.

4. Delete 10M sorted values

Deletion is where some trees fall apart.

All Benchmarks in One Image

This image shows:

• Load (100k)

• Insert (10M)

• Search (10M)

• Remove (10M)

  For every data structure and every data type.

No surprises. Just raw behavior.

Key Results (int type)

What’s Actually Happening

1. BST collapses — instantly

Sorted input turns it into a linked list.

root
  └── right
        └── right
              └── ...

Tree height becomes n, not log(n).

10 million operations → 10 million steps per lookup in the worst case.

If sorted input exists anywhere in your workload, BST is a bug.

2. Why RBTree beats std::set and std::map

std::set/std::map are real RB-trees, but they are node-based:

• every insert = allocation
• pointers everywhere
• cache misses everywhere
• terrible locality

Your RBTree is likely:

• more contiguous
• fewer allocations
• fewer indirections

Result: faster in every phase.

Yes, you can beat the STL if your workload is specialized.

3. AVL search is faster because the tree is tighter

Height guarantees:

• AVL:

  textCopy

  h ≤ 1.44 log2(n)
  
  

• RBTree:

  textCopy

  h ≤ 2 log2(n)
  
  

AVL is shallower → fewer comparisons → better searches.

But rotations make inserts/removes more expensive.

Classic trade-off. Your numbers reflect it perfectly.

4. unordered_set dominates numeric workloads

Hashing integers/floats is basically:

return value;

Load factor is doing the real work.

As long as rehashing isn’t happening constantly, you get near-constant time everything.

Nothing beats it for numeric pipelines.

5. Strings slow everything down

Strings pay three taxes:

1. allocation
2. hashing
3. comparison

The result is obvious in the graph: the string bars explode.

If your hot path uses strings, you’re already losing.

Use IDs, handles, or interned strings.

What Happens at 100M Ops?

If you scale this to 100M:

• unordered_set → expect rehash storms
• std::set/map → pointer-chasing bottleneck dominates everything
• RBTree/AVLTree → branch mispredicts add up fast
• strings → memory bandwidth becomes the real limit
• allocators → fragmentation finally bites

Everything gets worse, not linearly — worse than linear.

Limitations (To Stay Honest)

• Single-threaded
• No memory usage measurements
• No custom allocators (tcmalloc / jemalloc / pool allocators)
• No microarchitectural profiling (cache misses, branch misses)
• No NUMA-aware runs

This is the next iteration.

Practical Takeaways (Use This in Real Systems)

RBTree

Use when you want ordering + stable performance. Great default choice.

AVLTree

Use when reads dominate and updates are rare. Lowest lookup latency.

unordered_set

Use when you don’t need order and your keys are numeric. Fastest thing here.

std::set / std::map

Use only when you need STL guarantees or interoperability. Slow under heavy churn.

BST

Use only in classrooms. Never in production. Sorted input kills it instantly.

Conclusion

At 10M operations, theory stops being theory:

• Balanced trees hold up
• Hash tables dominate for numbers
• Node-based containers pay the indirection tax
• Strings are universally expensive
• BST collapses on contact with sorted data

If you’re building performance-sensitive C++ systems, these results are not optional — they’re reality.

github repo