데이터 100만 건 탐색 시간을 50만 번에서 20번으로 단축하는 Halving 전략

Context

Linear Scan 방식의 탐색 구조는 데이터 규모 증가에 따라 연산량이 선형적으로 증가하는 O(n)의 한계를 가짐. 특히 대규모 데이터셋에서 탐색 횟수가 기하급수적으로 늘어남에 따라 성능 병목 현상이 발생함.

Technical Solution

• 데이터셋을 매 단계 절반으로 축소하는 Halving 메커니즘 기반의 Binary Search 적용
• 정렬된 상태의 데이터를 전제로 Mid-point 비교를 통한 불필요한 탐색 범위 제거
• Balanced Tree 구조 내에서 각 레벨마다 키 공간을 분할하여 탐색 경로를 log₂(n) 수준으로 유지
• B-Tree의 Branching Factor를 높여 단일 레벨에서 처리 가능한 데이터 양을 확장하고 Tree Depth를 최소화
• Divide and Conquer 전략을 통해 복잡한 문제를 하위 문제로 분할하여 전체 시간 복잡도를 O(n log n)으로 최적화

Impact

• 100만 개의 데이터 탐색 시 최대 비교 횟수를 500,000회에서 20회로 단축
• Linear Scan 대비 최악의 경우 약 25,000배의 연산 효율성 개선
• Branching Factor 256 기반 B-Tree 적용 시 1,000만 개의 키를 단 3단계의 레벨에서 인덱싱 가능

Key Takeaway

O(log n)의 본질은 단순한 속도 향상이 아닌 매 단계 문제 규모를 일정 비율로 축소하는 Halving 전략에 있음. Branching Factor의 조정은 상수 시간 복잡도 내에서 탐색 깊이를 제어하는 핵심 설계 변수로 작용함.