색인

색인은 찾을 것을 미리 정리해 두어서 찾을 때 전부 뒤지지 않게 해 줍니다. 책 뒤의 찾아보기가 가장 익숙한 색인입니다. 데이터베이스에서는 같은 것을 주로 인덱스라고 부릅니다. 검색 엔진에서는 문서를 넣을 때 만드는 찾아보기와 그것을 만드는 일을 모두 색인이라고 부릅니다.

상세

이 절은 검색 엔진의 색인이 무엇을 담고 어떻게 만들어지는지를 봅니다. 검색에서 문서는 찾아 줄 대상 한 건입니다. 예로는 쇼핑몰 상품 세 개를 씁니다. 상품 하나가 문서 한 건입니다.

요리책의 찾아보기

두꺼운 요리책에서 두부 요리를 찾는다고 해 봅시다. 첫 쪽부터 한 장씩 넘기는 사람은 없습니다. 뒤쪽 찾아보기에서 「두부 · 34쪽, 112쪽」을 보고 그 두 쪽만 펼칩니다.

찾아보기는 책을 다 쓴 뒤에 누군가 한 번 공들여 만든 것입니다. 그 한 번의 수고 덕에 읽는 사람은 찾을 때마다 책 전체를 넘기지 않습니다.

색인이라는 말

찾기 쉽게 미리 정리해 둔 목록을 색인이라고 부릅니다. 영어로는 인덱스(index)입니다. 책의 찾아보기가 그 원래 모습입니다.

데이터베이스에서는 이 말을 주로 「인덱스」로 씁니다. 흔한 예는 회원 테이블의 이메일 열 값을 정렬해 두는 구조입니다. 정렬돼 있으니 그 값으로 행을 빨리 찾습니다.

검색 엔진에서 색인은 두 가지를 함께 가리킵니다. 하나는 문서를 넣을 때 만들어 두는 찾아보기 자체입니다. 다른 하나는 그 찾아보기를 만드는 작업입니다. 「문서를 색인한다」고 하면 문서를 찾아보기에 넣는다는 뜻입니다.

이 편은 검색 엔진 쪽 뜻을 따라갑니다. 작업을 가리킬 때는 「색인 작업」, 결과물을 가리킬 때는 「색인」이라고 씁니다.

색인이 없을 때의 검색

상품 하나, 게시글 하나가 각각 문서 한 건입니다. 문서마다 번호가 붙어 있어서 검색 결과로는 이 번호를 돌려줍니다.

상품 문서 세 개를 두고 「무선」이 든 상품을 찾아보겠습니다.

색인이 없으면 방법은 하나입니다. 문서를 하나씩 열어 설명에 「무선」이 있는지 봅니다. 문서가 셋이면 금방 끝납니다. 천만 개면 천만 개를 다 읽습니다.

이렇게 전부 읽는 일은 검색마다 되풀이됩니다. 같은 문서 모음을 하루에 백만 번 검색하면 같은 글을 백만 번 다시 읽는 셈입니다.

찾을 때 할 일을 넣을 때 해 두기

색인은 이 되풀이를 끊습니다. 문서가 들어올 때 글을 한 번 낱말로 쪼갭니다. 그리고 낱말마다 그 낱말이 든 문서 번호를 적어 둡니다. 검색할 때는 찾는 낱말의 번호 목록만 읽습니다.

아래 코드는 두 방법을 나란히 놓습니다. 위쪽은 찾을 때마다 전부 읽습니다. 아래쪽은 넣을 때 한 번 정리합니다.

docs = {1: "무선 이어폰",
        2: "유선 이어폰",
        3: "무선 마우스"}

# 색인 없이: 찾을 때마다 전부 읽는다
hits = [n for n, text in docs.items()
        if "무선" in text.split()]
hits  # [1, 3]

# 색인: 넣을 때 한 번 정리해 둔다
index = {}
for n, text in docs.items():
    for word in text.split():
        index.setdefault(word, []).append(n)

index["무선"]    # [1, 3]
index["이어폰"]  # [1, 2]

두 방법은 같은 답을 냅니다. 다른 것은 일하는 때입니다. 아래쪽은 위쪽이 검색마다 하던 일을 문서를 넣을 때 한 번만 합니다. 검색 때는 목록 하나를 꺼냅니다.

그래서 색인이 있으면 검색 시간이 문서 수를 따르지 않습니다. 찾는 낱말의 번호 목록이 얼마나 긴지를 따릅니다. 문서가 천만 개여도 「무선」이 든 문서가 백 개면 번호 백 개만 읽습니다.

이 「낱말에서 문서 번호 목록으로」 가는 찾아보기가 역색인입니다. 문서를 열면 낱말이 보이는 보통 방향을 뒤집었다고 해서 붙은 이름입니다. 검색 엔진 색인의 한가운데에 이 역색인이 있습니다.

색인 작업이 거치는 단계

이 소절은 문서 한 건이 색인에 들어가기까지를 따라갑니다. 첫 단계는 글을 낱말로 쪼개는 일입니다.

글을 검색 단위로 쪼개는 일을 토큰화라고 합니다. 앞의 코드는 띄어쓰기로 쪼갰습니다. 띄어쓰기만으로 모자랄 때가 많아서 쪼갠 뒤에 한 번 더 다듬습니다.

다듬는 일은 낱말의 모양을 하나로 맞추는 것입니다. 「Earphones」는 「earphone」으로, 「이어폰을」은 「이어폰」으로 적습니다. 쪼개고 다듬는 일을 묶어 맡는 부품을 분석기라고 부릅니다.

한국어는 낱말 끝에 조사와 어미가 붙습니다. 그래서 낱말을 뜻의 가장 작은 단위로 나누는 형태소 분석을 분석기 안에 둡니다. 조사를 떼어 내야 「이어폰을」과 「이어폰이」가 같은 낱말로 모입니다.

분석을 마친 낱말은 역색인에 들어갑니다. 낱말마다 붙은 문서 번호 목록에 이 문서의 번호를 더합니다. 이 번호 목록을 포스팅 리스트라고 부릅니다.

검색어도 같은 분석기를 지나야 합니다. 넣을 때 「이어폰을」을 「이어폰」으로 적었다고 해 봅시다. 찾을 때 「이어폰을」을 손대지 않고 찾으면 색인에 그런 낱말이 없습니다. 두 쪽의 낱말 모양이 같아야 색인에서 만납니다.

flowchart TD
    subgraph 넣을때["문서를 넣을 때"]
        D["문서"] --> A1["분석기"]
    end
    subgraph 찾을때["검색할 때"]
        Q["검색어"] --> A2["같은 분석기"]
    end
    A1 -->|낱말과 문서 번호를 적는다| I["색인"]
    A2 -->|낱말로 목록을 읽는다| I
    I --> R["문서 번호 목록"]

그림의 두 길은 색인에서 만납니다. 한쪽은 적습니다. 다른 쪽은 읽습니다. 둘 사이에 같은 분석기가 서 있어야 적힌 낱말과 읽는 낱말이 맞아떨어집니다.

색인에 함께 적는 것

검색은 후보를 고르는 데서 끝나지 않습니다. 후보에 순서를 매겨야 합니다. 결과 화면에 상품 설명도 보여 줘야 합니다. 그래서 색인에는 역색인 말고도 몇 가지가 함께 들어갑니다.

전체 통계는 설명이 조금 더 필요합니다.

검색 결과의 순서는 문서가 검색어와 얼마나 맞는지로 정합니다. 이 맞는 정도를 수로 매긴 값이 관련도 점수입니다. 점수가 높은 문서가 위에 옵니다.

점수를 매길 때는 낱말이 얼마나 드문지가 크게 작용합니다. 상품 천 개 중 900개에 든 「무료」는 검색어로서 가려내는 힘이 약합니다. 열 개에만 든 「방수」는 후보를 크게 줄입니다. 낱말마다 그 낱말이 든 문서 수를 문서 빈도라고 부릅니다.

이 값을 검색할 때마다 세면 결국 문서를 다 읽게 됩니다. 그래서 문서를 넣을 때 통계를 함께 고쳐 적어 둡니다. 관련도 점수를 매기는 식들은 이 통계를 색인에서 꺼내 씁니다.

문서 길이도 점수에 쓰입니다. 같은 「방수」라도 한 줄짜리 설명에 든 것이 긴 설명 속 한 번보다 그 상품을 더 잘 말해 줍니다. 이 차이를 반영하려고 점수 식은 흔히 문서 길이를 평균 문서 길이와 견줍니다. 평균보다 짧은 문서에 든 낱말을 더 무겁게 칩니다.

넣은 뒤 검색에 걸리기까지

문서를 넣었다고 바로 검색에 걸리지 않을 수 있습니다. 까닭은 저장된 색인을 고치는 방식에 있습니다.

앞의 코드는 목록 끝에 번호를 더하기만 했습니다. 실제 색인은 목록마다 번호를 정렬하고 목록끼리 빈틈없이 이어 붙여 저장합니다. 이런 큰 색인 한가운데에 문서를 하나씩 끼워 넣으면 그때마다 긴 목록을 고쳐 써야 합니다.

그래서 많은 검색 엔진은 새 문서를 모아 작은 색인을 따로 만듭니다. 이 작은 색인 하나를 흔히 세그먼트라고 부릅니다.

검색은 큰 색인과 작은 색인을 모두 봅니다. 작은 색인이 늘수록 검색 한 번에 열어 볼 곳도 늘어납니다. 그러니 작은 색인이 여럿 쌓이면 하나로 합칩니다. 이 일을 세그먼트 병합이라고 부릅니다.

문서를 지울 때도 같은 문제가 생깁니다. 저장된 목록에서 번호 하나를 빼려면 긴 목록을 다시 써야 합니다. 그래서 지울 때는 그 문서에 「지웠음」 표시만 따로 남깁니다. 검색은 이 표시가 붙은 문서를 결과에서 뺍니다.

표시된 문서는 세그먼트 병합 때 치웁니다. 합치면서 새 목록을 쓸 때 그 번호를 옮겨 적지 않습니다.

문서를 고칠 때는 지우기와 넣기로 나눠 처리합니다. 옛 문서에 지웠음 표시를 남긴 뒤 고친 문서를 새 문서처럼 넣습니다.

새 문서는 작은 색인이 만들어져 검색 대상에 오른 뒤에야 걸립니다. 넣은 때와 찾을 수 있는 때 사이에 틈이 생깁니다. 게시글을 쓰자마자 목록에서 검색해 보는 화면이라면 이 틈을 먼저 따져야 합니다.

분석기를 바꿀 때의 재색인

색인에는 분석기를 지난 뒤의 낱말이 적혀 있습니다. 그래서 분석기를 바꾸면 이미 적힌 낱말과 새로 쪼갠 낱말의 모양이 어긋납니다.

처음에 띄어쓰기로만 쪼갰다고 해 봅시다. 옛 문서의 「이어폰을」은 색인에 「이어폰을」로 적혀 있습니다. 나중에 조사를 떼도록 분석기를 바꾸면 새 검색어는 「이어폰」으로 쪼개집니다. 옛 문서는 이 검색에 걸리지 않습니다.

이럴 때는 모든 문서를 새 분석기로 처음부터 다시 색인합니다. 이 작업을 재색인이라고 부릅니다.

문서가 많으면 오래 걸립니다. 그래서 흔히 새 색인을 옆에 따로 만듭니다. 다 되면 검색 대상을 새 색인으로 바꿔 답니다.

색인이 치르는 값

색인은 찾을 때의 일을 넣을 때로 옮긴 것입니다. 옮긴 일은 사라지지 않습니다. 넣는 쪽과 저장 공간이 떠안습니다.

그래서 색인은 한 번 넣고 여러 번 찾는 데이터에 맞습니다. 상품 목록, 게시글, 도움말 문서처럼 쌓인 뒤 계속 검색되는 데이터가 그렇습니다.

모든 찾기에 검색 엔진의 색인이 필요하지는 않습니다. 기본 키로 행 하나를 찾거나 가격 범위로 거르는 일은 데이터베이스 인덱스가 맡습니다. 검색 엔진의 색인은 글 속 낱말로 문서를 찾는 전문 검색을 위해 만듭니다.

관련 항목

색인을 이루는 구성 요소

역색인 · 포스팅 리스트 · 포스팅 · 용어 사전 · 문서 · 세그먼트 · 문서 빈도

색인에 넣기 전에 글이 거치는 처리 단계

분석기 · 토큰화 · 토큰 · 토크나이저 · 형태소 분석 · 불용어 · 어간 추출

색인을 읽어 도는 검색 방식

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

색인을 새로 고치고 다시 만드는 작업

증분 색인 · 색인 갱신 · 세그먼트 병합 · 재색인 · 리프레시

색인을 만들어 쓰는 검색 라이브러리와 엔진

Apache Lucene · Elasticsearch · OpenSearch · Solr

색인과 이름을 나눠 쓰는 데이터베이스 인덱스

인덱스 · B-tree · 해시 인덱스 · GIN · 테이블 풀 스캔

색인이 속하는 상위 분류

검색 엔진 · 검색 · 자료구조