인버티드 인덱스(Inverted Index)와 포워드 인덱스(Forward Index)는 하나 또는 여러 개의 문서에서 텍스트를 검색할 때 사용되는 대표적인 데이터 구조입니다. 두 인덱스는 같은 목적을 가지지만, 데이터를 매핑하는 방향이 정반대라는 점에서 큰 차이를 보입니다.
인버티드 인덱스(Inverted Index)란?
인버티드 인덱스는 단어(word)를 인덱스(key)로 저장하고, 해당 단어가 등장하는 문서 이름을 매핑된 참조 값(value)으로 저장하는 방식입니다. 즉, '어떤 단어가 어떤 문서에 있는가'를 빠르게 찾을 수 있도록 설계된 구조입니다.
포워드 인덱스(Forward Index)란?
포워드 인덱스는 이와 반대로 문서 이름을 인덱스(key)로 저장하고, 그 문서에 포함된 단어들을 매핑된 참조 값(value)으로 저장하는 방식입니다. 즉, '특정 문서에 어떤 단어들이 있는가'를 파악하는 데 적합한 구조입니다.
아래 표는 인버티드 인덱스와 포워드 인덱스의 주요 차이점을 항목별로 정리한 것입니다.
| 번호 | 구분 | 인버티드 인덱스 | 포워드 인덱스 |
|---|---|---|---|
| 1 | 매핑 방식 | 단어를 인덱스로 저장하고, 문서 이름을 매핑된 참조 값으로 저장합니다. | 문서 이름을 인덱스로 저장하고, 단어를 매핑된 참조 값으로 저장합니다. |
| 2 | 색인(Index) 생성 과정 |
|
|
| 3 | 색인 속도 | 색인을 만들기 전에 각 단어를 일일이 확인해야 하므로 색인 속도가 느립니다. | 키워드를 발견하는 즉시 추가하면 되므로 색인 속도가 빠릅니다. |
| 4 | 검색 속도 | 단어에서 문서로 바로 조회할 수 있어 검색 속도가 매우 빠릩니다. | 원하는 단어를 찾으려면 모든 문서를 탐색해야 하므로 검색 속도가 느립니다. |
| 5 | 예시 | Word Documents ------------------------- Welcome doc1 Hello doc1, doc3 Hi doc2 ------------------------- | Word Documents ------------------------- doc1 Welcome, Hello doc2 Hi doc3 Hello ------------------------- |
| 6 | 중복 여부 | 동일한 키워드가 인덱스에 중복 저장되지 않습니다. | 'Hello'처럼 동일한 키워드가 여러 문서의 인덱스에 중복으로 존재할 수 있습니다. |
| 7 | 실생활 예시 | 책 끝부분의 찾아보기(색인), 역방향 조회(Reverse Lookup) | 책 앞부분의 목차(Table of Contents), DNS 조회(DNS Lookup) |
정리
두 인덱스의 핵심 차이는 데이터를 바라보는 방향입니다. 포워드 인덱스는 문서 중심이라 색인은 빠르지만 검색이 느리고, 인버티드 인덱스는 단어 중심이라 색인은 느리지만 검색이 매우 빠릅니다. 이러한 특성 때문에 구글과 같은 검색 엔진은 방대한 문서에서 키워드 기반 검색을 신속하게 수행하기 위해 인버티드 인덱스를 활용합니다.