역 인덱스의 기본 아키텍처
역 인덱스(Inverted Index)는 일반적인 전진 인덱스(Forward Index)와 반대의 구조를 가집니다. 전진 인덱스는 '문서 → 항' 매핑을 제공하는 반면, 역 인덱스는 '항 → 문서' 매핑을 제공합니다. 이러한 아키텍처의 전환으로 인해 텍스트 검색 성능이 획기적으로 향상됩니다. 역 인덱스는 두 개의 핵심 구성 요소로 이루어집니다: 사전(Dictionary)과 포스팅 리스트(Posting List)입니다.
사전과 포스팅 리스트
사전은 컬렉션에 나타나는 모든 고유 항의 정렬된 목록입니다. 각 항에 대해 포스팅 리스트가 연결되며, 이 포스팅 리스트는 해당 항이 나타나는 문서 ID들의 순서 있는 목록과 선택적으로 항의 빈도(Term Frequency)나 위치(Position) 정보를 포함합니다. Apache Lucene 구현에서는 사전을 유한 상태 변환기(FST, Finite State Transducer)로 최적화하여 메모리와 검색 성능을 모두 확보합니다.
검색 실행 경로와 성능 고려사항
사용자가 검색 쿼리를 입력하면, 먼저 인덱싱 시간과 동일한 텍스트 분석 과정을 거쳐 항으로 토크나이징됩니다. 그 후 사전에서 각 항을 O(1) 조회하여 포스팅 리스트를 획득하고, 여러 항의 포스팅 리스트를 교집합 연산으로 빠르게 결합합니다. 검색 성능은 매칭된 문서 수에만 비례하며 전체 코퍼스 크기에는 무관합니다. 다만, 역 인덱스는 업데이트에 비용이 높다는 트레이드오프가 존재합니다. 문서 업데이트 시에는 기존 문서를 삭제 표시하고 새로운 세그먼트에 인덱싱한 후, 세그먼트 병합을 통해 최종 정리됩니다.