검색 엔진 내부 구조 완전 가이드 2025: Inverted Index, BM25, Ranking, Vector Search

TL;DR

• Inverted Index = 검색 엔진의 심장: 단어 → 문서 ID 리스트 매핑. 책 뒷면 색인의 디지털 버전
• BM25 > TF-IDF: 문서 길이 정규화 + 항 빈도 포화. Lucene/Elasticsearch의 기본 알고리즘
• Lucene이 모든 것의 기반: Elasticsearch, Solr, Vespa, OpenSearch 모두 Lucene 기반
• Vector Search의 부상: 의미 기반 검색. RAG, 추천 시스템의 핵심
• Hybrid Search가 표준: BM25 + Vector를 RRF(Reciprocal Rank Fusion)로 결합

1. 검색의 본질적 어려움

1.1 데이터베이스 LIKE의 한계

SELECT * FROM articles WHERE content LIKE '%redis%';

문제점:

1. 느림 — 100만 문서면 100만 번 비교, full table scan
2. 순서 없음 — 어떤 결과가 더 관련 있는지 모름
3. 단순 문자열만 — 어형 변화, 동의어, 오타 처리 못 함
4. 언어 무관 — "고양이"와 "고양이들"이 다른 단어

전통적 RDB는 검색에 부적합합니다. 전용 검색 엔진이 필요합니다.

1.2 검색 엔진이 해결하는 것

2. Inverted Index — 검색의 심장

2.1 직관

책 뒷면의 색인을 생각해보세요:

Apple ............ 23, 47, 89
Banana ........... 12, 34
Cherry ........... 5, 67, 102

Inverted Index도 같은 원리:

"redis"    → [doc1, doc5, doc100, doc234, ...]
"database" → [doc2, doc5, doc89, doc234, ...]
"cache"    → [doc1, doc100, doc500, ...]

검색 "redis AND database":

1. "redis"의 문서 리스트 가져오기 → [doc1, doc5, doc100, doc234]
2. "database"의 문서 리스트 가져오기 → [doc2, doc5, doc89, doc234]
3. 교집합 → [doc5, doc234]

O(1) 단어 룩업 + 리스트 교집합. 100만 문서에서도 밀리초.

2.2 Posting List 구조

각 단어의 문서 리스트를 posting list라고 합니다:

"redis":
  - doc1: positions=[5, 23], frequency=2
  - doc5: positions=[12], frequency=1
  - doc100: positions=[3, 17, 45], frequency=3

추가 정보:

• frequency: 문서 내 등장 횟수 (TF-IDF 계산용)
• positions: 문서 내 위치 (phrase 검색용)
• offsets: 원본 텍스트의 byte offset (highlighting용)

2.3 압축

수백만 문서 = 거대한 posting list. 압축이 필수:

• Delta encoding: [1, 5, 7, 12] → [1, 4, 2, 5] (차이만 저장)
• VByte encoding: 작은 숫자에 적은 byte
• PForDelta: Lucene이 사용하는 알고리즘
• Roaring Bitmaps: 매우 sparse한 set에 효율적

효과: 원본 대비 10-20% 크기. 수십억 문서를 GB 단위에 저장 가능.

2.4 디스크 vs 메모리

전체 인덱스를 메모리에 못 담으면:

• mmap: OS가 페이지 단위로 자동 캐싱
• cold posting: 자주 안 쓰이는 단어는 디스크에서 로드
• warm posting: 자주 쓰이는 단어는 메모리에 캐시

Lucene은 mmap을 광범위하게 사용 — OS의 페이지 캐시를 활용.

3. TF-IDF에서 BM25로

3.1 단순 카운트의 문제

"redis"가 들어간 문서 100개를 어떻게 정렬?

naive: 등장 횟수로 정렬 → 긴 문서가 무조건 위로 (불공정).

3.2 TF-IDF — 첫 번째 시도

TF (Term Frequency): 문서 내 단어 빈도

TF(t, d) = count(t in d) / total words in d

IDF (Inverse Document Frequency): 단어의 희귀성

IDF(t) = log(N / df(t))

• N: 전체 문서 수
• df(t): 단어가 들어간 문서 수

TF-IDF: TF × IDF

의미:

• TF 높음: 이 문서에 자주 나옴
• IDF 높음: 다른 문서에는 잘 안 나옴
• 둘 다 높음: 이 문서에 매우 특징적

3.3 TF-IDF의 문제

1. 선형 TF: 100번 나오면 50번 나오는 것의 2배 점수 → 비현실적
2. 문서 길이 무시: 긴 문서가 자연스럽게 더 많은 키워드 포함
3. 이론적 근거 부족: 휴리스틱

3.4 BM25 — Okapi BM25

1994년 등장. TF-IDF의 모든 문제를 해결:

BM25(D, Q) = Σ IDF(qi) × (f(qi, D) × (k1 + 1)) / (f(qi, D) + k1 × (1 - b + b × |D|/avgdl))

• f(qi, D): qi가 D에 나오는 횟수
• |D|: D의 길이
• avgdl: 평균 문서 길이
• k1: TF 포화 파라미터 (보통 1.2~2.0)
• b: 길이 정규화 강도 (보통 0.75)

3.5 BM25의 핵심 속성

1. TF 포화 (Saturation):

• 첫 번째 등장: 큰 점수 증가
• 두 번째: 작은 증가
• 100번째: 거의 증가 없음

의미: "redis가 5번 나옴 vs 1번 나옴"은 큰 차이지만, "redis가 100번 vs 50번"은 작은 차이.

2. 문서 길이 정규화:

• 평균보다 긴 문서는 점수 페널티
• 평균보다 짧은 문서는 점수 보너스
• b=0.75가 보통 최적

3. 이론적 근거: Probabilistic Information Retrieval 모델 기반.

3.6 왜 BM25가 25년 후에도 표준인가?

• 단순함: 파라미터 2개 (k1, b)
• 튜닝 쉬움: 대부분 기본값으로 충분
• 빠름: 인덱싱 시 미리 계산 가능
• 언어 독립적: 토큰화만 잘 하면 모든 언어
• 벤치마크 챔피언: TREC 등 공식 벤치마크에서 강력

Elasticsearch, Solr, Lucene, Vespa, Tantivy 모두 BM25 기본.

3.7 BM25F — 다중 필드

문서가 title, body, tags 등 여러 필드를 가질 때:

BM25F = Σ field_boost × BM25(field)

예시:

• title boost: 3.0
• body boost: 1.0
• tags boost: 2.0

"redis"가 title에 나오면 body보다 3배 점수.

4. Tokenization과 Analyzer

4.1 텍스트 → 토큰

검색 엔진은 텍스트를 직접 다루지 않습니다. 토큰으로 변환:

"Redis is a fast in-memory database!"
↓ tokenize
["redis", "is", "a", "fast", "in-memory", "database"]
↓ lowercase + stop words
["redis", "fast", "in-memory", "database"]
↓ stemming
["redis", "fast", "in-memori", "databas"]

4.2 Analyzer 구성

Elasticsearch/Lucene의 Analyzer:

Character Filter → Tokenizer → Token Filter

Character Filter: 원본 문자 변환

• HTML 태그 제거
• Unicode 정규화

Tokenizer: 토큰으로 분리

• Standard (공백 + 구두점)
• Whitespace (공백만)
• N-gram
• Korean nori, Japanese kuromoji, Chinese smartcn

Token Filter: 토큰 변환

• Lowercase
• Stop words 제거
• Stemming (Porter, Snowball)
• Synonym
• ASCII folding (é → e)

4.3 한국어 처리 — Nori

{
  "settings": {
    "analysis": {
      "analyzer": {
        "korean": {
          "type": "custom",
          "tokenizer": "nori_tokenizer",
          "filter": ["nori_part_of_speech", "lowercase"]
        }
      }
    }
  }
}

Nori의 처리:

"한국어 형태소 분석기" 
→ ["한국어", "형태", "소", "분석", "기"]

조사, 어미 제거 → 더 정확한 검색.

4.4 색인 시간 vs 쿼리 시간 분석

원칙: 같은 analyzer를 양쪽에 적용해야 함.

색인: "Running shoes" → ["run", "shoe"]  (stemming)
쿼리: "runs" → ["run"]                    (같은 stemming)
매치! ✅

만약 다르면:

색인: "Running shoes" → ["running", "shoes"]
쿼리: "runs" → ["run"]
매치 안 됨 ❌

5. 쿼리 종류

5.1 Boolean Query

{
  "bool": {
    "must": [
      { "match": { "content": "redis" } },
      { "match": { "content": "performance" } }
    ],
    "should": [
      { "match": { "tags": "tutorial" } }
    ],
    "must_not": [
      { "match": { "status": "draft" } }
    ],
    "filter": [
      { "range": { "year": { "gte": 2024 } } }
    ]
  }
}

• must: AND, 점수에 영향
• should: OR, 점수 boost
• must_not: NOT, 점수 X
• filter: AND, 점수 X (캐시 가능)

5.2 Phrase Query

정확한 구문 매칭:

{ "match_phrase": { "content": "redis cluster" } }

posting list의 position 정보 활용 — "redis"가 위치 5, "cluster"가 위치 6이면 매치.

slop: 단어 사이 거리 허용

{ "match_phrase": { "content": { "query": "redis cluster", "slop": 2 } } }

"redis hash cluster"도 매치 (slop=2).

5.3 Fuzzy Query (오타 허용)

{ "fuzzy": { "content": { "value": "rediis", "fuzziness": "AUTO" } } }

Levenshtein distance 기반:

• 1 = 1글자 차이
• 2 = 2글자 차이

AUTO: 단어 길이에 따라 자동

• 1-2글자: 0
• 3-5글자: 1
• 6+글자: 2

5.4 Wildcard / Prefix

{ "prefix": { "name": "redis" } }     // "redis", "redis-cluster", ...
{ "wildcard": { "name": "re*is" } }   // "redis", "remis", "rebis", ...

주의: 와일드카드는 느릴 수 있음. N-gram 인덱스가 더 효율적.

5.5 Range Query

{ "range": { "price": { "gte": 100, "lte": 500 } } }
{ "range": { "created_at": { "gte": "2024-01-01" } } }

숫자/날짜용. BKD-Tree 인덱스 사용 (Lucene 6+).

6. Lucene 내부 구조

6.1 Segment 기반 아키텍처

Lucene은 데이터를 segment로 저장:

• 각 segment는 immutable
• 새 데이터는 새 segment에
• 주기적으로 segment merge

Index/
  ├─ segment_001/
  ├─ segment_002/
  ├─ segment_003/
  └─ segment_004/

쓰기: 새 segment 생성. 빠름. 읽기: 모든 segment 검색 후 결합. Merge: 작은 segment들을 큰 것으로 통합. 백그라운드.

왜 immutable?: 동시성, 캐싱, 압축에 유리. Append-only는 항상 빠름.

6.2 Refresh와 Flush

Near-real-time search: 1초 후에는 검색 가능. 진정한 real-time은 아님.

6.3 BKD-Tree

Lucene 6+의 숫자 인덱스. K-dimensional Block Tree.

왜?: 숫자에 대해 효율적인 범위 쿼리.

price >= 100 AND price <= 500 같은 쿼리가 매우 빠름.

6.4 doc values

원본 문서를 byte offset으로 저장. 정렬, 집계, 필드 액세스에 사용.

columnar storage — 같은 필드의 값들이 연속 저장 → 캐시 친화적.

7. Vector Search — 의미 기반 검색

7.1 키워드 검색의 한계

쿼리: "강아지에게 좋은 음식"

키워드 매치:

• ✅ "강아지에게 좋은 음식"
• ❌ "반려견 사료 추천" (같은 의미, 다른 단어)
• ❌ "puppy food guide" (다른 언어)

키워드 검색은 표면적 매칭만 합니다.

7.2 Embedding 기반

텍스트를 **벡터(임베딩)**로 변환:

"강아지에게 좋은 음식" → [0.12, -0.34, 0.78, ..., 0.45]  (768차원)
"반려견 사료 추천"       → [0.15, -0.32, 0.81, ..., 0.42]  (비슷한 벡터)

의미가 비슷하면 벡터 거리가 가깝다.

7.3 코사인 유사도

cos_sim(A, B) = (A · B) / (|A| × |B|)

• 1.0 = 같은 방향 (매우 비슷)
• 0.0 = 직각 (관련 없음)
• -1.0 = 반대 (반대 의미)

7.4 ANN — Approximate Nearest Neighbor

수백만 벡터에서 가장 가까운 것 찾기. 정확한 검색은 O(N) → 너무 느림.

ANN 알고리즘:

• HNSW (Hierarchical Navigable Small World) — 가장 인기
• IVF (Inverted File) — Faiss
• PQ (Product Quantization) — 압축
• DiskANN — 디스크 기반

HNSW: log N 시간, 95%+ recall.

7.5 Vector DB

선택 가이드:

• 간편함: Pinecone (관리형)
• PostgreSQL 사용 중: pgvector
• 자체 호스팅 + 성능: Qdrant, Milvus
• Hybrid 검색 + 검색 엔진: Vespa, Elasticsearch + dense vector

8. Hybrid Search — BM25 + Vector

8.1 왜 Hybrid?

BM25만: 정확한 키워드는 잘 찾지만 동의어, 의미를 못 잡음. Vector만: 의미는 잘 잡지만 정확한 키워드(고유명사, 제품 코드)에 약함.

Hybrid: 두 방법 결과를 결합. 둘 다의 장점.

8.2 RRF — Reciprocal Rank Fusion

RRF_score(doc) = Σ 1 / (k + rank(doc, list_i))

• k: 보통 60
• rank(doc, list_i): i번째 검색 결과의 doc 순위

예시:

BM25 결과:    [doc5, doc1, doc3, doc7, doc2]
Vector 결과:  [doc1, doc3, doc8, doc5, doc4]

RRF (k=60):
doc5: 1/(60+1) + 1/(60+4) = 0.0319
doc1: 1/(60+2) + 1/(60+1) = 0.0325 ← 1위
doc3: 1/(60+3) + 1/(60+2) = 0.0319
doc7: 1/(60+4)            = 0.0156
doc2: 1/(60+5)            = 0.0154
doc8: 1/(60+3)            = 0.0159
doc4: 1/(60+5)            = 0.0154

장점:

• 점수 정규화 불필요
• 안정적
• 단순

8.3 Elasticsearch에서 RRF

{
  "retriever": {
    "rrf": {
      "retrievers": [
        {
          "standard": {
            "query": { "match": { "content": "redis cluster" } }
          }
        },
        {
          "knn": {
            "field": "embedding",
            "query_vector": [0.1, 0.2, ...],
            "k": 50
          }
        }
      ],
      "rank_window_size": 100,
      "rank_constant": 60
    }
  }
}

**Elasticsearch 8.8+**부터 RRF 네이티브 지원.

9. 검색 품질 평가

9.1 Precision vs Recall

• Precision: 검색 결과 중 관련된 비율
• Recall: 관련된 모든 것 중 검색된 비율

Precision = relevant ∩ retrieved / retrieved
Recall    = relevant ∩ retrieved / relevant

트레이드오프: 둘 다 높이기 어려움.

9.2 NDCG (Normalized Discounted Cumulative Gain)

순서를 고려한 점수:

• 상위에 있는 결과가 더 중요
• log 감쇠로 가중치
• 이상적 순서로 나누어 정규화 (0~1)

def ndcg_at_k(predicted, ideal, k=10):
    dcg = sum((2**rel - 1) / log2(i + 2) for i, rel in enumerate(predicted[:k]))
    idcg = sum((2**rel - 1) / log2(i + 2) for i, rel in enumerate(ideal[:k]))
    return dcg / idcg if idcg > 0 else 0

9.3 MAP (Mean Average Precision)

여러 쿼리에 대한 평균 정밀도. 검색 품질의 단일 지표.

9.4 A/B 테스팅

실제 사용자에게 두 알고리즘 비교:

• 클릭률 (CTR)
• 첫 클릭까지 시간
• 장바구니 추가율 (e-commerce)
• 세션 길이

10. 실전 — 검색 시스템 만들기

10.1 단계

1. 요구사항 분석: 무엇을 검색? 얼마나 빠르게? 얼마나 정확하게?
2. 데이터 소스: 어떤 문서들?
3. 인덱싱 파이프라인: 데이터 → 토큰 → 인덱스
4. 쿼리 인터페이스: API 디자인
5. 튜닝: BM25 파라미터, analyzer
6. 평가: NDCG, A/B 테스트
7. 개선: 의미 검색 추가, hybrid

10.2 작은 시스템 (수만 문서)

• Tantivy (Rust) 또는 Whoosh (Python)
• 단일 머신
• BM25만으로 충분

10.3 중간 시스템 (수백만 문서)

• Elasticsearch 또는 OpenSearch
• 3노드 클러스터
• BM25 + 한국어 analyzer
• 주기적 재인덱싱

10.4 대규모 (수십억 문서)

• Vespa (Yahoo, 가장 강력)
• 또는 자체 시스템 (Google, Bing 수준)
• BM25 + Neural Ranking
• ML 기반 personalization
• 분산 인덱스

10.5 RAG용 검색

• Vector DB (Pinecone, Qdrant, pgvector)
• Hybrid Search (BM25 + Vector + RRF)
• Re-ranking (Cohere, Voyage)
• Query expansion (LLM 기반)

퀴즈

참고 자료

• Lucene Documentation — 공식
• Elasticsearch: The Definitive Guide
• BM25 원논문 — Robertson et al.
• Introduction to Information Retrieval — Stanford 무료 책
• Tantivy — Rust 검색 엔진
• Vespa — Yahoo의 강력한 검색 + ML
• Faiss — Facebook ANN 라이브러리
• HNSW 원논문 — Malkov & Yashunin
• Reciprocal Rank Fusion — Cormack et al.
• Sentence-Transformers — 임베딩 라이브러리
• TREC — 검색 엔진 벤치마크