역색인

역색인은 낱말 하나를 주면 그 낱말이 든 문서들을 곧바로 알려 줍니다. 문서를 하나씩 열어 보며 낱말을 찾을 필요가 없어집니다. 검색 엔진이 많은 글 속에서 검색어가 든 글을 빨리 추려 내는 바탕이 이것입니다.

상세

이 절은 역색인이 어떤 모양이고 왜 그 모양이어야 하는지를 봅니다. 먼저 책 뒤의 찾아보기에 빗대어 모양을 잡습니다. 그다음 글 속 낱말을 찾으려면 왜 모든 글을 읽게 되는지 짚습니다.

예로는 짧은 문서 세 개를 씁니다. 이 셋으로 역색인을 만들어 검색해 보고 크기와 비용을 따집니다. 끝에서는 이 구조가 쓰이는 곳과 맞지 않는 곳을 정리합니다.

책 뒤의 찾아보기에 빗대면

두꺼운 기술 서적 뒤쪽에는 찾아보기가 있습니다. 「가비지 컬렉션 · 42쪽, 118쪽」처럼 낱말 옆에 그 낱말이 나오는 쪽 번호가 적혀 있습니다. 궁금한 낱말이 있으면 책을 처음부터 넘기지 않고 찾아보기에서 쪽 번호를 얻어 그 쪽만 펼칩니다.

역색인은 이 찾아보기를 쪽 번호 대신 문서 번호로 만든 것입니다. 낱말을 주면 그 낱말이 든 문서 번호가 나옵니다.

문서와 낱말

검색에서 문서는 찾아 줄 대상 한 건을 가리킵니다. 게시글 하나, 상품 하나, 로그 한 줄이 각각 문서가 됩니다. 문서마다 번호가 붙어 있어서 결과로는 이 번호를 돌려줍니다.

이 절에서 쓸 문서는 셋입니다.

모든 글을 읽는 검색

「배송」이 든 문서를 찾는 가장 단순한 방법은 문서를 하나씩 열어 글 속에 「배송」이 있는지 보는 것입니다. 데이터베이스에서 WHERE body LIKE '%배송%' 로 찾는 것이 이 방식입니다. 문서가 세 개면 금방 끝나지만 천만 개면 천만 개를 다 읽습니다.

찾기 쉽게 미리 정리해 둔 목록을 색인이라고 합니다. 영어로는 인덱스입니다. 데이터베이스에서는 이것을 인덱스라는 이름으로 씁니다.

그런데 body 열에 데이터베이스 인덱스를 걸어도 이 검색은 빨라지지 않습니다. 인덱스는 흔히 B-tree로 만듭니다. B-tree 는 열의 값을 통째로 정렬해 두는 구조입니다.

정렬된 값은 앞머리로 찾을 때만 도움이 됩니다. 「당일」로 시작하는 글은 정렬 순서에서 한데 모여 있어 빨리 찾습니다. 「배송」이 글 가운데 들어 있으면 정렬 순서가 아무 단서도 주지 못해 결국 전부 읽습니다.

역색인은 이 문제를 풀려고 열쇠를 바꿉니다. 글 전체를 열쇠로 삼지 않고 글 속 낱말 하나하나를 열쇠로 삼습니다.

낱말에서 문서로

문서를 열면 그 안의 낱말이 보입니다. 아래 표처럼 문서에서 낱말로 가는 방향으로 정리한 색인이 순방향 색인입니다.

위 표는 「1번에 무슨 낱말이 있나」에는 바로 답합니다. 「배송이 어느 문서에 있나」에는 답하지 못합니다. 그 질문에 답하려면 줄을 전부 훑어야 합니다.

역색인은 이 표를 뒤집습니다. 낱말이 줄의 머리에 섭니다. 그 낱말이 든 문서 번호가 옆에 붙습니다. 「역」은 방향이 거꾸로라는 뜻입니다.

이제 「배송」을 찾으면 「배송」 줄 하나만 읽고 1번과 2번을 얻습니다. 문서가 셋이든 천만 개든 읽는 줄은 검색어의 낱말 수만큼입니다.

용어 사전과 포스팅 리스트

역색인은 두 부분으로 이루어집니다. 하나는 색인에 오른 낱말을 모두 모은 목록입니다. 이 목록을 용어 사전이라고 부릅니다. 검색 쪽에서는 딕셔너리라고도 합니다.

다른 하나는 낱말마다 붙은 문서 번호 목록입니다. 이 목록을 포스팅 리스트라고 부릅니다. 목록 안의 번호 하나하나가 포스팅입니다. 위 표에서 「당일」의 포스팅 리스트는 1, 3 입니다.

아래 그림은 세 문서로 만든 역색인의 모양입니다. 위의 상자가 용어 사전입니다. 화살표 끝이 각 낱말의 포스팅 리스트입니다.

flowchart TD
    subgraph 용어사전["용어 사전 · 낱말 여섯"]
        T1["당일"]
        T2["무료"]
        T3["배송"]
        T4["안내"]
        T5["조건"]
        T6["환불"]
    end
    T1 --> P1["1, 3"]
    T2 --> P2["2"]
    T3 --> P3["1, 2"]
    T4 --> P4["1, 3"]
    T5 --> P5["2"]
    T6 --> P6["3"]

용어 사전은 낱말로 빨리 찾아야 하므로 해시테이블이나 정렬된 목록, 트리로 둡니다. 정렬해 두면 「배」로 시작하는 낱말을 모두 찾는 앞머리 검색도 할 수 있습니다.

포스팅 리스트는 문서 번호가 작은 것부터 오도록 정렬해 둡니다. 이 정렬이 뒤에 나올 「두 낱말이 다 든 문서 찾기」를 빠르게 만듭니다.

코드로 만들어 보기

백엔드 개발자에게 익숙한 모양으로 옮기면 역색인은 「낱말 → 번호 목록」 맵입니다. 아래는 파이썬으로 세 문서의 역색인을 만든 것입니다.

docs = {1: "당일 배송 안내",
        2: "무료 배송 조건",
        3: "당일 환불 안내"}

index = {}
for no, text in docs.items():
    for word in text.split():
        index.setdefault(word, []).append(no)

index["당일"]  # [1, 3]
index["배송"]  # [1, 2]

문서를 번호 순서로 넣었기 때문에 목록 끝에 붙이기만 해도 번호가 정렬된 채로 쌓입니다. 새 문서에 늘 더 큰 번호를 주면 이 성질이 유지됩니다.

포스팅에 더 적는 값

포스팅에는 문서 번호만 적을 수도 있고 더 적을 수도 있습니다. 흔히 함께 적는 값은 그 문서에서 낱말이 나온 횟수와 위치입니다.

횟수는 결과의 순서를 정할 때 씁니다. 한 문서에 「배송」이 다섯 번 나오면 한 번 나온 문서보다 검색어와 더 맞는다고 봅니다. 문서가 검색어와 얼마나 맞는지 매긴 이 값이 관련도 점수입니다.

위치는 낱말이 붙어 있는지 볼 때 씁니다. 1번 문서에서 「배송」은 두 번째, 「안내」는 세 번째 낱말입니다. 위치가 이어져 있으니 「배송 안내」라는 구절을 붙은 채로 찾는 검색에 1번이 걸립니다. 이런 검색을 구문 검색이라고 부릅니다.

두 값까지 포스팅에 함께 적으면 검색이 더 많은 일을 합니다. 대신 포스팅 하나가 커져서 역색인이 차지하는 공간도 늡니다.

글을 낱말로 쪼개기

앞의 코드는 띄어쓰기로 낱말을 나눴습니다. 글을 검색 단위로 쪼개는 이 일을 토큰화라고 부릅니다. 쪼갠 조각 하나는 토큰입니다.

띄어쓰기만으로는 모자랄 때가 많습니다. 「배송을」과 「배송이」는 다른 조각이 되어 「배송」으로 찾으면 둘 다 안 걸립니다. 그래서 조사와 어미를 떼고 낱말의 기본형만 남깁니다. 한국어에서는 이 일에 형태소 분석을 씁니다.

영어라면 대문자와 소문자를 하나로 맞추는 일도 합니다. 「Apple」과 「apple」이 같은 줄에 적혀야 둘 중 무엇으로 찾아도 걸립니다. 쪼개고 다듬는 과정을 묶어 맡는 부품이 분석기입니다.

검색어도 같은 분석기를 거쳐야 합니다. 넣을 때는 「배송을」을 「배송」으로 적었는데 찾을 때 「배송을」 그대로 찾으면 용어 사전에 그런 낱말이 없습니다. 넣는 쪽과 찾는 쪽의 낱말 모양이 같아야 둘이 만납니다.

두 낱말이 다 든 문서 찾기

낱말 하나를 찾을 때는 용어 사전에서 그 낱말을 찾고 포스팅 리스트를 읽으면 끝납니다. 검색어가 「당일 배송」처럼 두 낱말이면 두 목록을 함께 봐야 합니다.

두 낱말이 다 든 문서만 원하면 두 목록에 모두 있는 번호를 고릅니다. 「당일」은 1, 3 이고 「배송」은 1, 2 이니 답은 1번입니다. 두 목록에 겹치는 것만 남기는 이 셈이 교집합입니다.

둘 중 하나라도 든 문서를 원하면 두 목록을 합칩니다. 답은 1, 2, 3번입니다. 「그리고」와 「또는」으로 후보를 거르는 이 방식이 불리언 검색입니다.

목록이 길어지면 교집합을 어떻게 구하느냐가 속도를 가릅니다. 두 목록이 정렬돼 있으니 앞에서부터 나란히 걸으면 됩니다. 두 번호가 같으면 답에 넣고 둘 다 한 칸 나아갑니다. 다르면 작은 쪽만 한 칸 나아갑니다.

세 문서로는 목록이 너무 짧습니다. 아래 코드는 더 긴 번호 목록 두 개로 봅니다.

def both(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
        else:
            j += 1
    return out

a = [2, 5, 9, 14]
b = [5, 8, 14, 20]
both(a, b)  # [5, 14]

두 목록을 한 번씩만 지나가므로 걸리는 시간은 두 목록 길이의 합에 비례합니다. 목록이 정렬돼 있지 않았다면 한쪽 번호마다 다른 쪽을 처음부터 뒤져야 했습니다.

흔한 낱말과 드문 낱말

포스팅 리스트의 길이는 낱말마다 크게 다릅니다. 드문 낱말은 목록이 짧습니다. 거의 모든 문서에 나오는 낱말은 목록이 문서 수만큼 깁니다.

그래서 낱말 여럿이 다 든 문서를 찾을 때는 가장 짧은 목록부터 겹쳐 봅니다. 짧은 목록과 먼저 겹치면 후보가 금방 줄어 뒤의 긴 목록에서 볼 번호도 줄어듭니다.

영어의 the · a 처럼 거의 모든 문서에 나오고 뜻은 적은 낱말은 아예 색인에서 빼기도 합니다. 이런 낱말을 불용어라고 부릅니다. 빼면 공간을 아끼지만, 그 낱말이 뜻을 가르는 드문 검색은 못 하게 됩니다.

복잡도

속도는 빅오 표기법으로 적습니다. O(n) 은 걸리는 시간이 n 에 비례해 는다는 뜻입니다.

아래 표에서 p 는 포스팅 리스트의 길이입니다. k 는 문서 하나에 든 낱말 수입니다.

용어 사전 조회는 해시테이블로 두면 평균 O(1) 입니다. 정렬된 목록이나 트리로 두면 서로 다른 낱말 수를 V 라 할 때 O(log V) 입니다.

표에는 전체 문서 수가 안 나옵니다. 검색 시간은 문서가 얼마나 많은지가 아니라 찾는 낱말의 목록이 얼마나 긴지를 따릅니다. 모든 글을 읽는 검색은 모든 글의 길이를 더한 만큼 시간이 듭니다.

흔한 낱말이면 목록이 문서 수만큼 길어집니다. 그때도 글 전체가 아니라 번호만 읽으므로 모든 글을 읽는 검색보다 훨씬 적게 읽습니다.

번호 대신 간격 적기

포스팅 리스트는 역색인에서 공간을 가장 많이 차지합니다. 흔한 낱말은 목록 하나에 번호가 수백만 개씩 들어갑니다. 그래서 목록을 줄여 담는 방법이 여럿 쓰입니다.

대표적인 방법은 번호 대신 앞 번호와의 간격을 적는 것입니다. 목록이 정렬돼 있어서 간격은 늘 0보다 크고 대개 작은 수가 됩니다. 차이만 적는 이 방식이 델타 인코딩입니다.

이 표도 세 문서보다 긴 번호 목록을 예로 듭니다. 첫 번호는 앞 번호가 없으므로 0에서부터의 간격으로 적습니다.

위 표에서 번호는 31 까지 커지지만 간격은 대부분 한 자릿수입니다. 작은 수는 적은 바이트로 적을 수 있습니다. 수의 크기에 맞춰 바이트 수를 달리 쓰는 방식을 가변 길이 정수라고 부릅니다.

간격으로 적으면 목록 가운데 번호 하나를 바로 읽을 수는 없습니다. 앞에서부터 간격을 더해 가야 번호가 나옵니다. 앞에서부터 나란히 걷는 교집합과는 잘 맞는 방식입니다.

고치기가 비싼 까닭

역색인은 읽기에 맞춘 구조라서 고치기가 비쌉니다. 문서 하나를 넣으면 그 문서에 든 낱말 수만큼 포스팅 리스트를 건드립니다. 낱말이 백 개인 글이면 목록 백 개를 손봅니다.

지우기는 더 까다롭습니다. 정렬된 목록 가운데서 번호 하나를 빼려면 뒤의 번호를 당겨야 합니다. 간격으로 적었다면 이웃 간격도 다시 계산해야 합니다. 그래서 지운 문서의 번호에 「지워졌다」는 표시만 남기고 검색 결과에서 걸러 내는 방식이 흔합니다.

새 문서도 큰 역색인에 바로 끼워 넣지 않는 경우가 많습니다. 새로 들어온 문서들로 작은 역색인을 따로 만듭니다. 검색할 때는 큰 것과 작은 것을 모두 봅니다. 작은 것이 여럿 쌓이면 큰 것과 합칩니다. 이때 지운 표시가 붙은 번호도 함께 정리합니다.

이 작은 역색인 하나를 흔히 세그먼트라고 부릅니다. 이 방식에서는 문서를 넣고 나서 잠깐 뒤에야 검색에 걸리기도 합니다. 작은 역색인이 만들어져 검색 대상에 오르기까지 시간이 걸리기 때문입니다.

역색인을 쓰는 곳

이 절은 역색인이 실제로 어디에 들어 있는지를 봅니다. 검색 엔진, 시계열 데이터베이스, 관계형 데이터베이스 셋입니다.

검색 엔진은 이 구조를 한가운데 둡니다. Elasticsearch와 OpenSearch는 Lucene이라는 검색 라이브러리 위에 서 있습니다. Lucene 이 만드는 것이 역색인입니다.

역색인은 글 검색에만 쓰이지 않습니다. 「이 값이 붙은 항목이 어느 것인가」를 묻는 곳이면 어디든 같은 모양이 나옵니다.

시계열 데이터베이스는 시각마다 찍힌 값을 줄줄이 모아 두는 저장소입니다. 값 한 줄을 시계열이라고 부릅니다. 서버 한 대의 요청 수를 시각 순서로 늘어놓은 줄이 시계열 하나입니다.

시계열이 여럿이면 서로 가를 이름표가 필요합니다. 그래서 줄마다 method="GET" 처럼 이름과 값을 짝지은 이름표를 붙입니다. 이 이름표가 레이블입니다. 여기서 method 가 이름이고 "GET" 이 값입니다.

시계열 데이터베이스는 레이블로 시계열을 찾을 때 역색인 모양을 씁니다. 시계열마다 문서처럼 번호를 붙입니다. 레이블 이름과 값의 짝 method="GET" 하나가 낱말 노릇을 합니다. 그 레이블이 붙은 시계열 번호 목록은 포스팅 리스트 노릇을 합니다.

레이블 조건 두 개로 거르면 두 목록의 교집합을 구합니다. 글 검색에서 두 낱말이 다 든 문서를 찾던 것과 같은 셈입니다.

레이블 값이 몇 가지인지를 카디널리티라고 부릅니다. 레이블에 새 값이 나타나면 그 값을 단 시계열이 새로 생깁니다. 용어 사전의 줄도 하나 늘고 목록도 하나 늡니다.

사용자 번호처럼 값이 끝없이 많은 것을 레이블로 달면 사용자마다 시계열이 새로 생깁니다. 그러면 색인이 걷잡을 수 없이 커집니다. 이 일이 카디널리티 폭발입니다.

관계형 데이터베이스에도 역색인을 쓰는 인덱스가 있습니다. PostgreSQL 의 GIN(Generalized Inverted Index, 일반화 역색인)이 그렇습니다. 배열이나 JSON(JavaScript Object Notation) 안에 든 값, 글 속 낱말로 행을 찾을 때 씁니다.

쓸 때와 안 쓸 때

맞는 쓰임과 안 맞는 쓰임을 함께 놓아 봅니다.

관련 항목

역색인을 이루는 구성 요소

용어 사전 · 딕셔너리 · 포스팅 리스트 · 포스팅 · 문서 · 토큰 · 세그먼트

역색인을 만들 때 글이 거치는 처리 단계

분석기 · 토큰화 · 토크나이저 · 형태소 분석 · 불용어 · 어간 추출 · 표제어 추출 · n-gram · 유니코드 정규화

역색인 위에서 도는 검색 방식

불리언 검색 · 구문 검색 · 전문 검색 · 관련도 점수 · TF-IDF · BM25 · 벡터 검색

역색인을 작고 빠르게 만드는 기법

교집합 · 델타 인코딩 · 가변 길이 정수 · 스킵 리스트 · 비트맵 인덱스 · 압축 · 세그먼트 병합

역색인과 같은 일을 두고 겨루는 자료구조

순방향 색인 · B-tree · 해시테이블 · 트라이 · 접미사 배열 · 블룸 필터

역색인을 채택한 제품과 인덱스

Lucene · Elasticsearch · OpenSearch · Solr · GIN · PostgreSQL · Prometheus

역색인으로 레이블을 찾는 시계열 저장소

시계열 데이터베이스 · 레이블 · 카디널리티 · 카디널리티 폭발 · 관측성 백엔드

역색인이 속하는 상위 분류

색인 · 인덱스 · 자료구조 · 검색 엔진 · 정보 검색