ART 접두사 트리: 메모리 및 캐시 최적화

자동완성 최적화: 접두사 트리 메모리 825MB에서 18MB로 줄이기

5만 개의 명령어를 검색하는 트라이는 메모리 825MB를 사용했고, 해시 테이블보다 8배 느렸습니다 (480만 사이클 대비 60만 사이클). 각 노드는 2,064바이트로, 256개 포인터 배열을 포함해 탐색 시 자주 캐시 미스가 발생했습니다.

perf stat 벤치마크 결과, 트라이의 캐시 미스는 12.5만 건이었지만 해시 테이블은 단 1.8만 건에 그쳤습니다. 5글자 문자열 검색 시, 각 노드가 한 캐시 라인에 들어가지 않아 총 5번의 캐시 미스가 발생했습니다.

노드 구조와 메모리 사용량

표준 노드 구현:

typedef struct trie_node {
    struct trie_node *children[256];  // 2048 바이트
    void *value;                      // 8 바이트
    bool is_end;                      // 1 바이트
    // 합계: 2064 바이트
} trie_node_t;

5만 개의 명령어(평균 길이 8자) 데이터셋에 대해 약 40만 개의 노드가 필요했는데, 이는 해시 테이블의 1.2MB 대비 825MB로, 687배 이상의 차이입니다.

컴팩트 트라이: 체인 압축

해결책: 컴팩트 트라이(패트리샤 트라이), 단일 자식 노드로 이루어진 체인을 접두사로 압축합니다. 노드는 개별 문자 대신 접두사 문자열을 저장합니다.

typedef struct radix_node {
    char *prefix;
    int prefix_len;
    struct radix_node *children[256];
    void *value;
} radix_node_t;

탐색 알고리즘:

void* radix_search(radix_node_t *node, const char *key) {
    while (node) {
        int i = 0;
        while (i < node->prefix_len && key[i] == node->prefix[i]) {
            i++;
        }
        if (i < node->prefix_len) return NULL;
        if (key[i] == '\0') return node->value;
        node = node->children[(unsigned char)key[i]];
        key += i + 1;
    }
    return NULL;
}

결과: 메모리가 330MB로 감소하고, 사이클 수는 240만으로 줄어들며 캐시 미스는 6.8만 건으로, 2배 성능 향상이 이루어졌습니다.

적응형 래딕스 트리(ART)

문제점: 256개 포인터 배열 중 98%가 비어 있었습니다. 해결책: 자식 수에 따라 동적으로 노드 유형을 선택하는 적응형 노드 설계입니다.

• Node4 (1~4 자식): 40바이트
• Node16 (5~16 자식): 152바이트
• Node48 (17~48 자식): 640바이트
• Node256 (49+ 자식): 2048바이트

성장 전략: 제한을 초과하면 Node4 → Node16 → Node48 → Node256 순으로 확장됩니다.

평균 노드 크기: 40~152바이트 대비 2048바이트 — 메모리 절약률 10~50배입니다.

벤치마크 결과

5만 개 명령어에 대한 100만 번의 검색 비교:

| 구조 | 메모리 | 사이클 | 캐시 미스 | 성능 향상 |

|-----------|--------|--------|--------------|---------|

| 트라이 | 825 MB | 4,800 | 12.5 | 1× |

| 래딕스 | 330 MB | 2,400 | 6.8 | 2× |

| ART | 18 MB | 1,200 | 3.2 | 4× |

| 해시 | 1.2 MB | 600 | 1.8 | 8× |

ART는 표준 트라이 대비 45배 더 작으며, Node4/Node16 노드는 1~2개의 캐시 라인에 완전히 들어옵니다.

접두사 트리의 활용 사례

접두사 연산이 필요한 경우 ART를 사용하세요:

• 자동완성: O(k + m) 시간 복잡도로 하위 트리 탐색 가능 (m은 매칭 수). 해시 테이블은 전체 스캔이 필요합니다.
• IP 라우팅: 주소 비트 기반 최장 접두사 매칭.
• 맞춤법 검사: 편집 거리 기반 접두사 탐색.
• 희소 배열: 리눅스 커널에서 페이지 캐시, IDR, XArray 등에 활용됩니다.

정확한 조회, 소규모 데이터셋(<1,000개 항목), 공통 접두사 없는 문자열에는 피하세요.

리눅스 커널에서의 컴팩트 트라이 사용

커널은 radix_tree_node를 사용하며, 64개 슬롯(각 레벨당 6비트)을 갖습니다. 32비트 인덱스 기준 6단계 — 이는 이진 탐색 트리(BST)의 약 32회 캐시 미스 대비 ~6회로 훨씬 효율적입니다.

장점:

• 범위 연산 지원
• 예측 가능한 O(log₆₄ n) 복잡도
• 희소 데이터에 매우 효율적

핵심 요약

• 표준 트라이는 256포인터 배열로 메모리 사용량이 687배 증가
• ART는 적응형 노드로 메모리 18MB, 캐시 미스 3.2로 줄여 4배 성능 향상
• 정확한 조회에는 해시 테이블이 우수함
• 컴팩트 트리는 체인 압축으로 2배 속도 향상
• 리눅스 커널은 희소 배열 및 ID 할당에 이를 활용

— Editorial Team