공간 인덱스(Spatial Index)를 구성하는 작동할까?

인덱스(Index)는 데이터베이스 검색 속도를 향상시키기 위해 사용되며 자료구조로 구성됩니다. 인덱스를 사용하면 보다 빠르게 행을 찾고 검색할 수 있어 SELECT문 수행에 장점이 있습니다. 그러나 INSERT, UPDATE, DELETE 쿼리 수행시에는 추가 연산이 이뤄지기 때문에 오버헤드가 발생될 수 있으며 추가적인 물리적 저장 공간이 필요하게 됩니다.

R-tree Hierarchy

풀 테이블 스캔(full table scan)

인덱스가 지정되지 않은 테이블을 검색할 때는 풀 테이블 스캔이라 불리는 검색 방법을 사용합니다. 테이블에 저장된 모든 값을 처음부터 차례로 조회하는 아주 단순한 검색 방법인데, 1000개의 row가 있다면 최대 1000번 값을 비교합니다.

이진 탐색(binary search)

차례로 나열된 집합에 대해 유효한 검색 방법입니다. 처음부터 순서대로 조사하는 것이 아닌 집합을 반으로 나누어 조사하는 검색방법입니다.

이진 트리(binary tree)

이진 탐색은 고속으로 검색할 수 있는 탐색 방법이지만 데이터가 미리 정렬되어 있어야 합니다. 하지만 테이블 내의 행을 언제나 정렬된 상태로 두는 것은 힘든 작업입니다. 일반적으로 테이블에 인덱스를 작성하면 테이블 데이터와 별개로 인덱스용 데이터가 만들어집니다. 이때 이진 트리 데이터 구조로 작성되는데 아래와 같은 구조를 가집니다.

일반적인 DBMS에서 가장 많이 사용되고 있는 Index 알고리즘은 B-tree 입니다. PostgreSQL에서는 B-tree, Hash, GiST, SP-GiST, GIN,  BRIN과 같은 다양한 인덱스를 제공합니다. 서로 다른 유형의 쿼리에 가장 적합한 알고리즘을 사용합니다. 인덱스 알고리즘 별 주요 특징은 다음과 같습니다.

• B-tree:
  • 기본 인덱스 유형으로, 등호(=), 부등호(>, <, BETWEEN) 연산에 가장 적합
  • 대부분의 일반적인 검색에서 안정적인 성능을 제공
• GiST (Generalized Search Tree)
  • 범용 인덱스 프레임워크로, 공간 데이터나 유사도 검색 등 사용자 정의 정렬 기준이 필요한 경우 유용
  • PostGIS의 공간 인덱스에서 사용됨
• SP-GiST (Space-Partitioned GiST)
  • GiST와 유사하나, 공간 분할 기반의 트리 구조를 사용해 보다 고르게 분포된 데이터 구조에서 사용됨
  • 트라이(trie), k-d 트리, 쿼드트리 등의 구조에 적합합니다.
• Hash
  • 해시 기반으로 = 연산에 특화되어 있으며, 해시 조인이나 해시 분배 키와 같은 경우에 유용함
  • 하지만 PostgreSQL 10 이전에는 WAL(Write-Ahead Logging)이 지원되지 않아 복제 환경에서 제약이 있음
• GIN (Generalized Inverted Index)
  • 다대다 관계나 배열, JSON, full-text search 같은 복잡한 구성요소 검색에 유리함
  • 여러 값을 가진 열에서 각각의 요소를 빠르게 찾을 수 있음
• BRIN (Block Range INdexes)
  • 대용량 테이블에서 블록 단위로 요약된 정보를 저장하여 범위 조건 검색에 특화됨
  • 예를 들어 시간순으로 정렬된 로그 데이터에서 범위 검색 성능이 뛰어남

 

https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees

Hilbert R-tree - Wikipedia