정적 검색 트리: 이진 탐색보다 40배 빠른 비밀

Static search trees: 40x faster than binary search (2024)

이 글은 정렬된 데이터를 고속으로 검색하기 위한 정적 S+ 트리 구현을 소개합니다. Rust로 작성된 이 구현은 이진 탐색과 Eytzinger 레이아웃을 능가하여, 1GB 입력에서 쿼리당 1150ns였던 이진 탐색을 40배 이상 개선한 28ns까지 단축합니다. 저자는 Algorithmica의 S-tree를 기반으로 SIMD, prefetching, batching 등 고급 최적화 기법을 적용하고, 어셈블리 수준에서 코드를 분석하며 성능을 극한으로 끌어올립니다. 또한 메모리 레이아웃과 캐시 동작을 세심하게 다루며, DNA 서열 인덱싱과 같은 생물정보학 응용을 위한 첫걸음으로서의 동기를 설명합니다.