역색인(Inverted Index) 구조

엘라스틱서치에 대해 공부하던 중, 검색 속도가 빠른 이유 중 하나로 역색인 구조라는 것을 알게 되었고 이에 대해 정리해 보았다.

 

색인과 역색인

먼저 색인 구조는 문서의 위치에 대한 인덱스를 만들어 빠르게 문서에 접근하는 방법으로 문서를 중심으로 정보를 찾는다. 역색인 구조는 이와 반대로 단어로부터 문서를 찾는 형태이다.

일상생활에서 볼 수 있는 예시로는 책 맨 앞의 차례(목차)와 맨 뒤의 찾아보기(둘러보기) 페이지가 있다.

왼쪽의 차례와 같이 문서에서 키워드를 찾아보기 쉽도록 나열된 형태가 색인 구조, 오른쪽의 찾아보기 페이지처럼 문서에서 키워드를 통해 문서를 찾는 형태를 역색인 구조라고 할 수 있다.

 

역색인 구조가 검색 성능이 좋은 이유

그렇다면 왜 역색인 구조가 색인 구조보다 검색 성능이 좋을까?

다음과 같은 색인 구조와 역색인 구조에서 라떼라는 단어라는 단어를 검색해 문서를 찾는다고 가정해보자. 

색인 구조 예 / 역색인 구조 예

색인 구조에서 검색할 경우

색인 구조에서의 검색

색인 구조에서는 각 문서에 어떤 단어가 포함되어 있는지 기록하는 형식이다. 따라서 검색하기 위해선 모든 문서의 내용을 조회하며 찾는 단어가 있는지 확인해야 한다. 즉 전체 텍스트를 하나하나 읽어야 하므로 속도가 느리다. 만약 문서가 늘어날 경우 읽어야 하는 대상이 늘어나기 때문에 검색 속도는 더 느려진다.

역색인 구조에서 검색할 경우

역색인 구조에서의 검색

반면 역색인 구조에서는 단어를 기준으로 어떤 문서에 해당 단어가 포함되어 있는지를 바로 확인할 수 있다. 위 예시처럼 추출된 단어(Term)를 기준으로 연결된 문서 ID 리스트만 조회해 바로 훨씬 빠르게 검색이 가능하다. 만약 문서가 늘어난다고 해도 읽을 대상이 늘어나는 것이 아닌 연결된 리스트에 문서 ID 값이 추가되는 것이기 때문에 크게 느려지지 않는다.

 

정리

이렇게 역색인 구조는 단어에서부터 문서를 연결해 주기 때문에 빠른 검색 속도를 제공한다. 엘라스틱서치는 이러한 구조적 강점을 바탕으로 검색 분야에서 활용되고 있다.

빠른 검색의 구조적인 이유를 알게 되었고 중요한 개념임을 느꼈다.