데이터베이스 인덱스

인덱스란?

데이터베이스에서 데이터의 읽기속도를 높이는 테이블의 동작속도(조회)를 높여주는 데이터 구조

• 책의 색인, 목차처럼, 인덱스는 테이블의 특정 컬럼에 대해 정렬된 순서로 키와 참조를 저장하여 검색 속도를 향상시킨다.
• 인덱스를 사용하면 대량의 데이터 중에서 원하는 데이터를 효율적으로 찾을 수 있다!

인덱스 예시로 이해하기

도서관에는 여러권의 책이 있는데, 이 책들을 관리하는 데이터베이스 테이블 library 가 있다. 이 테이블에는 아래와 같이 책의 ID, 저자, 출판연도, 출판사 등의 정보가 포함되어 있으며, 대략 도서 6만권의 정보가 들어있다.

 

인덱스가 없다면?

현재 테이블에서 등록번호가 'CEM97499'인 책을 찾고자 하는 쿼리를 실행한다고 가정해보자

SELECT * FROM library WHERE 등록번호 = 'CEM97499';

• 인덱스가 없는 상태에서 위의 쿼리를 실행하면 데이터베이스는 테이블의 모든 행을 하나씩 검사하며 등록번호가 `CEM97499` 인 행을 찾을 것이다. 아래의 실행계획을 보면 이해가 쉽다.

실행 계획 (Explain)

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	library	ALL(풀스캔)	NULL	NULL	NULL	NULL	65376	Using where

• table: 쿼리가 접근하는 테이블 (library)
• type: ALL은 테이블의 모든 행을 검사하는 전체 테이블 스캔을 의미한다.
• possible_keys: 사용 가능한 인덱스가 없다. (NULL).
• key: 사용된 인덱스가 없다.(NULL).
• rows: 쿼리가 검사해야 하는 행 수 (전체 테이블 행 수인 65376건).
• Extra: Using where는 WHERE 조건을 사용하여 필터링함을 나타냅니다.

  💡  즉 6만건의 데이터에 대해 전체 테이블 스캔(테이블 풀스캔)을 수행하므로 매우 비효율적이다.

인덱스 생성 및 적용

CREATE INDEX idx_library_등록번호 ON library(등록번호);

• 인덱스를 추가하면 데이터베이스는 등록번호 컬럼에 대한 정렬된 인덱스를 생성한다.
• 이 인덱스는 각 등록번호 값과 해당 값이 저장된 데이터의 위치를 저장하여 빠르게 검색할 수 있다.

다시 `CEM97499` 등록번호를 찾는 쿼리를 실행해보고, 실행계획을 봐보자.

SELECT * FROM library WHERE 등록번호 = 'CEM97499';

실행계획

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	library	ref(부분범위스캔)	idx_library _등록번호	idx_library _등록번호	203	const	1	Using index condition

• table: 쿼리가 접근하는 테이블 (library)
• type: ref는 인덱스를 통해 특정 값을 찾는 방식으로, 부분 범위 스캔을 의미한다,
• possible_keys: 사용할 수 있는 인덱스 (idx_library_등록번호).
• key: 실제로 사용된 인덱스 (idx_library_등록번호).
• key_len: 인덱스 키의 길이
• ref: 검색 조건에 사용된 값 (const는 고정된 값임을 의미).
• rows: 쿼리가 예상하는 결과 행 수 (인덱스를 통해 찾은 1건).
• Extra: Using index condition는 인덱스를 사용하여 데이터를 검색함을 의미한다.

💡 이 실행 계획에서 rows를 보면, 인덱스를 사용하여 등록번호 컬럼에서 `CEM97499`을 한번에 찾았다. 즉 테이블 풀스캔 대신 인덱스를 사용하여 검색하여 성능이 크게 향상됨을 알 수 있다.

---

인덱스 구조(B-Tree, Hash)

1. B-Tree 인덱스

B-Tree 인덱스는 대부분의 데이터베이스 시스템에서 기본적으로 사용되는 인덱스 구조로 이는 균형 트리 구조로, 검색, 삽입, 삭제 등의 연산이 O(logN)으로 효율적으로 이루어질 수 있도록 설계되어 있다.

구조

• 루트 노드(Root Node)
  • 트리의 최상위 노드이며, 모든 검색, 삽입, 삭제 작업은 루트 노드에서 시작된다.
• 내부 노드(Internal Nodes)
  • 루트 노드와 리프 노드 사이의 중간 노드들
  • 내부 노드들은 키 값과 자식 노드에 대한 포인터를 가진다.
  • 키 값에 따라 트리를 아래로 참색하여 리프 노드로 접근한다.
• 리프 노드(Leaf Nodes)
  • 트리의 최하위 노드로 실제 데이터의 포인터를 포함하고 있다.
  • 모든 리프 노드는 더블 링크드 리스트 형태로 연결되며 범위 검색에 유리하다.
  • 리프 노드에는 키와 실제 데이터 위치가 저장된다.

특징

• 균형 유지
  • 모든 리프 노드가 동일한 깊이(Depth)를 가지므로 균형(Balance)를 유지한다.
  • 이는 검색, 삽입, 삭제 연산의 성능이 일정하게 유지된다.
• 빠른 검색
  • 키 값이 정렬된 상태로 저장되기 때문에 이진 탐색을 통해 빠르게 검색할 수 있다.
  • 평균 시간복잡도 = O(log n)
• 범위 검색(Range Scan)
  • 리프 노드가 더블 링크드 리스트로 연결되어 있어 범위 검색에 매우 효율적이다.

---

2. 해시 인덱스

해시 함수를 사용하여 키 값을 해시 값으로 변환하고, 이를 통해 데이터를 빠르게 검색할 수 있는 인덱스 구조로, 정확한 키 검색에는 O(1)로 매우 빠르지만, 범위 검색에는 적합하지 않다.

구조

• 해시 함수(Hash Function)
  • 키 값을 해시 값으로 변환하는 함수
  • 해시 값은 버킷의 인덱스 역할을 한다.
• 버킷(Bucket)
  • 해시 함수로 계산된 인덱스 값이 저장되는 장소
  • 각 버킷은 하나 이상의 키(key)-값(value) 쌍으로 저장된다.
• 해시 테이블(Hash Table)
  • 해시 테이블은 여러개의 버킷으로 구성된다.
  • 해시 함수로 생성된 해시 값을 저장하는 테이블
  • 각 해시 값은 데이터의 위치를 가리킨다.

특징

• 빠른 검색
  • 해시 함수로 인해 검색 시간이 일정하다.
• 정확한 키 검색
  • 정확한 키 값에 대한 검색에 매우 효율적이다.
• 범위 검색(Range Scan) 불가능
  • 데이터가 정렬되지 않기 때문에 범위 검색에는 적합하지 않다.
• 충돌 처리
  • 동일한 해시 값을 갖는 여러 키 값(충돌)을 처리하기 위한 방법(예: 체이닝, 오픈 어드레싱)이 필요하다.

---

인덱스 종류

1. 클러스터 인덱스 (Clustered Index)

테이블의 데이터가 인덱스 순서에 따라 물리적으로 정렬되는 인덱스

특징

• 물리적 정렬
  • 클러스터 인덱스가 적용된 컬럼에 따라 테이블의 데이터가 물리적으로 정렬된다. 즉 데이터가 디스크에 저장될 때 인덱스 키 순서에 따라 정렬된다는 뜻이다.
  • 예를들면, 등록번호 컬럼에 클러스터 인덱스가 있는 경우, 등록번호가 정렬된 순서로 데이터가 저장된다.
• 실제 데이터 페이지와 인덱스 페이지가 동일
  • 클러스터 인덱스는 실제 데이터 페이지와 인덱스 페이지가 동일하다.
  • 즉, 인덱스 노드가 실제 데이터 행을 가리키는 것이 아니라, 인덱스 노드 자체가 데이터 행을 포함한다.
• 빠른 데이터 접근
  • 클러스터 인덱스를 사용하면 데이터 검색 시 인덱스 트리를 탐색한 후 바로 필요한 데이터에 접근할 수 있다.
  • 이는 인덱스와 데이터가 같은 순서로 정렬되어 있기 때문에 가능하며, 특히 범위 검색에 매우 유리하다.
• 한 테이블에 하나만 생성 가능
  • 한 테이블에는 하나의 클러스터 인덱스만 존재할 수 있다. 이는 데이터의 물리적 정렬이 하나의 기준에 의해서만 가능하기 때문이다.
• 행의 순서 유지
  • 삽입, 삭제, 업데이트 시 데이터가 자동으로 재정렬되어 행의 순서를 유지한다.
  • 이는 추가적인 디스크 I/O를 발생시켜 시스템 부하를 줄 수 있다.

---

2. 보조 인덱스 (Secondary Index)

클러스터 인덱스와 달리 테이블의 데이터가 물리적으로 정렬되지 않는 인덱스

특징

• 물리적 정렬 X
  • 보조 인덱스는 테이블 데이터가 물리적으로 정렬되지 않는다.
  • 즉 인덱스가 데이터의 위치를 가리킬 뿐, 데이터 자체의 순서는 변경되지 않는다.
• 여러 개 생성 가능
  • 한 테이블에 여러 개의 보조 인덱스를 생성할 수 있다.
  • 이는 다양한 컬럼이나 컬럼 조합에 대해 검색 성능을 최적화할 수 있다.
• 검색 성능 향상
  • 특정 컬럼이나 컬럼 조합에 대해 보조 인덱스를 생성하면, 해당 컬럼에 대한 검색 성능이 향상된다. 그러나 클러스터 인덱스보다는 다소 느리다.
• 인덱스 페이지와 데이터 페이지 분리
  • 보조 인덱스는 별도의 인덱스 페이지에 저장되며, 인덱스 페이지는 데이터 페이지를 가리키는 포인터를 포함한다.
  • 보조 인덱스를 사용한 검색은 인덱스 페이지를 먼저 탐색하고, 거기서 가리키는 데이터 페이지로 이동하는 방식이다.
• 중복 허용
  • 보조 인덱스는 중복된 값을 허용한다.
  • 예를 들어, 동일한 저자 이름이 여러 번 나올 수 있다
• 업데이트 시 오버헤드 (Overhead during Updates)
  • 데이터 삽입, 삭제, 업데이트 시 보조 인덱스도 업데이트되어야 하므로 추가적인 오버헤드가 발생한다. -> (클러스터 인덱스보단 적음)

---

요약

특징	클러스터 인덱스 (Clustered Index)	보조 인덱스 (Secondary Index)
데이터 정렬	인덱스 키 값에 따라 데이터가 물리적으로 정렬됨	데이터가 물리적으로 정렬되지 않음
한 테이블에 생성 가능 개수	한 개	여러 개
검색 성능	빠름 (데이터와 인덱스가 동일하게 정렬됨)	비교적 빠름 (인덱스 페이지를 탐색한 후 데이터 페이지로 이동)
데이터 저장 위치	데이터 페이지와 인덱스 페이지가 동일	별도의 인덱스 페이지에 저장
중복 허용	기본 키와 유니크 키는 중복 불가, 그 외 컬럼은 가능	중복 허용
업데이트 시 오버헤드	클러스터 인덱스 재정렬로 인한 추가 I/O 발생 가능	보조 인덱스 업데이트로 인한 추가 오버헤드 발생
사용 예시	PRIMARY KEY, UNIQUE KEY	일반적인 INDEX

---

인덱스 설계

인덱스 손익분기점

일반적으로, 테이블이 가지고 있는 전체 데이터양의 5% ~ 20%이내의 데이터가 출력 될 때만 Index를 타는게 효율적이고, 그 이상이 될 때에는 오히려 풀스캔이 더 빠르다

인덱스 설계 원칙

자주 사용되는 쿼리 분석

• 인덱스를 생성하기 전에 데이터베이스에서 자주 사용되는 쿼리를 분석하자.
• 주로 `WHERE 절`, `JOIN 조건`, `ORDER BY`, `GROUP BY` 절에 사용되는 컬럼을 중심으로 분석하자.
• 쿼리의 실행 계획을 확인하고, 인덱스가 쿼리 성능에 어떻게 영향을 미치는지 분석하자.

선택도 높은 컬럼 선택

• 선택도 :  컬럼 값의 중복도(Cardinality)를 나타내는 지표
• 선택도가 높은 컬럼(즉, 중복도가 낮은 컬럼)은 인덱스로 생성할 때 효율적이다.
• 선택도가 높은 컬럼 예시 : 기본 키, 유니크 컬럼, 주민등록번호, 등록번호 등
• 선택도가 낮은 컬럼 예시 : 성별, 상태와 같은 범주형 데이터

복합 인덱스 사용

• 여러 컬럼을 조합하여 생성된 인덱스를 복합 인덱스라 하며, 이는 복잡한 쿼리의 성능을 향상시킬 수 있다.
• 인덱스 생성 순서가 중요하므로 복합 인덱스를 생성할 때는 자주 사용되는 컬럼을 먼저 배치한다.
• 일반적으로 WHERE 절에서 사용되는 컬럼을 우선시한다.
  •