Rust bbtree vs BTreeMap: 범위 조회·동시 접근·성능 차이

세 줄 요약

bbtree는 키를 정렬해 보관하며 순서대로 순회하거나 특정 구간의 값을 읽을 수 있는 Rust 맵이다.
unsync는 BTreeMap처럼 참조를 빌려 읽고, 공유 맵은 값 복사나 콜백으로 여러 스레드의 접근을 처리한다.
제작자는 단일 스레드에서 BTreeMap 대비 5배, 96개 스레드에서 crossbeam-skiplist 대비 12배 빠르다고 발표했다.

키 하나를 찾는 HashMap, 구간을 읽는 정렬 맵

HashMap은 사용자 ID 하나로 값을 찾는 작업에 적합하다. 반면 번호 100번부터 200번까지를 순서대로 읽으려면 키가 정렬된 맵이 편하다. Rust 컬렉션 안내도 키 정렬·범위 조회·최솟값과 최댓값이 필요한 작업에 BTreeMap을 제시한다.

bbtree는 BTreeMap처럼 키 순서와 범위 조회를 지원하면서 단일 스레드용 맵과 동시 접근용 맵을 제공한다. 정렬 순서는 키의 Ord를 따른다. 예를 들어 시간을 키로 저장하면 시간 구간을 조회할 수 있고, 사용자 ID를 키로 저장하면 ID 순서로 순회한다. 이는 표준 BTreeMap과 같은 방식이다.

unsync는 BTreeMap처럼 참조를 빌려 읽는다

0.1.5의 bbtree::unsync::BBTreeMap은 표준 BTreeMap을 대체하는 API다. 값을 바꿀 때는 가변 참조를 쓰고, get은 저장된 값의 참조를 돌려준다. range로 지정한 구간을 순서대로 읽는 코드도 이 타입에서 옮길 수 있다.

range(100..200)은 100 이상, 200 미만의 키를 읽는다. 200까지 포함하려면 range(100..=200)으로 쓴다.

하려는 작업	먼저 비교할 대상
키 하나로 값을 찾고 순서는 필요 없다	기존 HashMap 유지 여부
BTreeMap식 단일 소유 코드의 성능을 비교한다	bbtree::unsync::BBTreeMap
여러 스레드가 같은 맵을 읽고 바꾼다	bbtree::BBTreeMap의 공유 API

공유 맵은 값 복사와 콜백으로 읽는다

여러 스레드가 접근하는 bbtree::BBTreeMap은 get_copied로 값을 복사해 돌려준다. 복사하지 않고 값을 읽으려면 read의 콜백 안에서 처리한다. 콜백 실행 중 같은 맵을 다시 호출하면 교착이 생길 수 있다.

여러 항목을 읽는 scan은 전체 맵의 한 시점을 고정하지 않는다. 다른 스레드가 스캔 도중 항목을 넣거나 지우면 그 항목이 결과에 포함될 수도, 빠질 수도 있다. 동시 수정 중에도 특정 시점의 전체 목록이 필요한 작업에는 이 동작이 맞지 않는다.

공유 맵의 키에는 순서를 보존해 키를 인코딩하는 InlineKey 지원이 필요하다. 기본 전략이 지원하지 않는 사용자 정의 키는 별도 구현과 전략을 지정한다. unsync의 참조 반환 코드를 공유 맵으로 옮길 때 바뀌는 부분은 이러한 키 처리와 읽기 API다.

BTreeMap 대비 5배, crossbeam-skiplist 대비 12배

제작자가 README에 제시한 속도 향상은 단일 스레드에서 표준 BTreeMap 대비 5배, 96개 스레드에서 crossbeam-skiplist 대비 12배다. 전자는 표준 라이브러리의 정렬 맵과, 후자는 동시 접근을 지원하는 다른 자료구조와 비교한 수치다.

기존 BTreeMap 코드와 같은 API로 시험할 수 있는 타입은 unsync다. 여러 스레드가 같은 맵을 읽고 쓰는 코드는 공유 BBTreeMap을 사용한다. 공유 맵에서 값을 복사하거나 구간을 끝까지 순회하면 그 비용도 전체 처리 시간에 들어간다.