선택트리로 k-way 병합 성능을 설계하는 법

여러 정렬 스트림의 다음 값을 고르는 트리

선택트리(Selection Tree)는 여러 후보를 이진 토너먼트처럼 비교해 전체 승자를 루트에 유지하는 자료구조다. 대용량 데이터를 다룰 때 최솟값이나 최댓값을 반복해서 꺼내고, 다수의 정렬 스트림을 병합하는 용도로 쓰인다.

승자트리(Winner Tree)는 내부 노드에 각 대결의 승자를 저장하므로 루트가 전역 승자가 된다. 패자트리(Loser Tree)는 내부 노드에 패자를 두고 루트에 승자 인덱스를 보관한다. 패자트리는 갱신 과정의 비교 횟수를 줄일 수 있고, 승자트리는 구조를 이해하고 구현하기가 상대적으로 단순하다.

단말에서 시작한 비교 결과는 부모 방향으로 올라간다. 루트의 값을 꺼낸 뒤에는 그 값이 있었던 단말만 새 후보로 바꾸고, 루트까지의 경로만 다시 계산한다. 이 방식으로 다음 승자를 O(log k)에 결정한다.

배열로 관리하는 토너먼트 구조

후보가 k개인 완전 이진 선택트리는 노드 수가 약 2k이며, 힙처럼 배열 인덱스로 표현할 수 있다. 내부 노드는 승자트리라면 승자 값 또는 인덱스를, 패자트리라면 패자 인덱스를 저장한다.

같은 키가 여러 스트림에 나타날 수 있다면 (키, 소스 인덱스)를 함께 비교한다. 이 타이브레이커는 입력 순서를 보존하는 안정 병합에 필요하다.

초기 트리 구성은 O(k)~O(k log k)로 구현할 수 있다. 실무에서는 O(k) 초기화 알고리즘이나 완전 이진트리 빌드를 사용한다. 루트 조회는 O(1)이고, 추출 뒤의 경로 갱신은 O(log k)이다. 패자트리는 재경기에서 불필요한 비교를 줄이는 특성이 있다.

입력 소스가 소진되면 센티넬인 +∞를 넣어 병합을 자연스럽게 끝낼 수 있다. 처음부터 비어 있는 스트림에도 같은 방식을 적용한다. 스트림 길이가 크게 달라도 트리 높이는 최대 log k로 유지된다.

외부 정렬과 병합 엔진에서의 활용

디스크에 흩어진 정렬 런(run) k개를 합칠 때 선택트리는 다음 레코드의 선택 비용을 O(log k)로 유지한다. 대규모 로그나 트랜잭션 파일의 정렬, 데이터 웨어하우스 적재가 대표적인 적용 대상이다.

DB/MS 엔진에서는 정렬된 포스트 리스트 병합, 인덱스 머지 스캔, 스트림 기반 조인에서 안정적인 최소값 선택에 사용할 수 있다. 여러 파티션에서 정렬된 이벤트가 들어오는 실시간 집계에서도 같은 구조로 타임라인을 병합하며 지연을 낮추고 일정한 처리 시간을 확보한다.

Replacement Selection에서는 분포를 가정할 때 힙보다 평균 2배 길이의 런을 만들 수 있어 디스크 I/O 단계 수를 줄일 수 있다.

선택과 갱신은 각각 O(log k)이며, n개 레코드의 전체 병합 복잡도는 O(n log k)다. k ≪ n인 외부 병합에서는 총 비용을 크게 줄일 수 있다. k가 증가해도 성능 열화는 로그 수준이고 메모리 사용량은 O(k)다. 배열 기반 구현은 캐시 친화적이며, 예측 가능한 지연 시간을 확보하는 데도 유리하다.

병합 루프에서 단말을 갱신하는 방식

⤢✕

승자트리·패자트리·이진 힙의 선택 기준

지표	승자트리 (Winner)	패자트리 (Loser)	이진 힙 (Heap)
성능(선택/갱신)	O(1)/O(log k), 비교 횟수 보통	O(1)/O(log k), 비교 횟수 최소화	pop/push 각각 O(log k)
확장성(k 증가)	로그 증가	로그 증가(상수 계수 우수)	로그 증가
일관성(안정 병합)	소스 인덱스 tie-breaker로 용이	소스 인덱스 tie-breaker로 용이	튜플 키로 용이
안정성(에러/소진)	센티넬 처리로 안전	센티넬 처리로 안전	센티넬 또는 빈 힙 처리
운영 편의(구현)	중간	다소 복잡	가장 단순

k-way 병합에서 비교 횟수를 줄이고 싶다면 패자트리를 검토할 수 있다. 구현 단순성과 동적 워크로드에서의 재사용·확장 편의가 더 중요하다면 이진 힙이 적합하다. k가 자주 바뀌지 않고 반복 병합이 핵심인 경우에는 선택트리의 경로 기반 갱신이 강점이 된다.

Python으로 구현한 완전 이진 선택트리

환경은 Python 3.10+이며 표준 라이브러리만 사용한다. 각 입력 스트림은 오름차순 정렬되어 있다고 가정하고, 안정 병합을 위해 (키, 소스 인덱스)를 비교한다.

from math import inf, ceil, log2
from typing import Iterable, Iterator, List, Tuple, Any

class SelectionTreeMerge:
    def __init__(self, streams: List[Iterable[Any]]):
        self.k = len(streams)
        self.iters: List[Iterator[Any]] = [iter(s) for s in streams]
        # 트리 크기: 단말 시작 인덱스 m (2의 거듭제곱)
        self.m = 1 << ceil(log2(max(1, self.k)))
        self.N = 2 * self.m  # 1-based 사용, [1..2*m-1]
        # 각 단말에 (key, source) 저장. 비어있는 단말은 +∞
        self.tree: List[Tuple[float, int]] = [(inf, -1)] * self.N
        # 소스 인덱스 -> 단말 인덱스 매핑
        self.leaf_idx = [self.m + i for i in range(self.k)]
        # 초기 로드
        for i in range(self.k):
            key = next(self.iters[i], None)
            if key is None:
                self.tree[self.leaf_idx[i]] = (inf, i)
            else:
                # 안정 병합을 위해 (key, source) 튜플
                self.tree[self.leaf_idx[i]] = (key, i)
        # 남는 단말은 센티넬
        for i in range(self.k, self.m):
            self.tree[self.m + i] = (inf, -1)
        # 상향식 빌드
        for idx in range(self.m - 1, 0, -1):
            self.tree[idx] = min(self.tree[2 * idx], self.tree[2 * idx + 1])

    def _update_leaf(self, src: int):
        """src 소스의 단말 값을 갱신하고 경로 재계산"""
        leaf = self.leaf_idx[src]
        key = next(self.iters[src], None)
        self.tree[leaf] = ((key, src) if key is not None else (inf, src))
        idx = leaf // 2
        while idx >= 1:
            self.tree[idx] = min(self.tree[2 * idx], self.tree[2 * idx + 1])
            idx //= 2

    def merge(self) -> List[Any]:
        result: List[Any] = []
        while True:
            key, src = self.tree[1]
            if key is inf:
                break
            result.append(key)
            self._update_leaf(src)
        return result

if __name__ == "__main__":
    # 예시: 3개의 정렬 스트림 병합
    s1 = [1, 4, 9]
    s2 = [2, 2, 6, 10]
    s3 = [3, 7, 8]
    merger = SelectionTreeMerge([s1, s2, s3])
    out = merger.merge()
    print(out)  # [1, 2, 2, 3, 4, 6, 7, 8, 9, 10]

이 구현은 완전 이진 구조의 단말부터 부모까지 값을 갱신한다. 루트에서 최솟값을 배출한 뒤 해당 소스의 단말만 바꾸므로, 다음 값 선택에 O(log k)가 든다. 동등한 키는 소스 인덱스를 함께 비교해 안정성을 유지한다.

운영 시 지켜야 할 경계 조건

안정 병합이 필요하면 모든 비교 지점에서 (키, 소스 인덱스) 규칙을 일관되게 적용한다. 소스 소진은 +∞ 센티넬로 처리하면 루프를 단순하게 유지할 수 있다.

디스크 기반 병합에서는 각 소스에 블록 I/O 버퍼를 따로 적용해 랜덤 접근을 줄인다. 다만 이진 힙보다 초기화가 복잡할 수 있으며, 패자트리의 처리량 이점은 비교 횟수 감소에서 나온다. k가 자주 달라지는 동적 워크로드에서는 힙이 재사용과 확장에 더 단순하다.

k를 2의 거듭제곱에 맞추기 위한 패딩이 필요할 수 있고, 이때 메모리 미세 오버헤드가 발생한다.