Inverted Index(역색인)

Inverted Index(역색인)

주어진 키워드에 대해서 해당 키워드가 포함된 데이터의 위치를 추적해내는 것을 의미한다. 쉽게 말해서 데이터베이스 내의 데이터들로부터 키워드를 뽑아내는 과정이라면, 역색인은 특정 키워드에대해 요청(Request)이 들어왔을때 해당 키워드들을 포함하고 있는 데이터들을 찾아내는 것을 의미한다. 색인(Index)을 책 맨 앞의 목차라고 한다면, 역색인(Inverted Index)은 책 맨 뒷 부분의 색인이라고 할 수 있다. 이러한 역색인은 검색 엔진에 있어 성능향상을 위해 필수적으로 활용되는 부문이다. 검색 엔진(Elasticsearch, Apache Solr 등)에서 각 문장의 단어(term 또는 token이라고도 한다)를 분리하고 정렬한 다음, 각 단어가 어느 document에 있는지 표시하는 방식을 통해 Inverted Index을 활용하고 이를 통해 검색 성능을 향상시킨다. 

 

검색 엔진에서의 Inverted Index 

우리가 fox라는 키워드를 통해 검색을 한다고 가정해보자. 일반적으로 위의 테이블 데이터에서 한 줄씩 like '%fox' 검색을 통해 데이터를 검색한다. 전통적인 RDBMS 에서는 like 검색을 사용하기 때문에 데이터가 늘어날수록 검색해야 할 대상이 늘어나 시간도 오래 걸리고, row 안의 내용을 모두 읽어야 하기 때문에 기본적으로 속도가 느리다. 그러나 검색 엔진(Elasticsearch, Apache Solr 등)은 데이터를 저장할 때 다음과 같이 역 인덱스(inverted index)라는 구조를 만들어 저장한다.

이 역 인덱스는 앞서 말한 책의 맨 뒤에 색인과 유사하다. 검색 엔진에서는 추출된 각 키워드를 텀(term) 이라고 부른다. 이렇게 역 인덱스가 있으면 fox를 포함하고 있는 document들의 id를 바로 얻어올 수 있다.

검색 엔진은 데이터가 늘어나도 찾아가야 할 행이 늘어나는 것이 아니라 Inverted Index역 인덱스가 가리키는 id의 배열값이 추가되는 것 뿐이기 때문에 큰 속도의 저하 없이 빠른 속도로 검색이 가능하다. 이런 역 인덱스를 데이터가 저장되는 과정에서 만들기 때문에 검색 엔진은 데이터를 입력할 때 저장이 아닌 색인을 한다고 표현하게 되는 것이다.

 

출처: Elastic 가이드, 구르미 그린 데이터(개인 블로그)