역색인 (Inverted Index)

구글이 "인공지능"을 입력한 0.3초 만에 수십억 페이지에서 결과를 뽑아내는 핵심 자료구조

한눈에 — 책 뒤편 <찾아보기>를 떠올리자. "광합성 … 42, 87쪽"처럼 단어 → 그 단어가 나오는 위치 목록이 적혀 있다. 검색 엔진도 똑같이 모든 문서를 미리 한 번 훑어 "단어마다 그 단어를 담은 문서 번호 목록"을 만들어 둔다. 이 목록을 포스팅 리스트(posting list)라 하고, 전체 표를 역색인이라 한다. 검색할 때는 문서를 다시 읽지 않고 포스팅 리스트만 교집합하면 끝난다.

1. 정방향 색인 vs 역방향 색인

원래 데이터는 문서 → 단어들 방향이다(정방향, forward index). "문서 3에 어떤 단어가 있나?"엔 빠르지만, "'로봇'이란 단어가 어느 문서에 있나?"를 알려면 모든 문서를 처음부터 끝까지 읽어야 한다(전체 스캔). 역색인은 이 화살표를 뒤집어(invert) 단어 → 문서들로 저장한다. 그래서 이름이 "역(inverted)"이다.

정방향 색인

doc1 -> [고양이, 잔다, 소파]
doc2 -> [고양이, 로봇, 청소]
doc3 -> [로봇, 팔, 공장]

"로봇 어디 있어?" → doc1,2,3 전부 확인

역방향 색인

고양이 -> [doc1, doc2]
로봇   -> [doc2, doc3]
소파   -> [doc1]
공장   -> [doc3]

"로봇 어디 있어?" → 한 줄만 보면 [doc2, doc3]

2. 색인은 어떻게 만들어지나 — 분석(analysis) 파이프라인

문장을 그대로 넣지 않는다. 아래 단계를 거쳐 정규화된 토큰(term)으로 바꾼 뒤에야 색인에 넣는다. 아무 문장이나 넣어 각 단계가 무엇을 하는지 살펴보자.

① 토큰화 공백·문장부호로 자르기 · ② 소문자화 Robot=robot · ③ 불용어 제거 the, are 처럼 거의 모든 문서에 있어 변별력 없는 단어 버리기 · ④ 어간 추출(stemming) cleaning→clean, robots→robot

3. 살아있는 역색인 — 직접 검색해 보기

아래 8개의 짧은 문서로 만든 역색인이다. 검색어를 입력하면 검색 엔진이 하는 일을 단계별로 보여준다. 여러 단어를 넣으면 AND(모두 포함) 또는 OR(하나라도 포함)로 합친다.

로봇 고양이 잠 공장 로봇 팔 바다 우주 학교

문서 모음

역색인 (검색어에 등장한 term은 강조)

term	df	posting list (문서 번호 · 등장 횟수)

4. 포스팅 리스트 교집합이 빠른 이유

포스팅 리스트는 문서 번호 오름차순으로 정렬해 저장한다. 그래서 두 리스트의 교집합(AND)을 지퍼 잠그듯 양쪽 포인터를 한 번씩만 훑어 O(n + m)에 구한다. 정렬·해시 필요 없다.

# 두 포스팅 리스트의 교집합 (둘 다 정렬돼 있음)
def intersect(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]:
            i += 1          # a가 뒤처짐 → a만 전진
        else:
            j += 1          # b가 뒤처짐 → b만 전진
    return out

팁: 가장 짧은 포스팅 리스트부터 교집합하면 중간 결과가 빨리 줄어 더 빠르다. 그래서 df(문서 빈도)가 작은 term을 먼저 처리한다.

5. 순위 매기기 — TF-IDF

AND 검색 결과가 100만 건이면 어떤 순서로 보여줄까? 고전적인 점수가 TF-IDF다.

TF (Term Frequency) — 이 문서에서 그 단어가 많이 나올수록 관련성 ↑ tf = 등장 횟수
IDF (Inverse Document Frequency) — 희귀한 단어일수록 정보량 ↑. 전체 N개 문서 중 df개에만 나오면 idf = log(N / df). 거의 모든 문서에 있는 단어는 idf ≈ 0 → 사실상 무시된다(불용어 자동 처리).
점수 — 검색어의 각 term에 대해 tf × idf를 더한 값. 이 페이지의 검색 결과도 이 점수로 정렬된다.

실제 검색 엔진은 여기에 BM25(TF 포화 보정), 링크 점수(PageRank), 최신성, 개인화, 클릭 로그 학습(Learning to Rank) 등 수백 개 신호를 얹는다.

6. 규모의 기술

문제	해법
포스팅 리스트가 문서 수억 개	델타 인코딩 + 가변 바이트 — [17, 195, 812] 를 차이값 [17, 178, 617]로 저장해 작은 수로 압축
"서울 맛집" 처럼 구(phrase) 검색	위치 색인(positional index) — 문서 번호뿐 아니라 단어가 몇 번째에 나왔는지도 저장
새 문서가 계속 추가됨	세그먼트 병합 — 작은 색인을 메모리에 만들고 주기적으로 큰 색인과 합침 (Lucene의 방식)
한 대에 안 들어감	샤딩 — 문서를 여러 서버에 나눠 각자 검색 후 결과 병합 (Elasticsearch)
오타 `로부슬`	편집 거리 · n-gram 색인으로 비슷한 term 후보를 찾아 교정

어디서 쓰나 — 구글·네이버 웹 검색, Elasticsearch / OpenSearch / Apache Lucene·Solr, 데이터베이스의 전문 검색 인덱스(MySQL FULLTEXT, PostgreSQL GIN), 코드 검색(GitHub, ripgrep의 사전 색인), 로그 분석(Kibana), 이메일 검색까지 — "많은 텍스트에서 단어로 찾기"가 필요한 거의 모든 곳.

핵심 한 줄 — 문서를 미리 뒤집어 "단어 → 문서 목록"으로 저장해 두면, 검색은 문서를 읽는 게 아니라 목록을 합치는 일이 된다.