1. 인덱스란?

인덱스는 데이터베이스에서 테이블의 특정 열에 대한 검색을 빠르게 수행하기 위해 사용되는 자료구조입니다. 인덱스를 사용하면 테이블에 있는 모든 데이터를 순차적으로 검색하지 않고도 원하는 데이터를 빠르게 찾을 수 있습니다 테이블의 특정 컬럼에 인덱스를 생성하면 해당 컬럼의 데이터를 정렬하고 별도의 메모리 공간에 데이터의 물리적 주소를 함께 저장합니다. 이때 컬럼 값과 물리적 주소는 (key, value) 쌍으로 저장되고, 데이터 검색 시 인덱스를 통해 데이터를 빠르게 조회할 수 있습니다.

2. PostgreSQL 인덱스 자료구조 및 동작 방식

인덱스는 여러 자료구조를 이용해 구현할 수 있습니다. PostgreSQL에서는 기본적으로 B-Tree 자료구조를 사용합니다. 만약 다른 자료구조를 사용하고자 하면 명시적으로 설정해야 합니다.

B-Tree 인덱스 구조

PostgreSQL에서 사용하는 B-Tree 인덱스는 B+Tree의 특징을 많이 차용했으며 다음과 같은 특징을 가지고 있습니다.

• 균형 잡힌 다진 트리

  • 일반적인 이진 트리는 각 노드가 최대 2개의 자식 노드만 가지지만, B-Tree는 각 노드가 최대 M개의 자식을 가질 수 있습니다.

• 리프 노드에 데이터 저장

  • B+Tree의 특징을 차용한 것으로, 리프 노드에 키와 해당 키에 대한 포인터(데이터의 위치 정보)가 저장됩니다.

• 리프 노드 간 연결

  • 리프 노드들은 서로 연결되어 있어 범위 검색 시 데이터를 찾지 못해 root node로 다시 이동하지 않고 효율적으로 데이터를 검색할 수 있습니다.

• 키 정렬

  • 모든 키는 정렬된 상태로 저장되어 정렬 작업(ORDER BY)은 매우 빠르게 수행됩니다.

• 어떤 값과 정확히 일치하는 데이터를 찾을 때와 특정 값보다 크다 작다와 같이 범위로 찾을 때 모두 사용할 수 있습니다.

1

                            <      <=       =       >=      >

구조

• Root Node (루트 노드)
  • 트리의 최상위 노드
  • 하위 노드들의 범위를 나타내는 키 값들을 포함
• Non-leaf Node (중간 노드)
  • 루트와 리프 노드 사이에 위치
  • 자식 노드들의 범위를 나타내는 키 값들을 포함
• Leaf Node (리프 노드)
  • 실제 데이터가 있는 페이지를 가리키는 포인터를 포함
  • 정렬된 순서로 데이터를 저장
• 시간복잡도: O(logN)

Hash Index

PostgreSQL의 Hash 인덱스는 데이터를 해시 함수로 변환하여 데이터를 효율적으로 검색하는 데 사용됩니다. 이 인덱스는 = 연산자와 같은 동등 비교에 최적화되어 있으며 특정 키에 대한 빠른 검색을 제공합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

              [hash(10)]              <- Bucket 1
                  |
              [10] -> Data Pointer    <- Actual data pointer

              [hash(20)]              <- Bucket 2
                  |
              [20] -> Data Pointer    <- Actual data pointer

              [hash(30)]              <- Bucket 3
                  |
              [30] -> Data Pointer    <- Actual data pointer

• 빠른 동등 비교
  • = 연산자를 사용하는 동등 비교에 대해 최적화되어 있으며, 키에 대한 빠른 검색 성능을 제공합니다.
• 범위 검색에는 비효율적입니다.
• 여러 키가 동일한 해시 값을 가질 경우 이를 처리하기 위한 추가적인 처리 비용이 발생할 수 있습니다.
• 해시 인덱스는 데이터를 정렬된 순서로 저장하지 않기 때문에, 범위 기반의 순차 검색에 적합하지 않습니다.
• 시간복잡도: O(1)

3. Seq Scan과 Index Scan

Seq Scan (Sequential Scan)

• 테이블의 모든 행을 순차적으로 스캔하여 조건에 맞는 데이터를 찾는 방식
• 시간 복잡도: O(N)
  • 행의 개수를 N이라고 하면, 모든 행을 읽어야 하므로 시간 복잡도는 O(N)
• 공간 복잡도: O(1)
  • 추가적인 저장 공간이 필요하지 않음.

Index Scan

• 인덱스를 사용하여 검색 조건에 맞는 데이터 위치를 찾고, 필요한 데이터만 읽는 방식
• 시간복잡도: B-Tree(기본 자료구조)일 경우 O(logN)
  • 행의 개수를 N이라고 하면 O(logN)
• 공간복잡도: O(N)
  • 공간 복잡도는 데이터 크기와 노드의 개수 비례하여 O(N)

비교

데이터가 많을수록 O(N)과 O(logN)의 성능 차이가 커지기 때문에, 데이터가 많고 특정 데이터를 자주 검색해야 할 경우에는 인덱스를 사용하는 것이 효과적입니다.

4. 인덱스 장단점

장점

• 검색 성능 향상
  • WHERE, ORDER BY, GROUP BY 절에 자주 사용되는 열에서 인덱스를 사용하면, Seq Scan에 비해 훨씬 빠른 검색 성능을 얻을 수 있습니다.
• 데이터 정렬
  • B-Tree 인덱스를 사용하면 데이터가 정렬된 상태로 저장되어 추가적인 정렬 작업 없이 효율적으로 처리할 수 있습니다.

단점

• 쓰기 성능 저하
  • 데이터를 INSERT, UPDATE, DELETE할 때마다 인덱스도 업데이트되어야 하므로 쓰기 작업의 성능이 저하될 수 있습니다.
• 추가 저장 공간 사용
  • 인덱스는 테이블 외부에 별도의 저장 공간을 차지하므로 디스크 공간을 추가로 차지하게 됩니다.

5. 인덱스를 효율적으로 사용하는 방법

• 쿼리에서 자주 사용되는 조건에 인덱스 추가
  • WHERE, JOIN, ORDER BY, GROUP BY 등에서 자주 사용되는 열에 인덱스를 생성
• 자주 변경되는 열에 인덱스는 피하기
  • 생성, 삭제, 업데이트가 빈번하게 일어나는 열에 인덱스를 설정하면, 인덱스 갱신이 자주 발생해 오히려 성능이 저하될 수 있습니다. (시간 복잡도: O(logN))
• 카디널리티에 기반한 인덱싱 전략

카디널리티란? (Cardinality)

테이블에 포함된 행(row)의 수를 의미합니다.

• 높은 카디널리티: 고유한 값이 많은 경우(예: 이메일 주소) 인덱스를 생성할 때 유용합니다. 높은 카디널리티의 열은 검색 성능을 향상시키는 데 기여할 수 있습니다.
• 낮은 카디널리티: 고유한 값이 적은 경우(예: 성별) 인덱스의 효율성이 떨어질 수 있습니다. 이러한 경우 인덱스를 생성하는 것이 오히려 성능 저하를 초래할 수 있습니다.