[Elasticsearch] 엘라스틱 서치 역인덱스(Elasticsearch inverted index) - 컴도리돌이

---

 

 

이번 글에서는 엘라스틱서치(Elasticsearch)에서 데이터를 어떤 방식으로 저장하는지 알아보겠습니다.

오늘 글의 주제는 역인덱스(inverted index) 구조에 대해서 알아보겠습니다. 

---

 

일반적인 RDBMS에서 텍스트 형식으로 이루어진 컬럼에서, 특정 단어가 포함되어 있는지 확인하기 위해서는 다음과 같이 패턴을 검색할 수 있습니다. 

 

SELECT *
FROM test_table
WHERE test_columns LIKE '%quokka%'

 

보통 와일드카드 '%'를 이용하여 특정 단어로 시작한, 끝 맺히는, 포함되어 있는 데이터를 조회할 때, LIKE 연산과 '%'을 사용하여 패턴 검색을 할 것입니다. 

 

1. the cute white quokka
2. the cute brown quokka
3. the cute white quokka jumps over the cute brown quokka
4. the brown quokka
5. the cute dog

 

전통적인 RDBMS에서는 특정 필드를 효율적으로 조회하기 위해서 인덱스를 사용하여 검색 속도를 개선합니다. 하지만 위에 같이 특정 단어가 포함된 데이터를 찾기 위해서 와일드카드 '%'을 양쪽에 붙여서 조회를 하면 인덱스가 걸리지 않는 상태로 조회를 하기 때문에 검색 속도가 매우 느립니다.

 

위의 예시로 'quokka'라는 텍스트를 포함한 행을 가져오려고 하면, 모든 데이터를 확인하고 해당 텍스트가 포함되어 있는지 검사를 해야 합니다. 즉 모든 테이블을 Full scan을 해야 합니다.

반응형

---

Elasticsearch inverted index

 

엘라스틱 서치(Elastic Search)에서 역인덱스(Inverted index)는 데이터를 효율적으로 검색하기 위해 사용되는 개념 중 하나입니다. 역인덱스에서는 전통적인 RDBMS의 인덱스 개념과 정반대입니다. 일반적인 인덱스에서는 문서의 실제 내용이 색인되어 저장되지만, 역인덱스는 각 단어를 키(key)로 사용하고, 해당 단어가 어떤 문서에서 발견되어 있는지에 대한 정보를 값(value)으로 저장합니다.  이러한 방식으로 특정 단어를 검색할 때, 해당 단어가 포함된 문서를 빠르게 찾을 수 있습니다. 

 

1. The cute white quokka
2. The cute brown quokka
3. The cuting white quokka jumps over the cute brown quokka
4. The brown quokka
5. The cute dog

 

위에 동일한 예시를 사용하여 역인덱스는 데이터를 어떻게 저장할까요? 위에 텍스트를 여러 개의 키워드로 쪼갭니다. 그리고 쪼갠 키워드는 자기 자신이 등장한 문서를 가리킵니다. 

 

Term	document	Term	document
the	1	cute	1, 2, 3, 5
white	1, 3	brown	2, 3
jumps	3	over	3
quokka	1, 2, 3, 4	dog	5
The	1, 2, 3, 4, 5	cuting	3

 

문서 1 ~ 5의 내용을 일반적인 RDBMS에 저장하고, LIKE 연산을 통해 패턴 매칭하여 데이터를 탐색한다고 했을 때, 'dog'라는 단어가 포함된 문서를 검색해 보겠습니다. 역인덱스에서 바로 'dog'을 찾아보면 문서 5를 가리키는 것을 확인할 수 있습니다. 마치 해시 테이블을 사용하는 것처럼 시간 복잡도가 거의 O(1)에 수렴합니다. 

 

Elasticsearch는 데이터가 늘어나도 찾아야 할 행이 늘지 않고, Term이 가리키는 document id값이 배열에 추가되는 것이기 때문에 빠른 속도로 특정 단어를 탐색할 수 있습니다. 이런 역인덱스를 데이터가 저장되는 과정에서 만들기 때문에 저장이 아닌 색인을 한다고 표현합니다.

---

Indexing for Beginners, Part 3

ElasticSearch [데이터 색인, 텍스트 분석, 인덱스]