데이터베이스 인덱스란 (인덱스의 개념과 종류)

0. 만약 인덱스가 없었다면

 

인덱스 없이 테이블에 대한 탐색을 한다고 가정해보자

num의 값이 27인 행을 찾는 다고 가정했을 때 인덱스가 없다면 , 정렬 되지 않은 데이터를 처음부터 찾아야한다.

이럴 경우 하나의 데이터를 찾기 위해서 최악의 경우 모든 값을 탐색하는 풀 스캔을 해야할 수도있다.

이는 매우 비효율적인 방법이다.

 

인덱스가 없는 경우 어떤 현상이 일어나는 지 알아보았으니, 그럼 이제 인덱스가 적용 된 경우를 살펴보자

 

 

처음 예시와의 차이점은 데이터가 정렬되어 있고 무작정 처음부터 조회하지 않는다.

이 경우 정렬된 데이터들로부터 인덱스를 통해 탐색하므로 효율적인 탐색이 가능해진다.

이제 우리는 인덱스를 통해 효율적인 탐색이 가능해진다는 것을 알았다.

바로 이 인덱스가 오늘 배워볼 주제이다.

어떻게 인덱스를 통해 효율적인 탐색이 가능하고, 어떻게 하면 효율적으로 인덱스를 사용할 수 있을 지 알아보자

 

1. 인덱스가 필요한 이유

 

테이블의 검색 성능을 높여주는 자료구조이다.

인덱스를 쓰게 되면 추가적인 쓰기 작업과 저장 공간을 활용하므로 탐색 속도를 높일 수 있다.

 

예시를 포함해서 지금까지의 설명으로 인덱스의 특징을 정리해볼 수 있다.

• 인덱스의 데이터는 정렬되어 있다.
• 인덱스는 추가적인 저장 공간을 필요로 한다.
• 인덱스를 사용해서 효율적인 탐색이 가능해진다.

여기까지만 들어도 인덱스가 무엇이고 어떤 장점이 있는 지 대략 파악되었을 것이다.

데이터베이스 쪽으로 좀 더 들어가서 구체적으로 왜 필요한 지 알아보자

 

2. 인덱스의 동작 방식

mySQL의 공식 문서를 보면 다음과 같이 나와있다.

Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.

 

크게 두 가지로 요약할 수 있다.

1. 조건에 맞는 데이터를 빠르게 검색하기 위헤
2. 데이터를 빠르게 정렬하거나 그룹핑 하기 위해

예를 들어,

SELECT * FROM team WHERE name = ‘sehan’;

DELETE FROM logs WHERE datetime < ‘2023-06-16’;

UPDATE employee SET salary = salary * 1.5 WHERE id = 100;

SELECT * FROM team T JOIN department D ON [T.id](<http://T.id>) = D.id;

 

각각의 쿼리에는 조건들이 포함되어 있다.

따라서 해당 쿼리들이 실행되면 조건에 맞는 데이터들을 찾아야한다.

하지만 이 경우 테이블의 데이터가 중간이나 끝에 있다면 풀스캔을 해야하는 상황이 된다.

 

이를 보완하기 위해 인덱스는 별도의 자료구조 및 작업을 실행하여 테이블 탐색 성능을 향상시켜준다.

즉 테이블의 데이터, 조건들을 빠르게 찾기 위해 필요한 것이 인덱스이다.

또한 인덱스는 조인을 할 때 조인을 하기 위한 조건을 빠르게 찾기 위해 사용되기도 한다.

무조건 Select 에서만 필요한 것이 아닌 조건 탐색을 위해서든 단순 데이터 탐색을 위해서든 인덱스는 사용될 수 있다.

 

3. 인덱스의 종류

그렇다면 인덱스는 어떻게 동작할까?

 

인덱스의 자료구조

인덱스를 구현하기 위한 자료구조로는 크게 두가지가 있지만 , 대표적으로 B-tree 와 B+tree 가 있다.

마지막엔 추가로 해시에 대해서도 알아볼 것이다.

B-tree,B+tree 에서 ‘B’의 의미는 정확히 밝혀진 바는 없지만 균형을 맞춘다는 의미에서 Balanced 라는 의미로 통한다.

균형을 맞춤으로써 좀 더 빠른 인덱싱이 가능해진다.

 

만약 자식노드들이 Balanced 하지 않다면 어떻게 될까?

트리가 편향되어 있는 BST(이진 탐색 트리)모습을 상상해보자

 

BST는 균형을 맞추지 않기 때문에 위와 같은 모습이 나올 수 있다. 

최악의 경우에는 O(n)의 시간 복잡도가 나오는데 B tree는 트리의 균형을 맞춤으로써 시간 복잡도를 줄여준다.

 

이는 BST는 최대 2개의 자녀 노드를 가지지만 B tree는 여러개의 자녀노드를 가질 수 있기 때문에 가능하다.

 

B-Tree

B-tree 는 항상 데이터가 정렬되어 있다는 특징이 있다.

때문에 어떤 데이터를 탐색하더라도 O(logN)의 시간 복잡도를 가진다.

그리고 모든 리프 노드들은 같은 레벨에 있으며 따라서 Balanced 되었다 라고 할 수 있다.

 

B-tree의 구성을 살펴보자, 노드는 키값과 리프 노드에 대한 포인터로 구성되어 있다.

각 key들의 왼쪽 자식들은 key보다 작은 값 ,오른쪽 값은 key보다 큰 값으로 되어있다.

 

B-tree 구조의 데이터 탐색 과정을 알아보자

현재 데이터에서 정수 27 데이터를 찾아보려고 한다.

먼저 27은 31보다 작으므로 왼쪽 자식노드로 이동한다.

그 다음 11, 29와 데이터를 비교하게 되는데 이 중간값이라는 것을 알 수 있다.

따라서 가운데에 있는 자식 노드로 탐색을 하게되고 27을 발견하게 되면서 탐색이 끝난다.

이렇게 균형 있는 트리 구조를 통해 특정 데이터를 효율적으로 찾을 수 있다.

 

하지만 모든 경우에서 베스트인것은 아니다.

선형 탐색(Full scan)의 경우 모든 데이터를 다 탐색하므로 O(n)의 시간 복잡도를 가진다.

이 경우 뒤에서 살펴볼 B+tree 라는 것을 통해서 Full scan시 효율을 개선할 수 있다.

 

삽입

삽입의 경우 조회 방식과 통일하게 Leaf Node들을 탐색하고 노드 자리가 비어있다면 해당 자리에 노드를 삽입 , 꽉 차 있다면 노드를 분할해서 삽입한다.

예제를 통해 13 데이터를 넣을려고 한다고 가정해보자

탐색의 결과, 12와 14 사이의 값에 배정되었다. 하지만 해당 Leaf Node는 노드가 꽉 찬 상태이다.

 

따라서 부모 노드에 데이터를 넣어주었다.

이렇게 되면 부모 노드도 꽉 찬 상태가 되므로 중앙값인 11로 데이터를 분할해준다.

 

부모 노드에 11을 넣으니 또 노드가 꽉 찬 상태가 된다.

그러므로 다시 중앙값인 11로 데이터를 분할해준다.

이렇게 함으로써 삽입 과정이 완료되었다.

 

B-tree의 특징

1. 모든 자식 들을 같은 레벨에 존재한다.
2. 노드의 key의 수가 k개라면, 자식노드는 k+1 이다.
3. Key들은 항상 정렬된 상태이다.

여기까지가 B- Tree 에 대한 작동 과정이다.

이제 B+ Tree에 대해 알아보자

 

B + Tree

 

B- tree와의 가장 큰 차이점은 리프 노드들만 데이터를 가질 수 있다는 점이다.

이는 Full scan 시에 가장 명확한 장점을 가진다.

 

다시 B-tree 의 Full scan 과정을 생각해보자

B-tree에서는 Full scan을 하기 위해서 모든 브랜치 노드 및 자식 노드들을 탐색했어야했다.

하지만 B+tree에서의 Full scan 은 다르다.

그 이유는 Leaf Node 에만 데이터가 존재하고 이들은 연결 리스트로 연결되어 있기 때문이다.

덕분에 한번의 선형 탐색으로도 Full scan을 완료할 수 있다.

 

B+tree의 특징

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 효율적인 탐색이 가능하다.

해시

 

 

해시가 인덱스에서 사용되는 것을 알기전에 해시테이블에 대해 알 필요가 있다.

해시 테이블은 key값을 인자로 하는 해시 함수의 결과를 통해 인덱스를 만듦으로써 데이터를 저장하는 자료구조이다.

이 경우 찾고자 하는 데이터의 key값을 해시함수 한번으로 조회할 수 있으므로 O(1)의 시간 복잡도를 가진다.

 

하지만 해시 자료구조는 인덱스에서 거의 쓰이지 않는데, 그 이유는 등호 방식에만 최적화 되어있기 때문이다.

즉 DB 탐색 시에 주로 사용되는 범위검색이나 정렬에는 취약하다.

이러한 단점 때문에 인덱스에서는 많이 사용되지 않는다.

 

인덱스의 종류

 

클러스터 인덱스

클러스터 인덱스는 실제 데이터를 정렬하여 인덱스를 만드는 것이다.

따라서 테이블당 단 하나의 클러스터 인덱스만을 만들 수 있다.

 

실제 데이터를 통해서 인덱스를 만드는 것이므로 조회 과정에서 매우 빠른 속도를 가진다.

하지만 그 외 삽입 , 삭제 , 수정 같은 경우 클러스터 인덱스의 사용이 적합하지 않다.

(DML이 일어나는 경우 매번 정렬을 유지하기 때문)

 

따라서 클러스터 인덱스는 테이블의 수정이 빈번하지 않고 조회 위주의 작업을 하게 될 경우 좋은 효율을 가질 수 있다.

실생활에 비유해보면, 영어 단어 책을 예시로 들 수 있다.

영어 단어 책은 항상 A~Z 까지 정렬되있는 데 책 자체가 정렬되어 있는 이것을 클러스터 인덱스로 볼 수 있다 !

 

논클러스터 인덱스

 

실제 데이터 테이블을 정렬하지 않고 별도의 공간에 인덱스 페이지를 생성해서 저장하는 방식이다.

따라서 인덱스 페이지를 저장하기 위한 추가적인 메모리 공간이 필요하다.

 

DB에서 데이터를 저장하는 단위이다.

하나의 페이지는 16kb의 크기를 가진다.

MySQL :: MySQL 8.0 Reference Manual :: 15.11.2 File Space Management

MySQL :: MySQL 8.0 Reference Manual :: 15.11.2 File Space Management

 

논클러스터 인덱스는 데이터의 조회보다 수정,삭제,삽입 시에 더 좋은 효율을 가진다.

실생활에 비유해보면 ,

책 앞에 색인(인덱스)를 보고 해당 내용이 있는 페이지로 이동하는 것이다 !

따라서 데이터의 조회보단 수시로 데이터의 변경이 일어나는 테이블에서의 사용하는 것이 적합하다.

4. 인덱스 만드는 법

SQL 문을 통해 인덱스를 만들 수가 있다.

이 중에서는 우리가 흔히 쓰는 프라이머리 키를 통한 인덱스 생성도 포함되어있다.

위에서 두가지의 인덱스를 배웠는데 각각 어떻게 만드는 지를 알아보자

 

클러스터 인덱스

1. 프라이머리 키를 선언하는 경우
2. not null + 유니크 제약 조건을 선언하는 경우

ALTER TABLE member ADD CONSTRAINT id PRIMARY KEY(id); → 클러스터링

ALTER TABLE member ADD CONSTRAINT id UNIQUE NOT NULL; → 클러스터링

 

논 클러스터 인덱스

1. 유니크 제약 조건을 선언하는 경우
2. 직접 (유니크)인덱스를 생성하는 경우

ALTER TABLE member ADD CONSTRAINT name UNIQUE(name); → 논클러스터링

CREATE INDEX name ON member (name); → 논클러스터링

아니면 테이블을 생성할 때 인덱스를 생성할 수도 있다.

CREATE TABLE member(
id INT PRIMARY KEY,
name varchar(20) not null,
INDEX name_idx (name)
)

 

이처럼 여러가지 방식으로 DB 인덱스를 생성할 수 있다.

5. 적절한 인덱스 사용

인덱스를 쓰면 빠른 조회가 가능하다는 장점이 있지만 인덱스를 사용하게 될 경우 추가적인 작업이 발생하므로 상황에 따라 사용하는 것이 좋다. 그렇다면 인덱스가 굳이 필요없는 상황은 언제일까?

1. 인덱스의 범위가 너무 넓은 경우이다. 넓다는 것의 기준은 전체 데이터의 15%이상을 조회해야한다는 의미로 보면 적합하다.
2. 이 경우 인덱스를 통한 효과가 미미하기 때문에 인덱스의 사용을 지양한다.
3. 조회보다 삽입,삭제 등 수정 작업이 많을 경우이다. 이 경우도 마찬가지로 인덱스로 인한 효과가 미미하다.(수정 작업 시 where 로 조회하는 경우 제외)
4. 데이터 자체가 적은 경우는 배보다 배꼽이 더 큰 상황이 올 수 있기 때문에 사용을 지양하는 것이 좋다.

6. 언제 쓰면 좋을까?

카디널리티가 높은 데이터를 인덱스로 하면 효과적이다.

여기서 카디너리티란 사전적 의미로 그룹 내 요소의 개수를 의미한다.

 

그렇다면 카디널리티가 높다는 것은 어떤 걸 의미할까?

정해진 데이터 내에서 그룹 내 요소 개수가 많다는 것은 중복이 적다는 것이다.

중복이 적다는 것은 인덱스로 사용 시 매우 좋은 효율을 낼 수 있다.

 

예를 들어 중복된 데이터가 많은 성별 , 학년은 카디널리티가 낮으므로(중복이 높음) 인덱스에 적합하지 않다.

반대로 학번 , 고유 ID 등은 카디널리티가 높으므로(중복이 낮음) 인덱스 사용에 적합하다.

7. 결론

인덱스의 동작 방식과 인덱스의 사용 효과에 대해 알아보았다.

인덱스는 적절하게 사용하면 좋은 효율을 낼 수 있지만 상황에 맞지 않는 인덱스 사용은 오히려 역효과를 불러올 수 있다.

때문에 인덱스가 필요한 상황인 지를 잘 판단해 효율적으로 사용할 수 있어야한다.

 

참고 자료

DB Index 동작원리를 알아보자

DB Index 동작원리를 알아보자

클러스터 인덱스 vs 넌클러스터 인덱스 | zinirun

클러스터 인덱스 vs 넌클러스터 인덱스 | zinirun

[자료구조] 그림으로 알아보는 B-Tree

[자료구조] 그림으로 알아보는 B-Tree