C++ 검색 엔진 구현 | 역색인·TF-IDF 랭킹·자동완성

들어가며: “검색 결과가 왜 이렇게 나오지?”

검색 엔진의 핵심

사이트 내 검색, 로그 분석, 문서 검색을 구현할 때 “단순 문자열 검색”만으로는 부족합니다. 역색인(Inverted Index)으로 빠르게 문서를 찾고, TF-IDF로 관련도 순으로 정렬하고, 자동완성으로 사용자 경험을 높여야 합니다. 이 글에서는 C++로 전문 검색 엔진의 핵심을 구현합니다.

역색인 구조, TF-IDF 랭킹, 토큰화, Trie 기반 자동완성을 차례로 구현하고 운영 환경에 맞게 최적화합니다.

요구 환경: 예제가 std::shared_mutex와 std::optional을 쓰므로 C++17 이상으로 컴파일합니다.

단순 문자열 검색으로 부족해지는 상황

사이트 내 검색이 너무 느림

블로그나 문서 사이트에서 “검색”을 누르면 전체 문서를 순회하며 grep처럼 찾는 방식은 검색 시간이 전체 텍스트 크기에 비례해 늘어납니다. 역색인을 쓰면 단어 → 문서 목록으로 해시 조회 한 번에 접근하므로, 비용이 전체 문서 수가 아니라 “그 단어가 들어 있는 문서 수”에 비례하게 됩니다.

검색 결과 순서가 이상함

“C++ 메모리 관리”를 검색했는데, “메모리”만 한 번 나오는 문서가 맨 위에 나옵니다. TF-IDF로 단어 빈도와 문서 내 중요도를 반영하면, 실제로 관련 있는 문서가 상위에 노출됩니다.

한글 검색이 제대로 안 됨

“검색엔진”을 검색했는데 “검색”, “엔진”으로 분리되지 않아 결과가 없습니다. 토큰화(Tokenization)와 형태소 분석으로 단어 단위 인덱싱이 필요합니다.

자동완성이 없음

사용자가 “C++“를 입력하는 동안 “C++ 메모리”, “C++ 스마트 포인터” 같은 제안이 없어 불편합니다. Trie 기반 자동완성으로 입력 중 실시간 제안을 제공할 수 있습니다.

대용량 인덱스 메모리 부족

수백만 문서를 인덱싱하면 역색인이 수 GB를 차지합니다. 메모리 매핑, 압축, 분할 인덱스로 제한된 리소스에서도 동작하도록 설계해야 합니다.

---

인덱서·랭커·자동완성으로 나뉜 구조

전체 구조

검색 엔진은 인덱싱 파이프라인과 검색 파이프라인으로 나뉩니다.

flowchart TB
    subgraph Indexing[인덱싱 파이프라인]
        D1[문서 입력]
        D1 --> T1[토큰화]
        T1 --> T2[정규화]
        T2 --> I1[역색인 구축]
        I1 --> I2[TF-IDF 가중치 계산]
    end
    subgraph Search[검색 파이프라인]
        Q1[쿼리 입력]
        Q1 --> Q2[쿼리 토큰화]
        Q2 --> Q3[역색인 조회]
        Q3 --> Q4[TF-IDF 스코어링]
        Q4 --> Q5[랭킹 정렬]
        Q5 --> Q6[결과 반환]
    end
    I2 --> Index["(역색인)"]
    Index --> Q3
    subgraph Autocomplete[자동완성]
        A1[Trie]
        Q1 -.->|입력 중| A1
    end

시퀀스 다이어그램

sequenceDiagram
    participant User as 사용자
    participant API as 검색 API
    participant Index as 역색인
    participant Trie as 자동완성 Trie
    User->>API: "C++ 메모리" 검색
    API->>API: 쿼리 토큰화 ["C++", "메모리"]
    API->>Index: 각 토큰별 문서 ID 조회
    Index-->>API: Posting List
    API->>API: TF-IDF 스코어 계산
    API->>API: 상위 N개 정렬
    API-->>User: 검색 결과
    User->>API: "C++" 입력 중
    API->>Trie: prefix "C++" 조회
    Trie-->>API: ["C++ 메모리", "C++ 스마트 포인터", ...]
    API-->>User: 자동완성 제안

핵심 포인트:

• 역색인: 단어 → (문서 ID, TF) 리스트. 검색 시 단어로 바로 문서 집합을 찾습니다.
• TF-IDF: Term Frequency × Inverse Document Frequency. 흔한 단어보다 특정 문서에만 자주 나오는 단어에 높은 가중치.
• Trie: 접두사 검색에 최적화된 트리. 자동완성에 사용합니다.

---

역색인 구현

Posting 구조

역색인에서 각 단어(term)는 Posting List를 가집니다. 각 Posting은 (문서 ID, TF) 쌍입니다.

// posting.hpp
#pragma once
#include <cstdint>
#include <vector>
namespace search {
// 단일 문서 내에서의 term 등장 정보
struct Posting {
    uint32_t doc_id;
    uint32_t term_freq;  // 해당 문서에서 term 등장 횟수
    Posting(uint32_t d, uint32_t tf) : doc_id(d), term_freq(tf) {}
};
// 역색인: term -> Posting List
// TF-IDF 계산을 위해 term_freq 저장
using PostingList = std::vector<Posting>;
}  // namespace search

역색인 인덱서

// inverted_index.hpp
#pragma once
#include "posting.hpp"
#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
#include <cstdint>
namespace search {
class InvertedIndex {
public:
    using DocId = uint32_t;
    // 문서 추가: doc_id와 토큰화된 term 목록
    void add_document(DocId doc_id, const std::vector<std::string>& terms) {
        // term별 빈도 계산
        std::unordered_map<std::string, uint32_t> term_freq;
        for (const auto& term : terms) {
            if (!term.empty()) {
                term_freq[term]++;
            }
        }
        // Posting 추가
        for (const auto& [term, freq] : term_freq) {
            index_[term].emplace_back(doc_id, freq);
        }
        // 문서 수 갱신 (IDF 계산용)
        num_docs_ = std::max(num_docs_, doc_id + 1);
    }
    // term의 Posting List 조회
    const std::vector<Posting>* get_postings(const std::string& term) const {
        auto it = index_.find(term);
        if (it == index_.end()) return nullptr;
        return &it->second;
    }
    // 문서 수 (IDF 계산용). doc_id를 0부터 빈틈없이 부여한다고 가정
    uint32_t num_documents() const { return num_docs_; }
    // term이 등장하는 문서 수
    uint32_t document_frequency(const std::string& term) const {
        auto* postings = get_postings(term);
        return postings ? postings->size() : 0;
    }
private:
    std::unordered_map<std::string, std::vector<Posting>> index_;
    uint32_t num_docs_ = 0;
};
}  // namespace search

주의점: Posting List는 보통 doc_id 순 정렬되어 있어야 merge 연산(AND 검색)이 효율적입니다. 위 예제는 단순화했으며, 프로덕션에서는 인덱싱 시 정렬하거나 정렬된 구조(Vector, Skip List)를 사용합니다. 문서를 doc_id가 증가하는 순서로만 추가한다면 emplace_back만으로 자연스럽게 정렬이 유지되므로, 증가하는 ID를 부여하는 것 자체가 가장 싼 정렬 방법입니다.

num_docs_를 “지금까지 본 가장 큰 doc_id + 1”로 계산하는 점도 기억해 둘 만합니다. ID를 1, 1000, 50000처럼 띄엄띄엄 부여하면 실제 문서는 3개인데 N은 50001이 되어 IDF가 부풀려집니다. 문서 삭제를 지원하게 되면 같은 문제가 생기므로, 실제 서비스에서는 추가·삭제 시 늘리고 줄이는 별도 카운터를 두는 편이 정확합니다.

---

TF-IDF 랭킹

TF-IDF 공식

• TF (Term Frequency): 문서 내 term 등장 빈도. 많이 나올수록 중요.
• IDF (Inverse Document Frequency): log(N / df) — N은 전체 문서 수, df는 term이 등장하는 문서 수. 흔한 단어일수록 가중치 감소.
• 스코어: TF × IDF (또는 정규화된 변형)

// tfidf.hpp
#pragma once
#include "inverted_index.hpp"
#include <cmath>
#include <string>
#include <vector>
// 패키지 선언
namespace search {
class TFIDFScorer {
public:
    explicit TFIDFScorer(const InvertedIndex& index) : index_(index) {}
    // 단일 term에 대한 문서 스코어 계산
    double score_term(const std::string& term, uint32_t doc_id, uint32_t tf) const {
        uint32_t N = index_.num_documents();
        uint32_t df = index_.document_frequency(term);
        if (N == 0 || df == 0) return 0.0;
        // IDF: log((N + 1) / (df + 1)) + 1 (스무딩)
        double idf = std::log(static_cast<double>(N + 1) / (df + 1)) + 1.0;
        // TF: 1 + log(1 + tf) (sublinear scaling — 과도한 반복 억제)
        double tf_score = 1.0 + std::log(1.0 + tf);
        return tf_score * idf;
    }
    // 쿼리 [t1, t2, ...]에 대한 문서 총 스코어
    double score_document(
        const std::vector<std::string>& query_terms,
        uint32_t doc_id
    ) const {
        double total = 0.0;
        for (const auto& term : query_terms) {
            auto* postings = index_.get_postings(term);
            if (!postings) continue;
            for (const auto& p : *postings) {
                if (p.doc_id == doc_id) {
                    total += score_term(term, doc_id, p.term_freq);
                    break;
                }
            }
        }
        return total;
    }
private:
    const InvertedIndex& index_;
};
}  // namespace search

BM25 변형: 실무에서는 TF-IDF 대신 BM25를 많이 씁니다. Lucene(Elasticsearch·OpenSearch의 기반)도 기본 유사도로 BM25를 씁니다. BM25의 TF 항은 tf × (k1 + 1) / (tf + k1 × (1 − b + b × 문서길이 / 평균길이)) 꼴이라 두 가지를 동시에 합니다. 첫째, tf가 커져도 점수가 k1 + 1에 수렴하는 상한이 있어 같은 단어를 수십 번 반복한 스팸성 문서가 점수를 독식하지 못합니다. 둘째, b(보통 0.75)로 문서 길이를 보정합니다. 위 score_term의 1 + log(1 + tf)는 첫 번째 효과만 부분적으로 흉내 낼 뿐 길이 보정이 없어서, 이 엔진으로 실제 문서를 색인해 보면 긴 문서가 상위에 몰리는 경향이 바로 보입니다. BM25로 바꾸려면 인덱싱할 때 문서별 토큰 수를 따로 저장해 두기만 하면 됩니다.

---

공백 분리와 한글·영문 혼합 토큰화

간단한 토큰화 (공백 분리)

// tokenizer.hpp
#pragma once
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
namespace search {
// 헤더에 정의하는 함수는 inline이어야 여러 .cpp에서 포함해도 링크 에러가 나지 않는다
inline char to_lower_ascii(char c) {
    return static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
}
// 공백 기준 분리 + 소문자화 (영문)
inline std::vector<std::string> tokenize_simple(const std::string& text) {
    std::vector<std::string> tokens;
    std::string current;
    for (char c : text) {
        if (std::isspace(static_cast<unsigned char>(c)) || c == ',' || c == '.') {
            if (!current.empty()) {
                std::transform(current.begin(), current.end(), current.begin(), to_lower_ascii);
                tokens.push_back(std::move(current));
                current.clear();
            }
        } else {
            current += c;
        }
    }
    if (!current.empty()) {
        std::transform(current.begin(), current.end(), current.begin(), to_lower_ascii);
        tokens.push_back(std::move(current));
    }
    return tokens;
}

한글/영문 혼합 토큰화 (자소 분리 없이)

한글은 형태소 분석기(MeCab, Kiwi 등)를 붙이는 것이 정석이지만, C++ 단독으로는 n-gram 또는 공백+특수문자 분리로 대체할 수 있습니다.

// 한글 음절 단위 분리 (초성/중성/종성 분리 없이)
// "검색엔진" -> ["검색", "엔진"] 또는 [검색엔진] (사전 기반 필요)
inline std::vector<std::string> tokenize_korean_simple(const std::string& text) {
    std::vector<std::string> tokens;
    std::string current;
    for (unsigned char c : text) {
        // 0x80 이상(UTF-8 멀티바이트 한글 등)은 토큰의 일부로 유지.
        // isalnum만 쓰면 한글 바이트가 전부 구분자로 취급되어 사라짐.
        bool keep = c >= 0x80 || std::isalnum(c) || c == '+' || c == '#';
        if (!keep) {
            if (!current.empty()) {
                tokens.push_back(std::move(current));
                current.clear();
            }
        } else {
            current += c;
        }
    }
    if (!current.empty()) {
        tokens.push_back(std::move(current));
    }
    return tokens;
}
// 통합 토큰화: 영문은 소문자, 한글은 그대로
inline std::vector<std::string> tokenize(const std::string& text) {
    auto tokens = tokenize_korean_simple(text);
    for (auto& t : tokens) {
        // 영문만 소문자화
        bool all_ascii = std::all_of(t.begin(), t.end(), [](char c) {
            return static_cast<unsigned char>(c) < 128;
        });
        if (all_ascii) {
            std::transform(t.begin(), t.end(), t.begin(), to_lower_ascii);
        }
    }
    return tokens;
}
}  // namespace search

실무 팁: 한글 품질을 높이려면 외부 형태소 분석기를 C++에서 호출하거나, 사전 기반 최장 일치를 구현합니다. 이 글에서는 단순 분리만 다룹니다.

이 토큰화 코드에서 처음 흔히 겪는 문제는 두 가지입니다(::tolower에 char를 그대로 넘기면 UTF-8 바이트처럼 음수인 값에서 정의되지 않은 동작이 되므로, 위 코드는 unsigned char로 변환하는 도우미를 씁니다). 첫째, std::isalnum은 바이트 하나를 현재 로캘 기준으로 판정하므로 UTF-8 한글의 각 바이트(0x80 이상)를 영숫자로 보지 않습니다. 그래서 조건을 isalnum만으로 쓰면 한글 문서를 색인해도 토큰이 하나도 남지 않는, “영어는 검색되는데 한글은 전혀 안 된다”는 증상이 나옵니다. 위 코드는 0x80 이상 바이트를 토큰에 포함하도록 고쳐 두었습니다. 둘째, +와 #을 구분자로 취급하면 “C++“와 “C#“이 모두 “c”로 줄어들어 서로 구분되지 않으므로, 프로그래밍 관련 문서를 다룬다면 이런 기호를 토큰 문자로 남겨 두는 편이 낫습니다. 이 함수들을 헤더에 정의했으므로 inline을 붙여, 여러 .cpp에서 포함해도 multiple definition 링크 에러가 나지 않게 했습니다.

---

자동완성 (Trie)

Trie 노드

// trie.hpp
#pragma once
#include <string>
#include <unordered_map>
#include <vector>
#include <memory>
namespace search {
class Trie {
public:
    void insert(const std::string& word) {
        Node* node = &root_;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = std::make_unique<Node>();
            }
            node = node->children[c].get();
        }
        node->is_end = true;
        node->word = word;  // 완성된 단어 저장 (선택)
    }
    // prefix로 시작하는 단어들 (최대 max_results개)
    std::vector<std::string> search_prefix(const std::string& prefix,
                                           size_t max_results = 10) const {
        const Node* node = &root_;
        for (char c : prefix) {
            auto it = node->children.find(c);
            if (it == node->children.end()) {
                return {};
            }
            node = it->second.get();
        }
        std::vector<std::string> results;
        collect_words(node, results, max_results);
        return results;
    }
private:
    struct Node {
        // 주의: 표준은 불완전 타입을 원소로 허용하는 컨테이너를 vector·list·forward_list로만 보장한다.
        // unordered_map<char, unique_ptr<Node>>는 주요 구현에서 동작하지만 이식성을 따지면
        // std::vector<std::pair<char, std::unique_ptr<Node>>>가 안전하다.
        std::unordered_map<char, std::unique_ptr<Node>> children;
        bool is_end = false;
        std::string word;  // 리프에서만 사용
    };
    void collect_words(const Node* node,
                      std::vector<std::string>& results,
                      size_t max_results) const {
        if (results.size() >= max_results) return;
        if (node->is_end && !node->word.empty()) {
            results.push_back(node->word);
        }
        for (const auto& [c, child] : node->children) {
            collect_words(child.get(), results, max_results);
            if (results.size() >= max_results) break;
        }
    }
    Node root_;
};
}  // namespace search

children이 unordered_map이라 결과 순서는 정해져 있지 않습니다. 자동완성 품질을 높이려면 빈도 기반 정렬을 넣습니다. 각 단어에 빈도를 저장하고, 후보를 모두 모은 뒤 빈도 순으로 상위 N개를 고르거나, 노드마다 “이 아래에서 가장 인기 있는 단어 N개”를 미리 저장해 두는 방식이 흔합니다.

---

통합 검색 엔진 클래스와 사용 예시

통합 검색 엔진 클래스

// search_engine.hpp
#pragma once
#include "inverted_index.hpp"
#include "tfidf.hpp"
#include "tokenizer.hpp"
#include "trie.hpp"
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
namespace search {
struct SearchResult {
    uint32_t doc_id;
    double score;
    std::string snippet;  // 미리보기 (선택)
};
class SearchEngine {
public:
    // 문서 추가
    void add_document(uint32_t doc_id, const std::string& title, const std::string& content) {
        auto terms = tokenize(title + " " + content);
        // 제목에 가중치 (제목 term 2회 반영)
        for (const auto& t : tokenize(title)) {
            terms.push_back(t);
        }
        index_.add_document(doc_id, terms);
        // 자동완성용: 제목/인기 검색어 등
        for (const auto& t : tokenize(title)) {
            if (t.size() >= 2) {
                trie_.insert(t);
            }
        }
    }
    // 검색
    std::vector<SearchResult> search(const std::string& query, size_t top_k = 10) {
        auto query_terms = tokenize(query);
        if (query_terms.empty()) return {};
        TFIDFScorer scorer(index_);
        // 문서별 스코어 집계
        std::unordered_map<uint32_t, double> doc_scores;
        for (const auto& term : query_terms) {
            auto* postings = index_.get_postings(term);
            if (!postings) continue;
            for (const auto& p : *postings) {
                double s = scorer.score_term(term, p.doc_id, p.term_freq);
                doc_scores[p.doc_id] += s;
            }
        }
        // 스코어 순 정렬
        std::vector<SearchResult> results;
        for (const auto& [doc_id, score] : doc_scores) {
            if (score > 0) {
                results.push_back({doc_id, score, ""});
            }
        }
        std::sort(results.begin(), results.end(),
             [](const SearchResult& a, const SearchResult& b) {
                return a.score > b.score;
            });
        if (results.size() > top_k) {
            results.resize(top_k);
        }
        return results;
    }
    // 자동완성: Trie에는 tokenize를 거친(영문 소문자) 단어가 들어 있으므로 prefix도 같은 규칙으로 정규화
    std::vector<std::string> autocomplete(std::string prefix, size_t max = 10) {
        bool all_ascii = std::all_of(prefix.begin(), prefix.end(),
            [](char c) { return static_cast<unsigned char>(c) < 128; });
        if (all_ascii) {
            std::transform(prefix.begin(), prefix.end(), prefix.begin(), to_lower_ascii);
        }
        return trie_.search_prefix(prefix, max);
    }
private:
    InvertedIndex index_;
    Trie trie_;
};
}  // namespace search

사용 예시

// main.cpp
#include "search_engine.hpp"
#include <iostream>
int main() {
    search::SearchEngine engine;
    // 문서 추가
    engine.add_document(0, "C++ 메모리 관리", "C++에서 스마트 포인터를 사용한 메모리 관리 방법.");
    engine.add_document(1, "C++ 스마트 포인터", "unique_ptr, shared_ptr, weak_ptr 설명.");
    engine.add_document(2, "검색 엔진 구현", "역색인과 TF-IDF를 이용한 검색 엔진 구현.");
    // 검색
    auto results = engine.search("C++ 메모리", 5);
    for (const auto& r : results) {
        std::cout << "doc_id=" << r.doc_id << " score=" << r.score << "\n";
    }
    // 자동완성
    auto suggestions = engine.autocomplete("C++", 5);
    for (const auto& s : suggestions) {
        std::cout << "  " << s << "\n";
    }
    return 0;
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.14)
project(search_engine LANGUAGES CXX)
set(CMAKE_CXX_STANDARD 17)
add_executable(search_engine
    main.cpp
)
target_include_directories(search_engine PRIVATE ${CMAKE_CURRENT_SOURCE_DIR})

---

빈 검색 결과, 한글 검색 실패, Trie 메모리 폭증: 에러 해결

검색 결과가 비어 있음

증상: 쿼리를 넣었는데 항상 빈 결과가 나옵니다. 원인: 인덱싱과 검색의 토큰화·정규화가 다르거나(대소문자 포함), 인덱스가 비어 있는 경우가 대부분입니다. 해결법:

// ❌ 잘못된 예: 인덱싱은 소문자, 검색은 원문
index_.add_document(0, tokenize_lower(doc));  // "C++" -> "c++"
auto terms = tokenize(query);                 // "C++" -> "C++" (그대로)
// ✅ 올바른 예: 동일한 tokenize 함수 사용
index_.add_document(0, tokenize(doc));
auto terms = tokenize(query);

원인을 좁힐 때는 num_documents()가 0보다 큰지, 검색어를 토큰화한 결과의 각 토큰에 대해 get_postings(term)이 nullptr인지를 로그로 찍어 보면 어느 단계에서 어긋났는지 바로 보입니다. 앞의 자동완성처럼 사용자 입력을 받는 모든 경로가 같은 정규화를 거치는지도 확인합니다.

---

메모리 부족 (OOM)

증상: 대량 문서 인덱싱 시 std::bad_alloc 원인: 역색인이 전부 메모리에 상주. 수백만 문서 × 평균 100 term이면 수 GB. 해결법:

// 1. Posting List 압축 (VByte, Simple9 등)
// 2. 메모리 매핑 파일로 디스크 오프로드
// 3. 배치 인덱싱 후 디스크에 저장, 검색 시 mmap
// ✅ 예: 문서 수 제한 또는 배치 플러시
constexpr size_t MAX_IN_MEMORY_DOCS = 100000;
if (index_.num_documents() >= MAX_IN_MEMORY_DOCS) {
    flush_index_to_disk();
    index_.clear();
}

---

검색 속도가 느림

증상: 쿼리당 수백 ms 이상 원인:

1. Posting List가 정렬되지 않아 선형 스캔
2. 스코어 계산 시 불필요한 반복
3. 결과 정렬 비용 해결법:

// ✅ Posting List를 doc_id 순 정렬 (인덱싱 시 1회)
void add_document(DocId doc_id, const std::vector<std::string>& terms) {
    // ... term_freq 계산 ...
    for (const auto& [term, freq] : term_freq) {
        index_[term].emplace_back(doc_id, freq);
    }
}
// 인덱싱 완료 후:
for (auto& [term, list] : index_) {
    std::sort(list.begin(), list.end(),
              [](const Posting& a, const Posting& b) { return a.doc_id < b.doc_id; });
}

---

한글 검색이 안 됨

증상: “검색엔진” 검색 시 결과 없음 원인: “검색엔진”이 하나의 토큰으로만 저장되어 있으며, “검색”, “엔진”으로 분리되지 않음 해결법:

// n-gram 인덱싱: "검색엔진" -> "검색", "색엔", "엔진" (2-gram)
// UTF-8에서 한글 한 글자는 3바이트이므로 바이트가 아니라 "글자 시작 위치" 기준으로 자름
std::vector<std::string> ngram_tokenize(const std::string& text, size_t n = 2) {
    std::vector<size_t> starts;  // 각 글자(코드 포인트)의 시작 바이트 위치
    for (size_t i = 0; i < text.size(); ++i) {
        if ((static_cast<unsigned char>(text[i]) & 0xC0) != 0x80) starts.push_back(i);
    }
    starts.push_back(text.size());
    std::vector<std::string> tokens;
    for (size_t k = 0; k + n < starts.size(); ++k) {
        tokens.push_back(text.substr(starts[k], starts[k + n] - starts[k]));
    }
    return tokens;
}
// 또는 외부 형태소 분석기 연동 (MeCab, Kiwi 등)

n-gram 방식은 사전이 없어도 “검색엔진”에서 “엔진”을 찾을 수 있게 해 주지만 대가가 있습니다. 한 단어에서 여러 토큰이 나오므로 인덱스 크기가 몇 배로 커지고, “색엔”처럼 의미 없는 조각이 다른 단어와 우연히 겹쳐 엉뚱한 문서가 걸리는 정확도 문제가 생깁니다. 검색어도 반드시 같은 n-gram으로 쪼개 AND 조건으로 찾아야 하며, 한 글자 검색어는 2-gram 인덱스에서 아예 찾을 수 없다는 점도 설계할 때 정해 둬야 합니다. 바이트 단위로 substr을 하면 한글 글자가 중간에서 잘려 깨진 문자열이 인덱스에 들어가므로, 위처럼 UTF-8 글자 경계를 기준으로 잘라야 합니다.

---

Trie 메모리 폭증

증상: 자동완성 Trie가 수 GB 사용 원인: 모든 고유 단어를 Trie에 넣으며, 단어 수가 수백만 개 해결법:

// ✅ 인기 검색어만 Trie에 저장 (상위 10만 개 등)
// ✅ 또는 DAWG/MA-FSA 같은 압축 Trie 사용
// ✅ 인덱스와 별도로 "인기 쿼리"만 Trie에 유지

---

스레드 안전성

증상: 멀티스레드에서 검색 시 크래시 또는 잘못된 결과 원인: InvertedIndex, Trie가 동시 읽기/쓰기에 안전하지 않음 해결법:

// ✅ 검색은 공유 락, 인덱싱은 배타 락
#include <shared_mutex>
class InvertedIndex {
    mutable std::shared_mutex mtx_;
public:
    void add_document(...) {
        std::unique_lock lock(mtx_);
        // ...
    }
    // 포인터를 반환하면 락이 풀린 뒤 다른 스레드의 add_document가
    // 벡터를 재할당해 포인터가 무효화될 수 있으므로 복사본을 반환한다
    PostingList get_postings_copy(const std::string& term) const {
        std::shared_lock lock(mtx_);
        auto it = index_.find(term);
        return it == index_.end() ? PostingList{} : it->second;
    }
};

복사 비용이 부담되면 검색 함수 전체를 공유 락 안에서 실행하거나, 앞의 “Double Buffer”처럼 읽기 전용 인덱스를 std::shared_ptr로 교체하는 방식이 낫습니다.

---

Skip List·스코어 캐싱·Early Termination

Posting List 정렬 및 Skip List

AND 검색 시 두 Posting List를 merge할 때, 정렬된 리스트면 투 포인터로 O(n+m)에 가능합니다. 리스트가 길면 Skip List로 일부만 읽어 성능을 높일 수 있습니다.

// 두 정렬된 Posting List의 교집합 (AND)
std::vector<Posting> merge_and(
    const std::vector<Posting>& a,
    const std::vector<Posting>& b)
{
    std::vector<Posting> result;
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i].doc_id == b[j].doc_id) {
            result.push_back(a[i]);
            ++i; ++j;
        } else if (a[i].doc_id < b[j].doc_id) {
            ++i;
        } else {
            ++j;
        }
    }
    return result;
}

스코어 캐싱

동일 쿼리가 반복되면 LRU 캐시로 (query → top_k 결과)를 저장합니다.

#include <lru_cache.hpp>  // 또는 직접 구현
std::optional<std::vector<SearchResult>> cache_lookup(const std::string& query) {
    static LRUCache<std::string, std::vector<SearchResult>> cache(1000);
    return cache.get(query);
}

상위 K개만 유지하기

상위 K개만 필요할 때, 힙을 사용해 모든 문서를 정렬하지 않고 K개만 유지합니다. 후보가 n개면 전체 정렬의 O(n log n) 대신 O(n log K)입니다. 검색 엔진에서 말하는 본격적인 early termination(WAND, MaxScore)은 여기서 더 나아가, 단어별 최대 점수 상한을 이용해 상위 K에 들 수 없는 문서는 점수 계산 자체를 건너뜁니다.

// 상위 K개만 유지하는 최소 힙
auto cmp = [](const SearchResult& a, const SearchResult& b) {
    return a.score > b.score;  // 최소 힙: 점수 낮은 것이 top
};
std::priority_queue<SearchResult, std::vector<SearchResult>, decltype(cmp)> heap(cmp);
for (const auto& [doc_id, score] : doc_scores) {
    if (heap.size() < top_k) {
        heap.push({doc_id, score, ""});
    } else if (score > heap.top().score) {
        heap.pop();
        heap.push({doc_id, score, ""});
    }
}

메모리 풋프린트 어림하기

정확한 크기는 데이터에 따라 다르므로, 구조로부터 직접 계산해 보는 편이 좋습니다. 이 글의 Posting은 uint32_t 두 개라 8바이트입니다. 문서 100만 개가 각각 고유 단어 100개를 가진다면 posting은 1억 개, 순수 데이터만 약 800MB이고, 여기에 std::vector의 여유 용량과 unordered_map 노드·문자열 키의 오버헤드가 더해집니다. doc_id를 정렬해 두고 이전 ID와의 차이(gap)를 VByte로 저장하면, 자주 나오는 단어일수록 차이 값이 작아져 1~2바이트로 줄어들기 때문에 압축 효과가 큽니다. Trie는 노드마다 unordered_map을 들고 있어 글자당 수십 바이트 이상을 쓰므로, 단어 수가 늘면 역색인보다 먼저 메모리 문제를 일으키기도 합니다.

---

인덱스 분할·업데이트 전략·헬스 체크

인덱스 분할 (Sharding)

문서를 여러 인덱스 샤드로 나누고, 쿼리 시 모든 샤드에 병렬 요청 후 결과를 merge합니다.

std::vector<SearchResult> search_sharded(const std::string& query, size_t top_k) {
    std::vector<std::future<std::vector<SearchResult>>> futures;
    for (auto& shard : shards_) {
        futures.push_back(std::async(std::launch::async, [&shard, &query, top_k]() {
            return shard.search(query, top_k * 2);  // 각 샤드에서 더 가져와 merge
        }));
    }
    std::vector<SearchResult> all;
    for (auto& f : futures) {
        auto r = f.get();
        all.insert(all.end(), r.begin(), r.end());
    }
    std::sort(all.begin(), all.end(), ...);
    if (all.size() > top_k) all.resize(top_k);  // 조건 없이 resize하면 결과가 적을 때 빈 항목이 채워짐
    return all;
}

샤딩에서 가장 놓치기 쉬운 것은 점수의 기준입니다. 각 샤드가 자기 문서만으로 IDF를 계산하면, 같은 단어라도 샤드 A에서는 흔하고 샤드 B에서는 드물어 점수가 서로 다른 잣대로 매겨집니다. 이렇게 합친 top-k는 샤드 배정에 따라 순위가 흔들립니다. Elasticsearch가 샤드별 통계를 먼저 모으는 dfs_query_then_fetch 검색 유형을 따로 제공하는 이유가 이것이며, 직접 구현한다면 전체 문서 빈도를 한곳에 모아 IDF를 통일하거나, 문서를 해시로 고르게 분배해 샤드 간 통계 차이를 작게 유지해야 합니다. 각 샤드에서 top_k * 2처럼 여유 있게 가져오는 것도 이 차이로 인해 전체 상위권 문서가 잘리는 것을 줄이기 위한 장치입니다.

인덱스 업데이트 전략

• 전체 재구축: 주기적으로 전체 인덱스 재생성 (구현 단순)
• 증분 인덱스: 새 문서만 추가, 삭제는 비트맵으로 마스킹
• Double Buffer: 새 인덱스 구축 후 원자적으로 스왑

Docker Compose 예시

# docker-compose.search.yml (Compose v2에서는 version 키가 필요 없음)
services:
  search-api:
    build: .
    ports:
      - "8080:8080"
    environment:
      - INDEX_PATH=/data/index
      - CACHE_SIZE_MB=512
    volumes:
      - index-data:/data
    deploy:
      resources:
        limits:
          memory: 2G
  # 선택: Redis로 쿼리 캐시
  redis:
    image: redis:7-alpine
    ports:
      - "6379:6379"
volumes:
  index-data:

헬스 체크

// /health 엔드포인트
bool is_healthy() const {
    return index_.num_documents() > 0 && !index_corrupt_;
}

메트릭 수집

// Prometheus 메트릭 예시
// search_duration_seconds - 검색 지연
// search_queries_total - 쿼리 수
// index_documents_total - 인덱스된 문서 수

---

자주 묻는 질문 (FAQ)

Q. Elasticsearch 대신 직접 구현하는 이유는?

A. 의존성 최소화, 임베디드/엣지 환경, 학습 목적에 적합합니다. 대규모 분산 검색이 필요하면 Elasticsearch/OpenSearch를 사용하는 것이 좋습니다.

Q. 한글 검색 품질을 높이려면?

A. 형태소 분석기(MeCab, Kiwi)를 C++에서 호출하거나, n-gram 인덱싱을 적용합니다. 상용 검색 엔진은 보통 전문 형태소 분석기를 사용합니다. 다음 글: C++ 프로파일러 비교: perf 화염 그래프, gprof, Valgrind Callgrind, VTune, Tracy 이전 글: [C++ 실전 가이드 #50-8] 이전 글

---

같이 보면 좋은 글

• C++ 시리즈 전체 보기
• C++ 데이터베이스 엔진 구현 | B-Tree·트랜잭션·쿼리 최적화 [#50-4]
• 구간 쿼리와 누적합을 위한 트리
• C++에서 RabbitMQ·Kafka 연동하기

---