Search Engine & Inverted Index Physics

1. Overview

검색 엔진과 역인덱스(Search Engine & Inverted Index Physics)는 RDBMS의 LIKE '%keyword%' 풀스캔 쿼리가 대용량 텍스트(게시글 수백만 개, 로그 수십억 줄) 앞에서 완전히 붕괴될 때, 이를 $O(1)$ 속도로 구원하는 Full-Text Search(전문 검색) 엔진의 내부 물리 아키텍처를 해부합니다.

학습자는 문장을 단어 단위로 쪼개고 형태소를 분석하는 **텍스트 분석 파이프라인(Analyzer & Tokenizer)**을 뜯어봅니다. 나아가 책 맨 뒤의 "색인(찾아보기)"과 똑같은 원리인 역인덱스(Inverted Index) 구조가 단어에서 문서 ID로 즉각 점프하는 물리 엔진을 해부합니다. 마지막으로 어떤 문서가 사용자의 검색어와 가장 관련성이 높은지 수학적으로 점수를 매기는 TF-IDF와 BM25 랭킹 알고리즘, 그리고 Elasticsearch / Lucene의 분산 샤딩(Sharding) 매커니즘까지 장악하여 대규모 텍스트 기반 검색 및 로깅 백엔드 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 핵심 자료 구조 (Core Structure): 역인덱스(Inverted Index), Term Dictionary, Postings List(문서 ID 리스트).
• 텍스트 분석 프로세스 (Text Analysis): Character Filter, Tokenizer, Token Filter(소문자 변환, 어근 추출/Stemming, 불용어/Stopword 제거).
• 검색 알고리즘과 랭킹 (Search & Ranking): TF(단어 빈도), IDF(역문서 빈도), TF-IDF 계산식, Okapi BM25 랭킹.
• 엔진 아키텍처 (Engine Architecture): Apache Lucene 세그먼트(Segment) 구조, Elasticsearch/OpenSearch의 인덱스, 샤드(Shard), 마스터/데이터 노드 분산 처리 메커니즘.

Out-of-Scope

• 벡터 검색 및 임베딩 (Vector Search): 텍스트의 '의미(Semantic)' 공간을 계산하는 AI 기반 검색 체계 → 06-02-04 Vector Database 영역으로 위임 (여기서는 순수 키워드 매칭 기반).
• 로깅 스택 심화 연동: Logstash/Beats 인제스천(Ingestion) 및 Kibana 대시보드 시각화 → 09-06 Observability 영역.

Boundaries

• RDBMS 인덱스(B-Tree) vs 역인덱스(Inverted Index): B-Tree는 "특정 단어로 시작하는(Prefix, LIKE 'app%')" 검색이나 정확히 일치하는 문자열을 정렬하여 찾는 데 최적화되어 있습니다. 하지만 문장 "중간"에 포함된 단어(LIKE '%apple%')를 찾으려면 B-Tree는 완전히 무용지물이 되어 테이블 1,000만 건을 전부 훑어야(Full Scan) 합니다. 검색 엔진은 문장을 미리 쪼개어(Analyze) 'apple'이라는 단어가 3번, 5번, 100번 문서에 있다고 '역'으로 기록(Inverted Index)해 두기 때문에, 문장 중간 단어 검색이 $O(1)$ 속도로 폭발적으로 빨라지는 절대적인 차이가 존재합니다.

3. Counterexample

• 동의어 및 형태소 분석 누락 (Analyzer Missing): 사용자가 "달리는 고양이"를 검색했는데, 데이터베이스에는 "달린다 고양이"로 저장되어 있어 검색 결과가 0건 나오는 심각한 리콜(Recall, 재현율) 저하 문제. 영어의 경우 "running"을 검색해도 "run", "runs" 문서를 찾아주어야 합니다. 역인덱스 저장 시 Tokenizer와 Stemming(어간 추출) 필터를 거치지 않고 원본 텍스트 그대로 인덱싱해버리면 전문 검색 엔진의 의미가 완전히 퇴색됩니다.
• Elasticsearch 샤드 과다 쪼개기 (Oversharding Problem): 데이터가 100GB 정도밖에 안 되는 소규모 프로젝트임에도, "미래를 대비한다"며 Elasticsearch 인덱스의 Primary Shard(분할 단위) 수를 50개로 뻥튀기 설정. 각 샤드는 내부적으로 완전한 Lucene 엔진 인스턴스를 메모리와 스레드와 함께 띄웁니다. 50개의 샤드는 CPU와 JVM 힙 메모리(Heap) 오버헤드를 막대하게 소모하여, 데이터는 별로 없는데 클러스터 전체가 버벅거리고 죽어버리는 악명 높은 "오버샤딩 붕괴"를 유발합니다 (보통 샤드 1개당 20~50GB 권장).

4. Prerequisites

• 기본 자료구조 (Basic): 맵(해시맵, 딕셔너리) 및 배열 리스트의 탐색 원리. (04-02 Core Data Structures)
• RDBMS 한계 (Recommended): 인덱스와 LIKE 연산의 제약 사항. (06-01-02 SQL Engineering)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 책을 찢어 단어로 색인하다, 역인덱스 (Inverted Index)

• Why to Learn: RDBMS가 10초 걸리는 %키워드% 검색을 검색 엔진은 어떻게 0.01초 만에 해치우는지, 시선을 180도 뒤집어 "문서 안의 단어"가 아니라 "단어에 달린 문서"로 저장하는 역발상 자료구조를 꿰기 위함입니다.
• What to Learn:
  • Concepts: 정방향 인덱스(Forward Index, 문서 → 단어) vs 역방향 인덱스(Inverted Index, 단어 → 문서), 텀 딕셔너리(Term Dictionary, 트리 또는 해시), 포스팅 리스트(Postings List).
  • Skills: 다중 키워드 검색 시 포스팅 리스트 간의 교집합(AND)/합집합(OR) 비트 연산 최적화 로직 이해.
• How to Learn:
  • 1단계: 포스팅 리스트 생성: 문서 1("나는 오늘 사과를 먹었다"), 문서 2("사과는 맛있다"). 파싱 결과: 사과 → [Doc1, Doc2]. 오늘 → [Doc1]. 사용자가 '사과'를 검색하면 $O(1)$ 해시맵 탐색으로 즉시 [Doc1, Doc2] 문서 ID 리스트를 획득하는 마법을 해부합니다.
  • 2단계: 불리언 교집합(Boolean Intersection): "오늘" AND "사과". 엔진은 두 단어의 포스팅 리스트 [Doc1]과 [Doc1, Doc2]를 꺼내어 순차적으로 교집합 연산(Skip pointer 활용)을 수행. 단 몇 번의 메모리 포인터 이동만으로 교집합 [Doc1]을 도출해내는 고속 탐색을 뜯어봅니다.
• Implement: 파이썬 순수 딕셔너리를 활용한 Inverted Index 스크래치 구현. documents = { 1: "hello world", 2: "hello python", 3: "python is fun" }. 루프를 돌아 각 단어 쪼개기. index = {"hello": [1, 2], "python": [2, 3], ...} 객체 완성. 검색어 search("hello AND python") 함수 구현하여 두 배열의 Python 집합(Set) 교집합 연산으로 [2] 반환하는 엔진 코어 로직 데모.

Recommended

Core Topic 02: 지저분한 문장을 정제된 뼈대로, 분석 파이프라인 (Text Analysis Pipeline)

• Why to Learn: 검색 엔진이 똑똑하게 동의어를 찾고 대소문자 차이를 무시하는 똑똑함의 핵심이 바로 데이터를 디스크에 쓰기 직전(또는 쿼리 직전) 통과시키는 "분석기(Analyzer)" 파이프라인에 있음을 장악하기 위함입니다.
• What to Learn:
  • Concepts: 캐릭터 필터(Character Filter: HTML 제거 등), 토크나이저(Tokenizer: 공백 분리, N-Gram 등), 토큰 필터(Token Filter: Lowercase, Stemming/어간 추출, Stopword/불용어 제거).
  • Skills: 한글 형태소 분석기(Nori 등)의 동작 원리, Index Time 분석과 Search Time 분석의 일치성(Consistency).
• How to Learn:
  • 1단계: 파이프라인 흐름: 원본 "<p>Dogs are RUNNING!</p>". 1) Char Filter: HTML 태그 날림 → Dogs are RUNNING!. 2) Tokenizer: 띄어쓰기 쪼갬 → [Dogs, are, RUNNING!]. 3) Token Filter: 소문자화 + 불용어(are) 삭제 + 원형(dog, run) 복원 → [dog, run]. 이 깔끔한 단어들만 역인덱스 텀(Term) 딕셔너리에 들어가는 과정을 해부합니다.
  • 2단계: N-Gram 토크나이저 (부분 검색): 'apple'을 앞뒤로 자른 'app', 'ppl', 'ple' 도 모두 토큰으로 저장. 한글 "자동차가" 검색 시 "자동차" 형태소를 못 뽑아도 글자 단위로 N-Gram 매칭시켜 부분 검색을 가능하게 하는 트레이드오프(저장 용량 폭발 vs 완벽한 부분 매칭)를 뜯어봅니다.
• Implement: 파이썬 파이프라인 모사 함수 작성. analyzer(text) 내부에 remove_html(), split_by_space(), lowercase(), remove_stopwords(set(['a', 'the', 'is'])) 순차 호출 체인 구성. 임의의 엉망진창 영문 문장을 통과시켜 깔끔한 핵심 토큰 배열만 추출되는 전처리 로직 데모 텍스트 로깅.

Practical

Core Topic 03: 관련된 것만 최상단에, 수학적 랭킹 엔진 TF-IDF와 BM25 (Ranking Algorithms)

• Why to Learn: 100만 건의 검색 결과 중에서 유저가 진짜 원하는(관련성 높은) 문서를 상위 10개로 추려내는 검색 엔진의 두뇌, 즉 '검색 점수(Relevance Score)'를 계산하는 수학적 원리를 장악하기 위함입니다.
• What to Learn:
  • Concepts: TF (Term Frequency, 문서 내 단어 빈도), IDF (Inverse Document Frequency, 역문서 빈도), TF-IDF 계산식, Okapi BM25 알고리즘(문서 길이 정규화 및 TF 포화 방지).
  • Skills: 스코어 기반 디버깅(Elasticsearch _explain API 모방 사고), 검색 품질 튜닝.
• How to Learn:
  • 1단계: TF-IDF의 직관: 'TF(자주 나오는가?)'. A 문서에 '사과'가 5번 나오면 1번 나온 문서보다 관련성이 높다. 'IDF(희귀한 단어인가?)'. '그리고', '이것' 같은 단어는 모든 문서에 다 나오므로 중요도가 0에 가깝다. 반면 '딥러닝'은 소수 문서에만 나오므로 IDF 가중치가 급등하는 마법의 곱셈 공식을 해부합니다.
  • 2단계: BM25의 발전 (현재 표준): 1,000페이지짜리 긴 책에 '사과'가 5번 나온 것보다, 1페이지짜리 전단지에 '사과'가 5번 나온 것이 더 사과 관련 문서임. 즉 "문서 길이 대비 빈도(Length Normalization)"를 보정하고, 아무리 많이 나와도 한계치를 넘으면 점수 상승을 꺾는(Saturation) 현대 BM25 랭킹의 공학적 완성도를 뜯어봅니다.
• Implement: 파이썬 TF-IDF 계산기. 4개의 임의 문자열 리스트(문서 집합). 전체 문서 집합을 스캔하여 IDF 딕셔너리 산출. 쿼리 "빠른 자동차" 입력 시, 각 문서별 (TF * IDF) 점수 누적 합산 리스트 도출 및 내림차순(점수 높은 순) sort() 후 1위 문서부터 순위대로 출력하는 랭킹 검색기 로직 시연.

Advanced

Core Topic 04: 분할하고 합쳐라, 분산 검색과 불변 스토리지 (Lucene & Cluster Architecture)

• Why to Learn: 수십 TB의 로그 텍스트를 담기 위해, 하나의 거대한 덩어리가 아니라 여러 대의 물리적 장비(Elasticsearch Data Node)로 쪼개서 병렬 검색 후 합치는(Scatter/Gather) 빅데이터 클러스터 아키텍처를 장악하기 위해서입니다.
• What to Learn:
  • Concepts: Apache Lucene, 세그먼트(Segment, 불변 역인덱스 단위), 세그먼트 병합(Merge), Elasticsearch 아키텍처, 샤드(Primary/Replica Shard), 스캐터 앤 개더(Scatter & Gather) 검색 페이즈.
  • Skills: 읽기 부하와 쓰기 부하에 따른 적절한 샤드(Shard) 개수와 레플리카 수 설계 통찰력 확보.
• How to Learn:
  • 1단계: 불변성(Immutable)의 득과 실: Lucene 엔진 내부의 세그먼트(한번 디스크에 쓰여진 역인덱스 구조체)는 수정할 수 없습니다. 삭제나 업데이트 시 새 세그먼트를 굽거나 삭제 마커를 달 뿐입니다. 이는 캐싱(OS Page Cache) 효율을 극대화하여 램(RAM)에서 초고속 읽기를 달성하는 스토리지 계층의 천재성을 해부합니다.
  • 2단계: Scatter & Gather 페이즈: 사용자가 "에러 로그" 검색. 마스터(코디네이터) 노드는 5개의 샤드(여러 서버 장비)에 똑같은 검색 쿼리를 동시(Scatter)에 뿌립니다. 각 샤드가 자신의 역인덱스를 뒤져 로컬 Top 10을 뽑아 마스터에게 돌려줍니다. 마스터가 총 50개를 모아(Gather) 글로벌 Top 10으로 최종 정렬하는 분산 컴퓨팅의 우아한 역학을 뜯어봅니다.
• Implement: 병렬 Scatter-Gather 모사 파이썬 스크립트. 데이터 리스트 100건을 4개의 파티션 덩어리(가상 샤드 리스트)로 분할. concurrent.futures.ThreadPoolExecutor를 활용하여 4개 스레드가 각각의 파티션에서 점수(랜덤 난수 부여로 모사) Top 3개를 뽑음. 메인 스레드가 반환된 총 12개를 extend하여 다시 sort한 뒤 최종 글로벌 Top 3를 뽑아내는 마스터 노드 로직 텍스트 출력 데모.

7. Terminology

8. References

Primary

• [P1] CS2023 - Information Management (IM) - Information Retrieval
• [P5] SFIA - Enterprise IT Architecture - Search Optimization

Secondary

• [Information Retrieval: Implementing and Evaluating Search Engines] Stefan Büttcher - Inverted Index & Ranking Algorithms
• [Introduction to Information Retrieval] Christopher D. Manning - Text Analysis and TF-IDF

Industry

• [Elasticsearch Reference] - Index Modules, Text Analysis & Mapping
• [Apache Lucene Documentation] - Segment Architecture and Query Parsing

9. Final Checklist

Primary

• RDBMS의 LIKE '%키워드%' 쿼리가 B-Tree 인덱스를 무력화하는 이유와 역인덱스가 이를 극복하는 물리적 원리를 설명할 수 있는가?
• Tokenizer와 Token Filter 파이프라인을 거쳐 "Dogs are RUNNING"이 [dog, run]으로 역인덱스에 등재되는 과정을 증명할 수 있는가?

Secondary

• 다중 키워드(AND, OR) 검색 시 여러 단어의 포스팅 리스트(문서 ID 배열) 간에 일어나는 비트 논리 연산 속도를 해부할 수 있는가?
• TF-IDF 공식에서 '관사' 같은 흔한 단어의 점수가 0에 가깝게 수렴하고 희귀 단어의 점수가 치솟는 수학적 메커니즘을 묘사할 수 있는가?

Industry

• BM25 랭킹 알고리즘이 "문서 길이가 길수록 키워드가 많이 나오는 현상"을 어떻게 수식적으로 보정하는지 논증할 수 있는가?
• 불변성(Immutable)을 가진 Lucene 세그먼트가 캐싱 효율을 극대화하는 이유와, 오버샤딩이 Elasticsearch 클러스터 메모리를 붕괴시키는 과정을 분석할 수 있는가?