역색인(Inverted Index)이란? 검색엔진이 빠르게 결과를 찾는 원리

부스트키워드 팀

검색 데이터로 키워드의 검색량, 트렌드, 검색 의도를 파악하고 마케팅 의사결정을 돕는 도구 부스트키워드를 만듭니다.

검색창에 단어 하나를 입력하면 0.1초도 안 되는 시간에 수십억 개의 문서 중 관련 있는 것들이 화면에 뜹니다. 사람이 도서관에서 책을 한 권씩 넘기며 찾는다면 평생이 걸려도 못 할 일을, 검색엔진은 어떻게 순식간에 해내는 걸까요? 그 비밀의 핵심에는 역색인(Inverted Index)이라는 자료구조가 있습니다. 이 글에서는 검색엔진이 왜 역색인을 쓰는지, 그리고 실제로 어떻게 동작하는지를 예제를 통해 차근차근 살펴봅니다.

검색엔진은 왜 문서를 하나씩 뒤지지 않을까?

순차 검색(Linear Scan)의 한계

가장 단순한 방법을 먼저 생각해봅시다. 사용자가 "제주도 맛집"을 검색하면, 저장된 모든 문서를 처음부터 끝까지 읽으면서 "제주도"와 "맛집"이라는 단어가 들어 있는지 확인하는 방식입니다. 이를 순차 검색이라고 합니다.

문서가 100개 정도라면 이 방식도 크게 문제되지 않습니다. 하지만 실제 웹에는 수백억 개의 페이지가 존재합니다. 검색할 때마다 이 모든 문서를 처음부터 훑는다면, 아무리 서버가 빨라도 사용자가 체감할 수 있을 정도로 느려집니다. 검색어가 늘어날수록, 문서가 늘어날수록 걸리는 시간은 계속 늘어나기만 합니다.

색인(Index)이 필요한 이유

이 문제를 해결하는 방법은 우리가 이미 일상에서 쓰고 있습니다. 두꺼운 전공 서적 뒤에 있는 "찾아보기(색인)" 페이지를 떠올려보세요. 특정 용어가 몇 페이지에 나오는지 미리 정리해두면, 책 전체를 넘길 필요 없이 색인 페이지만 확인하면 됩니다.

검색엔진도 마찬가지입니다. 문서가 새로 들어올 때마다 "어떤 단어가 어떤 문서에 들어 있는지"를 미리 정리해두면, 실제 검색 요청이 들어왔을 때는 이 정리된 표만 확인하면 되므로 속도가 비약적으로 빨라집니다. 이렇게 검색을 빠르게 하기 위해 미리 만들어두는 자료구조를 색인이라고 부르고, 그중에서도 검색엔진이 실제로 사용하는 방식이 바로 역색인입니다.

역색인이란 무엇인가

정방향 색인(Forward Index)과 역색인(Inverted Index)의 차이

색인을 만드는 방향은 두 가지로 나눌 수 있습니다.

정방향 색인은 "문서 → 그 문서에 들어 있는 단어들" 순서로 정리한 표입니다. 예를 들어 "1번 문서에는 사과, 바나나, 과일이라는 단어가 있다"는 식입니다. 이 방식은 문서 하나의 내용을 파악하기엔 편하지만, "사과라는 단어가 들어 있는 문서를 모두 찾아라"는 질문에는 여전히 모든 문서를 뒤져야 하므로 도움이 되지 않습니다.

역색인은 이 순서를 뒤집습니다. "단어 → 그 단어가 들어 있는 문서들" 순서로 정리하는 것입니다. 즉 "사과라는 단어는 1번, 3번, 7번 문서에 들어 있다"는 식으로 미리 정리해두는 방식입니다. 이렇게 하면 검색어가 들어왔을 때 해당 단어의 목록만 바로 꺼내 보면 되므로 속도가 훨씬 빨라집니다. '색인을 뒤집었다(inverted)'는 이름도 여기서 나왔습니다.

역색인의 기본 구조: 단어(Term)와 포스팅 리스트(Postings List)

역색인은 크게 두 부분으로 이루어집니다.

첫째는 사전(Dictionary)입니다. 문서 전체에 등장하는 모든 고유한 단어를 모아놓은 목록입니다.

둘째는 포스팅 리스트(Postings List)입니다. 사전에 있는 각 단어마다 "이 단어가 등장하는 문서 번호들의 목록"을 매달아 놓은 것입니다.

정리하면 역색인은 "단어 → [이 단어가 나오는 문서 번호 목록]" 형태의 거대한 표라고 이해하면 됩니다.

간단한 예제로 이해하는 역색인 만들기

예시 문서로 역색인 직접 구성해보기

다음과 같은 짧은 문서 4개가 있다고 가정해봅시다.

• 문서 1: "제주도 흑돼지 맛집 추천"
• 문서 2: "서울 맛집 리스트"
• 문서 3: "제주도 여행 코스 추천"
• 문서 4: "부산 맛집과 여행 정보"

먼저 문서를 검색이 가능한 단위로 쪼개는 과정을 거칩니다(이를 형태소 분석 또는 토큰화라고 부릅니다). 그 결과를 바탕으로 단어별 등장 문서를 정리하면 다음과 같은 역색인이 만들어집니다.

• 제주도 → [문서 1, 문서 3]
• 흑돼지 → [문서 1]
• 맛집 → [문서 1, 문서 2, 문서 4]
• 추천 → [문서 1, 문서 3]
• 서울 → [문서 2]
• 리스트 → [문서 2]
• 여행 → [문서 3, 문서 4]
• 코스 → [문서 3]
• 부산 → [문서 4]
• 정보 → [문서 4]

이제 이 표만 있으면 원본 문서를 다시 들여다보지 않아도 어떤 단어가 어느 문서에 있는지 바로 알 수 있습니다.

검색어가 들어왔을 때 매칭되는 과정

사용자가 "맛집"을 검색했다고 해봅시다. 검색엔진은 문서 1~4를 순서대로 읽는 대신, 역색인 표에서 "맛집" 항목만 바로 찾습니다. 그러면 [문서 1, 문서 2, 문서 4]라는 답이 즉시 나옵니다. 문서 3은 애초에 확인할 필요조차 없습니다. 문서가 4개가 아니라 4억 개였더라도 걸리는 시간은 거의 똑같습니다. 이것이 역색인이 만들어내는 속도의 비밀입니다.

여러 단어를 검색할 때: AND 검색은 어떻게 처리될까

두 단어를 동시에 만족하는 문서 찾기

실제 검색에서는 단어 하나만 입력하는 경우보다 여러 단어를 함께 입력하는 경우가 훨씬 많습니다. "제주도 맛집"처럼 두 단어를 모두 포함하는 문서를 찾고 싶을 때, 검색엔진은 각 단어의 포스팅 리스트를 각각 꺼낸 뒤 두 목록에 공통으로 들어 있는 문서만 골라냅니다.

위 예제에서 "제주도"의 목록은 [문서 1, 문서 3]이고 "맛집"의 목록은 [문서 1, 문서 2, 문서 4]입니다. 두 목록에 공통으로 들어 있는 문서는 문서 1뿐이므로, "제주도 맛집"이라는 검색어에는 문서 1이 결과로 나오게 됩니다.

포스팅 리스트를 문서 번호 순으로 정렬해두는 이유

실제 검색엔진에서는 포스팅 리스트를 문서 번호 순서대로 미리 정렬해둡니다. 두 목록이 이미 정렬되어 있으면, 마치 두 줄로 세워진 사람들의 번호표를 비교하듯 양쪽을 한 번씩만 훑으면서 공통된 번호를 매우 빠르게 찾아낼 수 있기 때문입니다. 이렇게 검색어의 개수가 늘어나도 처리 속도가 크게 느려지지 않도록 설계되어 있다는 점이 역색인 구조의 큰 장점입니다.

실제 검색엔진에서는 어떻게 응용될까

순위 매기기(Ranking)와의 관계

지금까지 살펴본 과정은 "해당 단어가 들어 있는 문서를 찾는" 단계에 해당합니다. 하지만 구글이나 네이버 같은 실제 검색엔진은 여기서 한 걸음 더 나아가, 찾아낸 문서 중 어떤 것이 더 사용자의 의도와 가까운지 순위를 매깁니다. 이때는 단어가 문서 안에 얼마나 자주 등장하는지, 얼마나 중요한 위치(제목, 첫 문단 등)에 있는지, 다른 사이트로부터 얼마나 많이 링크되었는지 등 다양한 정보를 함께 고려합니다. 역색인은 이러한 순위 계산에 필요한 후보 문서를 빠르게 추려내는 첫 관문 역할을 합니다.

대규모 데이터에서의 색인 압축과 분산 처리

전 세계 웹페이지를 대상으로 역색인을 만들면 그 크기는 상상을 초월합니다. 그래서 실제 검색엔진은 포스팅 리스트를 압축된 형태로 저장하고, 하나의 서버가 아니라 수많은 서버에 색인을 나누어 저장한 뒤 병렬로 검색을 처리합니다. 또한 새로운 웹페이지가 계속 생겨나고 기존 페이지가 수정되기 때문에, 역색인 역시 실시간 또는 주기적으로 갱신하는 구조를 함께 갖추고 있습니다.

정리하며: 역색인이 중요한 이유

역색인은 "단어를 기준으로 문서를 미리 정리해둔다"는 단순한 아이디어에서 출발하지만, 이 발상 하나가 오늘날 우리가 당연하게 여기는 빠른 검색 경험을 가능하게 만든 핵심 기술입니다. 문서를 하나씩 읽는 대신 미리 만들어둔 표를 참조하는 방식, 그리고 정렬된 목록을 빠르게 비교하는 방식이 결합되어, 방대한 양의 데이터 속에서도 원하는 정보를 즉시 찾아낼 수 있게 해줍니다. 검색창 뒤에서 어떤 일이 벌어지는지 알고 나면, 평소 무심코 쓰던 검색이 조금은 다르게 보일 것입니다.