인덱스 동작 원리: 데이터 구조와 검색 알고리즘

오늘은 인덱스의 아키텍처를 좀 더 깊게 파고들어 볼 거야. 인덱스가 실제로 내부에서 어떻게 동작하는지 알아보자. 인덱스 구조를 알면 쿼리가 왜 빨라지는지, 그리고 다양한 상황에서 어떤 인덱스를 골라야 할지 감이 잡히거든.

인덱스 구조라고 하면, 인덱스 내부에서 데이터가 어떻게 정렬되고 저장되는지에 대한 얘기야. 예를 들어, 서류가 잔뜩 들어있는 캐비닛을 생각해봐. 서류가 그냥 한데 쌓여 있으면 원하는 걸 찾기 힘들지. 근데 알파벳 순서로 정리되어 있으면 훨씬 빠르게 찾을 수 있어. 인덱스도 딱 그런 식이야. 데이터를 잘 정렬해서 원하는 정보를 최대한 빠르게 찾을 수 있게 해주는 거지.

B-TREE 인덱스 구조

B-TREE (balanced tree — 균형 트리)는 PostgreSQL에서 가장 많이 쓰이는 인덱스 타입이야. 쉽게 말해서, 트리 구조로 데이터가 노드에 저장되고, 검색은 트리의 루트에서 리프까지 내려가면서 진행돼.

이렇게 생겼어:

         루트
          /       |       \
      노드 1    노드 2    노드 3
     /   \       |       /   \
리프1 리프2   리프3  리프4 리프5

각 노드는 검색을 안내하는 키 값을 가지고 있어. 예를 들어, 루트 노드에 [10, 20, 30] 값이 있으면:

• 10보다 작은 모든 데이터는 리프1에 있어.
• 10과 20 사이 데이터는 리프2에, 이런 식으로 쭉 가는 거지.

B-TREE 인덱스의 장점:

• 데이터 검색이 빠름: 검색 복잡도가 O(log n)이라서 선형 검색보다 훨씬 빨라.
• 범위 검색(예: 10과 50 사이 값 찾기)에 적합해.

예시: 예를 들어 students 테이블에 age 컬럼이 있다고 해보자. 이 컬럼에 B-TREE 인덱스를 만들면:

CREATE INDEX age_idx ON students (age);

PostgreSQL이 나이 값으로 균형 트리를 만들어서, 특정 나이나 나이 범위에 해당하는 학생을 빠르게 찾을 수 있게 해줘.

B-TREE에서 검색 알고리즘

쿼리를 실행하면, PostgreSQL은 인덱스를 이렇게 써서 데이터를 찾아:

1. 검색 키(예: 나이 25)를 정함.
2. 루트 노드부터 시작함.
3. 키를 노드의 값 범위와 비교해서 해당 자식 노드로 이동함.
4. 리프에 도달할 때까지 3번을 반복함.
5. 리프에서 키에 해당하는 데이터를 반환함.

쿼리 예시:

SELECT * FROM students WHERE age = 25;

인덱스 덕분에 스캔해야 하는 데이터 양이 확 줄어서, 검색이 엄청 빨라져.

검색 알고리즘과 성능

인덱스는 스캔해야 할 행(row) 수를 줄여서 검색을 빠르게 해줘. 인덱스가 없으면 PostgreSQL은 테이블 전체를 다 읽어야 해(이걸 순차 스캔 또는 Seq Scan이라고 해). 인덱스가 있으면 인덱스 스캔(Index Scan)이 일어나서 훨씬 빨라.

순차 스캔과 인덱스 스캔 비교

• 순차 스캔 (Seq Scan):

  • PostgreSQL이 테이블의 모든 행을 읽으면서 조건을 체크하고, 맞는 행만 반환해.
  • 인덱스가 없거나, 쿼리가 거의 모든 행을 읽어야 할 때 사용돼.

• 인덱스 스캔 (Index Scan):

  • PostgreSQL이 인덱스를 써서 해당하는 행만 찾고, 그 행만 테이블에서 읽어와.
  • 큰 테이블에서 일부 데이터만 찾을 때 훨씬 빨라.

예시: 인덱스 없이 나이 검색

SELECT * FROM students WHERE age = 25;

이렇게 하면 100만 행을 다 읽어야 할 수도 있어. B-TREE 인덱스가 있으면, 예를 들어 100행만 읽으면 돼.

인덱스 구조가 성능에 미치는 영향

인덱스가 빠른 이유는, 스캔해야 할 데이터 양을 줄여주기 때문이야. 예를 들어, 테이블에 수백만 행이 있어도, 인덱스가 있으면 쿼리는 몇 개 노드만 읽으면 돼서 훨씬 빨라져.

인덱스 구조를 이해하는 게 진짜 중요해. 인덱스가 어떻게 동작하는지 알면, 왜 어떤 쿼리가 느린지, 어떻게 하면 더 빠르게 만들 수 있는지 알 수 있거든.

그리고 어떤 인덱스를 써야 할지도 알아야 해. 범위 검색엔 B-TREE가 좋아. 배열이나 JSONB에는 GIN이 더 맞아. 잘못된 인덱스를 쓰면 오히려 느려질 수도 있어.

실전 예제

인덱스가 실제로 어떻게 도움이 되는지 예시로 보자.

정렬을 위한 인덱스

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

B-TREE 인덱스가 있으면, PostgreSQL이 인덱스에서 바로 정렬된 데이터를 가져올 수 있어서 추가 정렬이 필요 없어.

범위 검색을 위한 인덱스

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

B-TREE 인덱스 덕분에, 지정한 범위에 해당하는 행을 빠르게 찾을 수 있어.

자주 묻는 질문과 주의할 점

왜 항상 인덱스를 쓰면 안 돼? 인덱스는 디스크 공간을 차지하고, insert, update, delete 작업이 느려질 수 있어. 인덱스 구조도 같이 업데이트해야 하거든. 그래서 자주 쓰는 컬럼에만 인덱스를 만들어야 해.

언제 인덱스가 소용없어? 테이블의 대부분 행을 읽는 쿼리(예: WHERE true)에는 PostgreSQL이 Seq Scan을 선호해. 인덱스 노드를 읽는 게 이득이 없으니까.