В C++ библиотеку Google Abseil https://github.com/abseil/abseil-cpp/tree/master/absl/container, о которой я уже писал (https://t.me/sea_plus_plus/69), добавили четыре новых STL-like Btree контейнера:
absl::btree_map, absl::btree_multimap, absl::btree_set и absl::btree_multiset. Данные хранятся в памяти, но под капотом алгоритм, который пришел из баз данных. Btree хранит несколько элементов в одном блоке памяти, что уменьшает количество аллокаций, а также за счет более эффективного использования кэша работает быстрее в большинстве случаев.Это практически drop-in замена
std::map и std::set. Однако при вставке и удалении происходит инвалидация итераторов. Поэтому надо быть осторожным.English version: https://telegra.ph/Google-Abseil-Btree-10-20