Bbtree: 가장 빠른 정렬 맵

bbtree는 Rust의 정렬 맵으로, 스킵리스트를 대체한 4개 LSM 트리의 자체 벤치마크에서 1.37~6.83배 성능 향상을 기록함 핵심은 캐시 미스 한 번으로 탐색 범위를 최대한 줄이는 것임. 고정 크기 인라인 키와 공통 접두사 건너뛰기로 여러 키를 비교하고, 비교 결과가 같을 때만 전체 키를 읽음 Turso의 인메모리 인덱스에서는 삽입이 2.22배, 인덱스를 사용하는 SELECT가 1.90배 빨라짐 배치 조회와 삽입에서는 Rust의 비동기 상태 머신으로 여러 탐색을 교차 실행해 캐시 미스 대기 시간을 숨김 안정 버전 Rust에서 일반적인 키 타입을 자동 최적화하며, 사용자 정의 타입은 InlineKey 로 최적화를 활용할 수 있음 적용 사례와 성능 B-tree의 성능 향상은 에이전트 메모리, LLM 학습, RAG, KV 저장소, 상태 캐싱, 벡터 검색 등 상위 시스템에도 도움이 됨 LSM 트리의 멤테이블은 최근 쓰기를 메모리에 보관하는 정렬 맵이며, Rust에서는 보통 crossbeam-skiplist 같은 스킵리스트를 사용함 스킵리스트는 탐색 중 방문하는 거의 모든 노드에서 캐시 미스를 겪지만, bbtree 조회는 소수의 캐시 라인에 접근함 crossbeam-skiplist와 인터페이스가 비슷하면서도 에포크(epoch)가 없어 고정(pin)하거나 재진입할 시점을 관리할 필요가 없음 4개 LSM 트리 통합 벤치마크는 Ryzen 9 9900X의 단일 스레드에서 각 시스템의 자체 벤치마크로 수행했으며, 정렬 맵만 교체함 fjall: 조회 2.47배, 삽입 1.61배, 배치 쓰기 3.00배 빨라짐 SlateDB: 조회 1.71배, 쓰기 1.65배, 10행 배치 쓰기 2.36배 빨라짐 Tonbo: 1,000만 행 쓰기 6.83배, 충돌 검사를 수행하는 트랜잭션 4.10배 빨라짐 Lance의 자체 스킵리스트 기반 MemWAL 인덱스: 단건 조회 2.19배, 배치 조회 3.94배, 배치 쓰기 4.21배 빨라짐 Turso 인메모리 데이터베이스 인덱스의 스킵리스트를 교체하면 삽입은 2.22배, 인덱스를 사용하는 SELECT는 1.90배 빨라짐 디스크의 bbtree를 메모리 매핑(mmap) 하면 재시작 후 트리를 재구축할 필요가 없으며, 표준 라이브러리의 BTreeMap보다 첫 응답을 160~2,500배 빨리 얻음 메모리 관리 사용자 정의 할당기를 처음부터 지원하며, 할당 실패를 정상적으로 처리할 수 있음 할당 크기는 ...