[masklinn]

> maybe could be a b-tree?

IIRC the complexity requirements of std::map preclude a b-tree (or require a binary tree). Though I don't remember the exact reasoning.

abseil's website makes the same claim, though also without justification:

> B-trees have a different implementation from STL std::map containers, which require binary trees commonly implemented as red-black trees.