ElasticSearch는 Inverted Index를 사용기에, 검색 속도가 엄청 빠르다.
다만, TEXT 타입 필드는 full-text search가 되지만, Keyword 타입은 exact search만 된다.
기본 지식
용어 정의
Foward Index의 Big-O = O(logN)
Inverted Index의 Big-O = O(1)
용어 정의
이야기에 앞서, 인덱스란 무엇인가?에 대한 기초 정의가 필요하다.
목적 : 데이터 검색 속도를 향상 시키기 위한 자료 구조
비용 : 추가적인 쓰기 작업 및 저장 공간 소모
인덱스는 검색 성능 향상을 위해 쓰이는 자료 구조로서
사용하는 데이터베이스에 따라 다양한 자료구조의 인덱스를 사용할 것이다.
(e.g. B-Tree, R-Tree, T-Tree)
인덱스는 인덱스 키의 방향성에 따라서 2가지로 구분할 수 있다.
Foward Index : 문서에 어떤 단어가 들어가는지 (문서 ID → 단어)
Inverted Index : 각 단어가 어떤 문서에 들어가는지 (단어 → 문서 ID)
다음과 같이 문서 2개가 주어질때, 각 인덱스는 데이터를 어떻게 저장하게 될까?
문서 1 : "apple banana"
문서 2 : "banana orange"두 인덱스에 저장되는 데이터 예시를 보면 명확하게 이해할 수 있다.
Foward Index
문서 1 → [apple, banana]
문서 2 → [banana, orange]
Inverted Index
apple → [문서 1]
banana → [문서 1, 문서 2]
orange → [문서 2]
즉,
특정 단어에 대한 검색은 Inverted Index가 월등히 빠를 것이다.
(e.g. Foward Index O(logN) < (fast) < Inverted Index O(1))
Foward Index의 Big-O = O(logN)
Foward Index 중 가장 대표적인 B-Tree Index의 경우, O(logN)이다.
문서가 늘어나면 검색이 급격히 느려지다가, 일정 구간이 넘어가면 더이상 (크게) 느려지지 않으며, 오직 logN 번의 검색만 필요하다.
위 설명을 들어도 왜 O(logN)인지 크게 공감이 되지 않는 건 당연하다.
Foward Index 중인 하나인 B-Tree 구조를 통해서 단계적으로 생각해보자.
B-Tree에서 깊이를 h, 자식의 수를 M이라고 하고 균등 트리라고 가정해보면,
깊이 h에서 총 노드 수는 M^h(M의 h 거듭제곱)일 것입니다.
저장 관점에서 데이터 N개를 저장하기 위한 최소 공간은 M^h ≥ N 일 것이다.
즉, 저장하기 위해 탐색해야하는 최소 높이는 h ≥ log (m) N 임을 알 수 있다.
N 번째에 저장된 대상을 찾기 위해서도 최악의 경우 log (m) N이 필요할 것이다.
이때 일반적으로 아랫첨자(m)을 생략하므로 log N의 검색 복잡도를 가지게 된다.
Inverted Index의 Big-O = O(1)
Inverted Index의 검색 성능이 O(1)인 것은 너무 직관적이다.
문서가 수백만개가 되더라도 banana 라는 단어가 어떤 문서에 있는지 이미 정의되어 있기 때문에, 오직 1번의 검색만 필요하다.
ElasticSearch
위 내용을 전부 이해했다면 아래 내용을 손쉽게 이해할 수 있을 것이다.
Keyword Type은 입력된 문자열 전체를 하나의 토큰으로 하여 Inverted Index를 만든다.
TEXT Type은 문자열을 여러 개의 토큰으로 나눠서 Inverted Index를 만들다.
더 자세한 내용은 아래 문서 1, 2를 가볍게 읽으면 더 정확하게 이해할 수 있을 것이다.
