[자료구조] 색인(Index), 역색인(Inverted Index)

Elasticsearch의 대표 특징으로 불리는 역색인에 대해 알아보려고 한다.

 

https://www.researchgate.net/figure/The-geographic-scopes-inverted-index-The-inverted-index-is-used-for-fast-document_fig3_266863129

역색인(Inverted Index)에 앞서, 색인(Index)에 대해 알아보자.

색인(Index)이란?

위의 사진에서 Forward Index이다.

• 문서에서 키워드를 찾아 보기 쉽도록 정렬 및 나열한 목록이다.
• 특정한 데이터가 어느 위치에 있는지 미리 저장해두어, 검색 시에 빠른 속도로 찾을 수 있도록 한다.
• 키워드를 토대로 데이터를 찾을 경우 마지막 데이터까지 확인을 해야할 수 있어 시간이 오래 걸릴 수 있다.

역색인(Inverted Index)이란?

위의 사진에서 Inverted Index이다.

• 키워드를 통해 문서를 찾아내는 방식이다.
• 데이터를 색인하는 과정에서 찾고자 하는 키워드를 기준으로 위치를 저장해두어 속도를 개선한 구조이다.
• 이는 문서에 번호가 지정된 것이 아니라, 키워드마다 어느 문서에 들어가 있는지 기록한다.
• 역색인 구조를 생성해두면, 키워드 색인을 통해 검색이 매우 빠르다.

인덱스와 역인덱스의 차이점

인덱스와 역인덱스의 차이점은 방향성(directionality)이다.

인덱스(Forward Index)는 document의 ID(번호)와 내용을 매핑한다. 인덱스를 통해 2번 문서는 Europe, 3번 문서는 France 내용이란 걸 알 수 있다.

반면 역인덱스(Inverted Index)의 경우 어떤 내용이 몇 번 문서에 담겨있는지를 보여준다. 역인덱스를 통해 Europe이 1, 2, 7번 문서에 있다는 걸 알 수 있다.

 

 

다음은 Elastic Search 를 중심으로 다루는 설명을 하는 내용을 작성할 예정이다.