트라이 자료구조로 접두사 검색 인덱스 설계하기

접두사가 곧 탐색 경로가 되는 인덱스

트라이(Trie, Prefix Tree)는 문자열을 문자 단위로 나누고, 공통 접두사는 같은 경로에 모으는 트리 기반 인덱스다. 루트에서 특정 노드까지 이어지는 경로가 하나의 키가 되며, 단어의 끝에는 종료 플래그와 필요한 메타데이터를 둔다.

검색, 삽입, 접두사 탐색의 시간 복잡도는 모두 O(m)이다. 여기서 m은 질의 문자열의 길이다. 데이터 크기 n에 영향을 덜 받는 이 특성은 긴 꼬리 지연시간을 줄이는 데 유리하다. 대규모 사전 검색, 자동완성, 접두사 필터링, URL 또는 명령 프롬프트 제안, 형태소 분석에 쓰인다.

노드는 children, terminal flag, payload를 가질 수 있다. 간선은 문자 또는 문자열 레이블이며, 연속된 경로를 압축한 구조는 라딕스 트리나 패트리샤 트리로 이어진다. 사전을 더 줄여 표현하는 방식으로는 DAWG가 있다.

노드 표현과 페이로드를 정하는 기준

자식 노드는 해시맵(children: dict)으로 관리하거나 고정 크기 배열로 둘 수 있다. 해시맵은 문자셋 변화에 유연하고, 배열은 캐시 친화성을 기대할 수 있다. 어느 쪽을 택할지는 알파벳 크기와 문자셋에 따라 결정된다.

노드의 payload에는 단어 종료 여부 외에도 빈도수나 점수, 문서 ID 목록, 마지막 갱신 시각처럼 랭킹과 필터링에 필요한 정보를 저장할 수 있다. 단일 자식으로 이어지는 경로는 엣지 레이블로 합쳐 라딕스 트리를 만들면 메모리 사용량과 트리 깊이를 낮출 수 있다. 이때 유니코드 정규화는 NFC/NFKC 중 하나로 일관되게 유지해야 한다.

삽입부터 후보 수집까지의 흐름

삽입은 입력 문자열을 정규화한 뒤 문자를 순회하면서 자식 노드를 생성하거나 기존 노드로 이동하는 방식이다. 마지막 노드에서 종료 플래그와 빈도를 갱신하고, 필요하다면 경로를 압축한 뒤 커밋한다.

자동완성은 먼저 접두사 경로를 찾는다. 해당 노드가 없으면 공집합을 반환한다. 경로가 있다면 그 서브트리에서 BFS 또는 DFS로 Top-K 후보를 모으고, 빈도·사전순·신선도 가중치를 적용해 순위를 정한다. 삭제는 종료 플래그만 먼저 해제하는 지연 삭제를 우선할 수 있으며, 참조 카운트가 0인 노드를 정리하고 배치 컴팩션으로 파편화를 줄인다.

⤢✕

메모리와 갱신 비용을 다루는 방법

문자셋을 소문자·숫자로 제한하고 공백이나 특수문자를 토큰화하면 알파벳 크기를 줄일 수 있다. 배열 인덱싱을 사용하면 분기 비용과 캐시 적중률 측면에서 이점이 있다.

공유 경로와 접미사 중복은 라딕스 트리와 DAWG로 줄일 수 있다. LOUDS나 순차화 방식은 디스크·메모리상 직렬화와 메모리 매핑을 위한 선택지다. 포스팅 리스트처럼 큰 payload는 별도 스토리지에 보관하고 노드에는 식별자만 남기는 편이 적합하다.

읽기가 많은 워크로드에서는 Copy-on-Write 스냅샷이나 RCU, 읽기-쓰기 락을 적용할 수 있다. 읽기 락 프리 경로를 보장하면 높은 QPS를 확보할 수 있다. 전체 인덱스를 오프라인에서 빌드한 다음 버전을 스왑하면 일관성을 유지할 수 있고, 인덱스 파일은 메모리 매핑으로 즉시 가용하게 만들 수 있다. 입력 정규화 실패나 불법 문자에는 폴백 규칙을 두며, 부분 삽입에는 롤백 또는 재시도 정책이 필요하다.

검색·언어 처리·라우팅에서의 적용

검색 자동완성과 추천 시스템에서는 키 입력마다 O(m) 접두사 탐색을 수행하고, 클릭률(CTR)과 최근성 신호를 랭킹에 결합할 수 있다. 사전과 형태소 분석에서는 어근·접사 탐색, 금칙어 필터링에 맞는다. 한국어 복합명사를 다룰 때는 공백 또는 자모 단위 토크나이징을 적용한다.

네트워크와 시스템 영역에서는 접두사 기반 경로 선택(LPM)에 응용할 수 있다. 바이너리 트라이와 패트리샤 트리는 고정 길이 키에 적합하다. 보안 패턴 매칭에서는 악성 URL이나 서명의 접두사를 차단하고, 정규표현식 전처리와 결합해 초기 후보를 줄일 수 있다.

구조 선택에서 확인할 성능과 운영 특성

해시+필터와 비교하면 접두사 질의 평균 지연시간은 3070% 감소할 수 있다. 100만 단어/평균 길이 8 환경에서는 메모리 상주, Top-10 조건으로 95퍼센타일 < 5ms 달성이 가능하다. 라딕스 트리나 DAWG를 적용하면 메모리를 3060% 절감할 수 있으며, LOUDS 기반 직렬화는 10M+ 키를 단일 노드 메모리 매핑으로 운용할 수 있다.

키 길이에 비례하는 시간 복잡도는 롱테일을 완화한다. 스냅샷 스왑은 무중단 갱신에, 부분 실패 시 롤백은 안정성 확보에 활용된다.

구조	성능(접두사)	확장성	일관성	안정성	운영 편의
Trie(기본)	O(m), 안정 지연	메모리↑, 샤딩 용이	높음	높음	구현 용이
Radix Trie	O(m), 깊이↓	메모리 절약	높음	높음	약간 복잡
Ternary Search Tree	O(m log Σ)	메모리 중간	중간	높음	포인터 관리 필요
HashMap+스캔	키 검색 우수, 접두사 비효율	데이터↑ 시 비용↑	낮음	중간	단순
DAWG	O(m), 최소화	매우 높음	높음	빌드 복잡	빌드 파이프라인 필요

트라이는 텍스트와 바이너리 키의 접두사 질의에 일관된 성능을 제공한다. 메모리와 지연시간의 균형은 라딕스 트리·DAWG·LOUDS의 조합으로 맞추고, 운영 환경에서는 읽기 우선 동시성과 스냅샷 스왑 전략을 함께 설계할 수 있다.