데이터베이스 인덱스의 구조와 특징

개요

데이터베이스에서 빠른 검색을 위해 사용되는 인덱스는 여러 가지 자료구조로 구현됩니다. 이 글에서는 주요한 인덱스 구조들의 특징과 장단점을 살펴보겠습니다.

---

인덱스의 주요 구조

1. Binary Search Tree (BST)

구조 특징:

• 이진 탐색 트리 구조
• 각 노드가 최대 2개의 자식 노드를 가짐
• 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값

검색 성능:

• 평균 시간복잡도: O(log n)
• 최악의 경우: O(n) - 편향 트리일 때

 

2. B-Tree

 

구조 특징:

• 다진 탐색 트리 구조
• 각 노드가 여러 개의 키를 가질 수 있음
• 모든 리프 노드가 같은 레벨에 위치
• 자식 노드의 개수가 2개 이상으로 확장 가능

주요 장점:

• 디스크 I/O 최적화
• 균형 잡힌 트리 구조 유지

 

3. B+ Tree

구조 특징:

                 [가이드 노드]
               /      |      \
              /       |       \
         [가이드]   [가이드]   [가이드]
            |        |         |
    [실제 데이터] - [실제 데이터] - [실제 데이터]
         ↑                              ↑
         └──────── 연결 리스트 ─────────┘

 

핵심 특징:

• 가이드 노드: 상위 레벨에서는 검색 경로만 제공
• 리프 노드: 맨 아래 레벨에만 실제 데이터 존재
• 연결 구조: 리프 노드들이 연결 리스트로 연결됨

 

B+ Tree의 주요 장점:

1. 범위 검색 최적화
   • 리프 노드가 연결되어 있어 순차 접근이 용이
   • WHERE age BETWEEN 20 AND 30 같은 범위 검색에 탁월
2. 일관된 검색 성능
   • 모든 데이터가 리프 레벨에 있어 검색 시간이 일정
3. 효율적인 순회
   • 정렬된 순서로 데이터 접근 가능

---

인덱스 사용 시 고려사항

저장 공간 오버헤드

문제점:

• 인덱스는 원본 컬럼 데이터를 복사하여 정렬된 상태로 저장
• 인덱스 생성 시마다 추가적인 디스크 공간 필요

예시:

-- 원본 테이블: 1GB
CREATE INDEX idx_name ON users(name);     -- +200MB
CREATE INDEX idx_email ON users(email);   -- +250MB
CREATE INDEX idx_age ON users(age);       -- +100MB
-- 총 저장 공간: 1.55GB

 

성능 영향

INSERT/UPDATE/DELETE 시 성능 저하:

• 원본 테이블 변경 시 관련된 모든 인덱스도 함께 업데이트 필요
• 인덱스가 많을수록 쓰기 작업 성능 저하

성능 저하 시나리오:

-- 사용자 정보 업데이트 시
UPDATE users SET name = 'John', email = 'john@email.com' WHERE id = 1;

-- 실제 수행되는 작업:
-- 1. users 테이블 업데이트
-- 2. idx_name 인덱스 업데이트
-- 3. idx_email 인덱스 업데이트
-- 4. 기타 관련 인덱스들 업데이트

 

만약 모든 컬럼에 인덱스를 걸어준다면?

: 인덱스는 B-TREE 구조로 데이터들을 '정렬' 한 복사 사본입니다. 하지만 모든 컬럼에 인덱스를 걸면 어떻게 될까요?
이 '정렬' 이라는 개념이 정립되지않습니다. 왜? 모든 곳에서 자기 기준대로 정렬을 하려면, 그냥 기존의 테이블 형식으로 복사 사본이 만들어질 수 있습니다. 추가적으로 데이터들이 생성/수정/삭제 되었을 때, 인덱스 컬럼에서는 추가적인 작업이 필요한데, 모든 곳에 인덱스가 걸려있다면 엄청난 데이터들의 움직임으로 성능 저하가 생깁니다.

---

인덱스 설계 원칙

1. 선택적 인덱스 생성

• 자주 검색되는 컬럼에만 인덱스 생성
• 카디널리티가 높은 컬럼 우선 고려

 

2. 복합 인덱스 활용

-- 개별 인덱스 대신
CREATE INDEX idx_name ON users(name);
CREATE INDEX idx_age ON users(age);

-- 복합 인덱스 고려
CREATE INDEX idx_name_age ON users(name, age);

 

3. 정기적인 인덱스 성능 모니터링

• 사용되지 않는 인덱스 제거
• 쿼리 실행 계획 분석

---

결론

인덱스는 검색 성능을 크게 향상시키는 강력한 도구이지만, 저장 공간과 쓰기 성능의 트레이드오프가 존재합니다. 특히 B+ Tree 구조는 범위 검색에 최적화되어 있어 대부분의 관계형 데이터베이스에서 기본 인덱스 구조로 채택되고 있습니다.

효과적인 인덱스 설계를 위해서는 애플리케이션의 쿼리 패턴을 분석하는 것이 중요합니다.