absl::btree_map — sorted·cache-friendly B-tree

#한 줄 요약

absl::btree_map은 sorted associative container를 B-tree로 구현한다. std::map의 red-black tree가 노드당 1 key + 좌우 child pointer를 강제하는 반면, B-tree 노드는 여러 key를 packed하게 들고 있어 cache line 활용도가 높다. 같은 key 수에서 lookup/insert가 빠르고 메모리도 절약된다.

#동기

std::map의 표준 구현은 거의 항상 red-black tree다. 노드마다 1 key + 2 child pointer + parent pointer + color bit. 메모리 overhead가 크고, traversal마다 노드 jump → cache miss.

1
RB-tree 노드 (대략 64-bit):
2
[key, value, left*, right*, parent*, color, padding]
3
overhead ≥ 32 bytes per key

B-tree는 다르다. 한 노드가 수십 개 key를 담는다. cache line(64B)에 여러 key가 들어간다.

1
B-tree 노드 (256 bytes 기준):
2
[key, key, ..., key, child*, child*, ..., child*]
3
overhead per key: 노드 헤더 / N

Abseil의 btree_map은 노드 크기를 cache line의 배수에 맞춰 설계해 modern CPU에서 std::map보다 2~4배 빠른 lookup을 보인다.

두 자료구조의 차이를 그림으로 비교하면 다음과 같다.

#API와 사용법

1
#include "absl/container/btree_map.h"
2

3
absl::btree_map<int, std::string> m;
4
m[1] = "one";
5
m[2] = "two";
6
m[3] = "three";
7

8
// 정렬된 순회
9
for (const auto& [k, v] : m) {
10
  // k는 오름차순
11
}
12

13
// 범위 쿼리
14
auto lo = m.lower_bound(2);
15
auto hi = m.upper_bound(10);
16
for (auto it = lo; it != hi; ++it) { /*...*/ }

std::map과 동일 인터페이스. lower_bound/upper_bound/equal_range, reverse iteration 모두 지원.

#std::map 대비 차이

가장 큰 트레이드오프는 iterator/pointer 안정성이다. std::map은 노드 단위 인디렉션이 강해서 안정적이고, btree_map은 노드 분할/병합으로 무효화될 수 있다.

#내부 구현

btree_map의 노드 헤더는 다음과 비슷하다.

1
// absl/container/internal/btree.h (요약)
2
template <typename Params>
3
class btree_node {
4
  using slot_type = typename Params::slot_type;
5

6
  btree_node* parent_;
7
  field_type position_;   // 부모에서의 위치
8
  field_type count_;      // 현재 key 개수
9
  field_type max_count_;  // 노드 최대 key 개수
10
  slot_type slots_[kMaxSlots];
11
  // leaf가 아니면 child pointer 배열도
12
};

노드 크기는 target_node_size 매개변수(기본 256B)에 맞춰 컴파일 타임에 결정된다. 작은 key type이면 한 노드에 수십 개 key가 들어간다.

lookup은 노드 안에서 binary search(또는 linear search — small N에서 더 빠름)로 위치를 찾고, 필요하면 child 노드로 내려간다. 트리 높이는 log_N이지만 N이 크므로 실제 깊이는 매우 얕다.

10M 원소:

• std::map: ~23 level (log_2)
• btree_map: ~4 level (log_64)

#코드 리뷰 포인트

1. std::map → btree_map

대부분의 sorted map은 btree_map이 더 빠르다. 단, pointer 안정성을 가정하는 코드를 검수.

1
// std::map의 관용구 — btree에서는 위험
2
auto* p = &m[key];
3
m.emplace(other_key, ...);  // 노드 분할 가능 → p dangling
4
*p = ...;

값을 직접 보관하지 말고 매번 find 또는 unique_ptr 보관.

2. std::set → absl::btree_set

absl::btree_set도 같은 트레이드오프로 제공된다. 정렬된 unique 집합이 필요하면 btree_set.

3. multimap / multiset 대응

absl::btree_multimap, absl::btree_multiset도 제공된다. std::multimap보다 빠르고 메모리 효율도 높다.

4. iteration이 hot path

range-for iteration 또한 cache-friendly하다. 노드 내부 순회는 인접 메모리, 노드 간 점프만 cache miss.

1
// 정렬된 순회 자주 — btree_map이 적합
2
for (const auto& [k, v] : sorted_index) Process(k, v);

#안티패턴

hash로 충분한 곳에 btree

정렬·범위 쿼리·lower_bound가 필요하지 않으면 hash map이 압도적으로 빠르다.

pointer 보관

1
// 회피
2
auto* p = &m[k];
3
m.emplace(...);
4
use(p);   // UB 가능
5

6
// Good
7
m[k] = ...;  // operator[] 마지막에

또는 value를 unique_ptr로.

iterator 캐시

1
auto it = m.find(k);
2
m.emplace(...);   // 노드 분할 → it 무효화 가능
3
use(it);

iterator도 보관 금지.

#node_handle (C++17 호환)

1
auto node = m.extract(key);
2
node.key() = new_key;  // key 수정 후
3
m.insert(std::move(node));

absl::btree_map은 C++17의 node_handle API를 지원해 key를 수정할 수 있다. 일반 m[k]로는 불가능한 동작.

#정리

• btree_map은 B-tree 기반 sorted map. cache 친화, 메모리 효율.
• std::map 대비 2~4배 빠른 lookup, 노드 fan-out 수십.
• iterator/pointer가 노드 분할/병합으로 무효화될 수 있다.
• 정렬·범위 쿼리가 필요 없으면 flat_hash_map이 더 빠르다.
• multi 변형(btree_multimap, btree_multiset)도 제공.

#다음 편

Part 5-05 — FixedArray에서 동적 크기지만 stack 할당을 노리는 배열을 본다.

#관련 항목

• Part 5-01 — flat_hash_map
• Part 5-05 — FixedArray
• Part 5-06 — InlinedVector
• Abseil — B-tree containers