데이터베이스 - 인덱스에 대해서

1. 인덱스란?

데이터베이스 인덱스(index)는 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블에 저장된 데이터의 검색 속도를 향상시키기 위한 자료구조이다. 조건을 만족하는 튜플(들)을 빠르게 조회하기 위해 사용한다. (빠르게 정렬(order by)하거나 그룹핑(group by)하기 위해서)

1-1. Index를 쓰는 이유

만약, Index를 사용하지 않게 되면 어떻게 될까? Index를 사용하지 않으면 데이터를 검색할 때 전체 테이블을 스캔(full scan)을 하게 된다. 만약 데이터가 1억에 있으면 O(N)의 시간복잡도로 1억 번을 탐색하게 된다. 하지만 Index를 사용하게 되면 검색 대상 레코드의 범위를 줄일 수 있다. 이는 대량의 데이터를 다루는 경우 데이터 검색 속도를 크게 향상시킨다.

 

1-2. Index의 장단점

• 장점
  • 검색 대상 레코드의 범위를 줄여 데이터를 빠르게 조회할 수 있다.
  • 중복 데이터를 방지하거나 특정 컬럼의 유일성을 보장한다.
  • order by 절과 group by 절, where 절 등이 사용되는 작업이 더욱 효율적으로 처리된다.
• 단점
  • 인덱스 생성에 따른 추가적인 저장 공간이 필요하다.
  • 데이터 삽입, 삭제 시, 인덱스를 업데이트해야 하므로 성능 저하가 발생할 수 있다.
  • 인덱스 생성 시간이 오래 걸릴 수 있다.

 

1-3. 인덱스 종류

• 클러스터형 인덱스(Clustered Index)
  • 클러스터형 인덱스란 데이터 행의 원래 순서대로 저장되어 있는 인덱스를 의미
  • 데이터의 저장 순서 그대로 되어있기 때문에 각 테이블은 단 하나의 클러스터형 인덱스를 가질 수 있다.
  • 클러스터형 인덱스는 행 데이터를 지정한 열에 맞춰 자동으로 정렬한다.
  • 클러스터형 인덱스는 영어사전이다. 영어사전은 책 내용 자체가 알파벳 순서로 되어 있기 때문에 그 자체가 인덱스가 된다.
• 보조형 인덱스(Secondary Index)
  • 보조형 인덱스란 실제 데이터의 위치와는 별개로 저장되는 인덱스를 의미
  • 보조형 인덱스는 인덱스의 기준이 되는 컬럼을 기준으로 실제 데이터와는 다른 별도의 순서를 가진다.
  • 그렇기 때문에 각 테이블은 여러 개의 보조형 인덱스를 가질 수 있다.
  • 보조형 인덱스는 '일반적인 목차가 있는 책'이다. 책 내용은 특정 키워드 순서로 진행되는 것은 아니지만 목차를 통해 그 키워드를 찾아 접근할 수 있듯, 보조형 인덱스도 데이터의 저장 순서와는 상관없이 존재한다.

 

2. 인덱스의 자료구조

2-1. 해시 테이블(Hash table)

해시 테이블은 키(Key)와 해시 값(Hash Value) 쌍으로 이루어진 자료구조이다. O(1)의 시간복잡도를 가지고 있어 상당히 빠른 검색을 할 수 있는 것이 특징이다.

해시 테이블의 검색 방식은 키를 해시 함수를 사용하여 해시 값으로 변환한 후, 해당 해시 값에 해당하는 값을 찾아서 검색한다. 해시 테이블은 검색 속도가 매우 빠르지만, 데이터의 분포에 따라 충돌이 발생할 수 있다. 따라서 충돌을 해결하기 위한 방법이 필요하다.

https://xladmt.tistory.com/entry/%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94%EA%B3%BC-%ED%95%B4%EC%8B%9C-%EC%B6%A9%EB%8F%8C-%EB%B0%8F-%ED%95%B4%EA%B2%B0%EB%B0%A9%EB%B2%95

해시 테이블과 해시 충돌 및 해결방법

 

해시는 등호(=, !=) 연산에만 특화되어 있어, 부등호 연산(>, <)인 범위 검색에는 적합하지 않다.

 

2-2. B-Tree

B-Tree는 데이터베이스에서 가장 널리 사용되는 인덱스 자료구조 중 하나이다. O(logN)의 시간 복잡도를 가지고 있다. B-Tree는 균형 잡힌 이진 검색 트리로 데이터베이스에서 검색 속도를 높이기 위해 사용된다.

B-Tree의 각 노드 내 데이터들은 항상 정렬된 상태인 것이 특징이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. (자식 노드의 개수는 n+1개) 또한, 한 노드에서 여러 개의 키를 가질 수 있고, 키에 해당하는 데이터도 함께 갖고 있다.

 

2-3. B+Tree

B+Tree는 B-Tree의 변형된 구조로 B-Tree와 비슷하지만 몇 가지 차이점을 가지고 있다. B+Tree 또한 균형 잡힌 이진 검색 트리이다. B+Tree는 B-Tree에 비해 더 많은 키를 가질 수 있다.

B+Tree는 B-Tree와 달리 내부 노드(Internal node)와 단말 노드(Leaf node)로 구분된다. B+Tree의 모든 데이터는 단말 노드에서만 저장되며, 내부 노드에는 검색을 위한 인덱스만 저장된다.

모든 리프 노드가 연결 리스트로 연결되어 있으며, 순차적으로 저장되어 있다. 이러한 특징으로 인해 범위 검색(Range Search)이나 순차 검색(Sequential Search)에 효율적이다.

 

3. index 실습

3-1. 자동으로 생성

1. 기본키로 생성 : 테이블 생성 시 기본키를 지정해주게 되면 그 기본키를 기준으로 하는 하나의 클러스터형 인덱스를 가진다.
2. UNIQUE 제약조건으로 생성 : 테이블의 컬럼에 유일 값을 가지게 하는 UNIQUE로 설정하게 되면 그 컬럼을 기준으로 하는 하나의 보조형 인덱스를 가진다.

 

3-2. 수동으로 생성

CREATE INDEX [인덱스 이름] ON [테이블 이름](컬럼 이름)

 

ex) 예시

CREATE TABLE employees (
    employee_id INT NOT NULL,
    first_name VARCHAR(50),
    last_name VARCHAR(50),
    department_id INT,
    PRIMARY KEY (employee_id)
);
CREATE INDEX idx_department_id ON employees (department_id);

 

3-3. 인덱스 확인

show index from [테이블명];

 

4. 인덱스 단편화(Index Fragmentation)

인덱스 단편화란, 인덱스 페이지들이 물리적으로 연속되지 않고 흩어져 저장되어 있는 상태를 의미한다. 이로 인해 데이터 조회 시 디스크 I/O가 증가하고, 인덱스 탐색 성능이 저하될 수 있다.

 

 

[참고]

https://ittrue.tistory.com/331

[DB] 데이터베이스 인덱스(index) 개념 정리

https://liltdevs.tistory.com/193

MySQL 단편화 Fragmentation 의 이해와 해결

https://jaehee1007.tistory.com/131

인덱스(Index)의 개념 정리 및 실습을 통해 이해하기