[Rust] B-Tree

#Rust

실제로 프로그램을 작성하다 보면 키-밸류 맵 구조를 사용할 일이 매우 많다.

그리고 맵에는 2가지 대분류가 있는데, 바로 ordered map과 unordered map이 그것이다.

ordered map은 실제로 데이터를 정렬된 형태로 저장하기 때문에 조회/추가/삭제 성능이 평범한 log N인 대신에 정렬된 형태로 데이터를 가져오기 좋다.

unordered map은 일반적으로 해시테이블을 기반으로 구현된다. 조회/추가/삭제 성능이 O(1)인 대신에 데이터를 정렬된 형태로 가져올 수 없다.

언어에 내장된 ordered map은 보통 tree로 구현되고, 그 중에서도 red black 트리로 구현되는게 국룰이었다. 대표적으로 C++의 이 그렇다.

근데 Rust의 내장 ordered map 구현체는 내장모듈로서는 드물게 B-Tree다. 실제로 코드를 보면 차수가 12로 고정되어있는 B-Tree더라.

표준 문서나 이슈들을 보면, 레드블랙은 메모리가 너무 분산되어서 캐시최적화가 구리기 때문에 비교적 메모리 파편화가 적은 B-Tree로 선택했다는 것 같다.
리밸런싱도 빈도가 덜하고.

BTree를 채택한 간략한 소개는 아래 문서 서두에 적혀있고
https://doc.rust-lang.org/beta/std/collections/struct.BTreeMap.html

이런저런 히스토리는 아래 이슈에 있다.
https://github.com/rust-lang/rust/issues/4992