[데이터베이스/DB] 데이터베이스에서 인덱스(INDEX)의 사용

0. 들어가면서

인덱스(Index)는 데이터베이스에서 테이블의 조회 속도를 높여주는 자료구조를 말합니다.

 

조회 성능의 관점에서 인덱스의 사용은 데이터베이스 안의 레코드를 처음부터 풀스캔(Full Scan)하지 않고, 테이블 내의 컬럼을 색인화하여 B+ Tree로 구성된 구조를 만들고 INDEX 파일 검색으로 속도를 향상시키게 됩니다.

 

사실 인덱스 자체에 대한 개념은 평소에 우리가 무의식적으로 계속 사용하고 있습니다.

List<Object> objects = ...

Object o = objects.get(index);
...

위와 같이 리스트에서 어떤 자료를 뽑을 때 처음부터 하나하나 세서 해당 위치에 있는 자료를 뽑는 것이 아니라, 인덱스로 바로 접근하여 해당 위치의 데이터를 꺼내오고 있죠.

 

 

그렇다면 데이터베이스에서 인덱스를 사용한다는 것은 어떤 뜻이며, 이러한 인덱스를 사용해야 하는 이유는 무엇일까요?

인덱스는 아래의 물음을 어떻게 해결할 것인가에 대한 답이 되는 개념입니다.

 

• 데이터베이스는 내가 원하는 데이터를 어떻게 찾는가?
• 데이터가 매우 많을 때, 원하는 데이터를 찾기 위해서는 시간이 왜 오래 걸리는가?
• 왜 조인(JOIN)을 하면 조회가 느려질까?

 

 

1. B+ Tree

1-1. B-Tree

이진 트리는 하나의 부모가 두 개의 자식밖에 가지지 못하기 때문에 한 쪽으로 길게 치우친 이진트리의 경우 거의 O(N)에 가까운 시간복잡도로 탐색을 수행하기 때문에 조회의 효율성이 떨어질 수 있습니다.

 

이에 대한 해결책으로 제시된 B-Tree는 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있도록 하며, 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞춰주는 트리 자료구조입니다.

 

한편, B-Tree에서 하나의 노드가 최대 M개의 자식을 가질 수 있을 때 이를 M차 B-Tree라고 하며 B-Tree에서 각 노드의 자료는 정렬된 상태가 유지되고, 노드의 값을 기준으로 왼쪽은 노드보다 작은 값이 들어가고 오른쪽 서브트리는 더 큰 값이 들어갑니다. 

 

아래는 3차 B-Tree의 예시입니다.

 

3차 B-Tree

루트 노드와 그 자식들을 살펴보면 10보다 작은 쪽으로는 5가 들어가게 되고, 10과 20 사이에는 14와 17이 들어갔습니다. 그리고 23, 27은 20보다 크기 때문에 오른쪽으로 들어가게 된 것이죠.

 

 

1-2. B+Tree

B+Tree는 위에서 설명한 B-Tree와 유사하지만 리프노드가 연결리스트의 형태를 가지기 때문에 선형 검색이 가능한 트리입니다. 이러한 특징으로 인해 특정한 범위에 있는 자료값들을 쉽게 인덱싱할 수 있고, 이로 인해 DB에서 채택한 자료구조로 자리매김하게 된 것이죠.

 

또한, B+Tree에서는 리프노드에 데이터 값들이 저장되어 있습니다. B-Tree에서는 각 노드마다 각자의 데이터가 있었지만 B+Tree는 리프 노드에 모든 데이터를 모아둡니다.

 

마지막으로 리프노드의 부모 Key는 리프노드의 첫번째 Key보다 작거나 같은 값을 갖습니다. B-Tree에서 달라진 점이라고 하면 '키'값을 기준으로 한다는 것과 키값이 '같은' 녀석도 자식으로 들어갈 수 있다는 것이죠.

 

아래는 B+Tree의 예시입니다.

 

B+Tree

 

B-Tree와 B+Tree를 잘 정리한 블로그가 있어 첨부합니다. 좀 더 자세한 개념과 동작 과정을 알고 싶으신 분은 아래 블로그를 참고하면 도움이 될 것 같습니다.

 

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

 

 

 

 

 

2. Clustered Index vs Non-Clusetered Index

한편, Index에는 크게 두 가지 분류가 있습니다. 각각에 대해서 짚어보겠습니다.

1-1. Clustered Index

Cluster는 '군집'을 의미하며, Clustered Index는 데이터와 인덱스가 결합하여 군집화 된 형태를 말합니다. 

 

조금 풀어서 설명하자면, Clustered Index는 DB안에 있는 데이터들을 어떤 물리적 순서로 정렬할 때 기준이 되는 인덱스를 의미하는데요. DB의 레코드들을 물리적으로 정렬하기 위해서는 한 가지 방법밖에 쓸 수 없기 때문에 하나의 테이블에는 하나의 인덱스만 존재할 수밖에 없습니다. 그리고 기본값으로는 테이블의 Primary Key값을 인덱스로 설정됩니다.

 

한편, 커스텀화 된 Clustered Index를 사용할 때는 테이블의 데이터를 지정된 컬럼에 대해 물리적으로 재배열하고, INDEX를 생성할 때는 데이터 페이지 전체를 다시 정렬합니다. 데이터가 테이블에 삽입되는 순서와 상관없이 INDEX로 생성되어 있는 컬럼을 기준으로 정렬되어 삽입되는 것이죠.

 

이 상황은 비단 커스텀화 된 Clustered Index를 생성할 때만 일어나지 않습니다. 아래와 같은 상황을 보겠습니다.

 

41	Jo, 2016147008, 90
42	Kim, 2020123123, 88
43	Choi, 2017231312, 85
44	Yun, 2018231222, 83
45	Sim, 2017789126, 75

 

41, 42,.., 45는 각 학생의 등수라고 생각해보고, 오른쪽 데이터는 학생의 이름, 학번, 점수라고 생각해보겠습니다. 만약 이 상황에서 84점인 학생 Shin, 2018562113, 84라는 레코드를 삽입하면 어떻게 될까요?

 

41	Jo, 2016147008, 90
42	Kim, 2020123123, 88
43	Choi, 2017231312, 85
44	Shin, 2018562113, 84
45	Yun, 2018231222, 83
46	Sim, 2017789126, 75

 

44, 45번째 등수인 학생 Yun, Sim을 각각 한 단계 아래로 이동시키고, 44번째 등수에 Shin이라는 학생을 넣어야 합니다. 즉, 레코드들을 하나씩 이동시켜야하는 과정에서 정렬을 해야하는 비용이 발생하게 되는 것이죠.

 

또한, 테이블에 데이터가 많이 저장된 상태에서 ALTER를 통해 Clustered Index를 추가하면, 많은 데이터를 Index에 맞춰 재정렬해야 하므로 많은 리소스를 차지하게 됩니다.

 

따라서, Clustered Index는 어떤 범위에 있는 데이터를 조회하는 등의 일반적인 조회에서는 매우 좋은 성능을 보이지만 데이터의 수정이나 삽입 등에 있어서는 이에 따른 비용으로 인해 성능에 악영향을 미칠수도 있게 됩니다.

 

그렇다면 우리가 보통 테이블의 PK값을 Auto_Increment로 하는 이유도 위의 맥락에서 이해할 수 있습니다. 인덱스가 기본값으로 PK값으로 설정된 상태에서 PK값 중에서 중간에 있는 어떤 값으로 데이터를 삽입하면 데이터의 재정렬이 일어나야 하기 때문에 성능이 안좋아지기 때문이죠.

 

 

1-2. Non-Clustered Index

Non-Clustered Index는 레코드들이 테이블에 삽입될 때 물리적인 순서를 정해두지 않습니다. Non-Clustered Index는 데이터 테이블과는 분리되어서 다른 장소에 저장되는 것이죠. 따라서 별로의 추가 저장 공간이 필요해진다는 것도 Non-Clustered Index의 정의에서 생각해볼 수 있습니다.

 

한편, Non-Clustered Index의 개념은 우리가 책을 읽을 때를 생각해보면 이해하기 쉬울 것 같습니다. 책의 진짜 내용은 각 페이지마다 있겠지만, 책의 목차는 맨 앞으로 빼두고 필요한 내용은 목차를 통해 찾아볼 수 있게 합니다. 이 때, 목차는 페이지 순서로도 해둘 수 있고 가나다 순으로 할 수도 있는 등 여러 방식이 가능하기 때문에 여러 개의 Non-Clustered Index가 존재할 수 있습니다.

 

Non-Clustered Index

위 그림을 보면 실제 데이터들은 물리적으로 정렬되어 있지 않지만, Index는 데이터 테이블과 분리되어 있고 Index를 찾아서 실제 데이터를 조회하고 있습니다.

 

예를 들어 위 그림에서 오른쪽 데이터 테이블의 키값이 '1'인 데이터 위치는 인덱스 테이블의 1번에 써져 있습니다. 그래서 해당 인덱스 테이블의 Record Pointer를 읽으면 키값이 '1'인 데이터는 '어느 곳에 있다'라는 정보를 알 수 있게 되는 것입니다. 그러면 그 정보를 바탕으로 데이터를 찾아가면 되겠죠.

 

위의 Clustered Index에 대해서 이해하고 Non-Clustered Index를 바라보면, Non-Clustered Index가 가지는 장점이 바로 보일 것 같습니다.

 

바로, Clustered Index에 비해 조회 속도는 느리지만, 데이터의 입력/수정/삭제는 더 빠르다는 사실인데요.

 

데이터가 물리적으로 정렬되어 있지 않기 때문에, 입력/수정/삭제 등을 할 때 데이터를 이동시키는 리소스가 발생하지 않습니다. 다만, 데이터를 INSERT할 때는 해당 데이터를 포인팅하는 인덱스를 생성해줘야만 하겠죠. 한편, 데이터를 조회할 때  인덱스를 통해 바로 데이터를 조회하는 것이 아니라, 인덱스는 데이터가 저장된 위치를 포인팅하기 때문에 그 포인터를 찾아가야 합니다. 그래서 Clustered Index보다 조회 시 약간은 느린 단점이 있죠.

 

3. 인덱스를 이용해서 쿼리 성능 개선 테스트해보기

MySQL을 사용해서 인덱스를 사용했을 때 어느 정도 조회 성능의 개선이 일어나는지 직접 확인해보려고 합니다.

 

우선 아래와 같은 쿼리문을 이용해서 백만개의 레코드를 가진 학생 테이블을 만들겠습니다. 학생 테이블에서 PK는 'sno'입니다. 그러면 이제 MySQL은 자동으로 sno를 기준으로 Clustered Index를 생성했겠죠? 아무런 설정도 하지 않았을 때 Default 인덱스값은 PK 값이기 때문입니다.

create table student(
    sno int primary key,
    sname varchar(10) not null,
    dept varchar(5) not null,
    year int,
    enter_date datetime default now()
);

drop procedure if exists load_student_data;

delimiter #
create procedure load_student_data()
begin
	declare i int default 0;
	declare sno int;
	declare sname varchar(10);
	declare dept varchar(5);
	declare year int;

	while i < 1000000 do
	    set i = i + 1;
	    set sname = lpad(conv(floor(rand()*pow(36, 10)), 10, 36), 10, 0);
	    set dept = lpad(conv(floor(rand()*pow(36, 5)), 10, 36), 5, 0);
	    set year = FLOOR(1 + RAND() * 4);
			
	    insert into student (sno, sname, dept, year) values (i, sname, dept, year);
	end while;
    
end #
delimiter ;

call load_student_data();

데이터 생성

데이터 백만개를 넣기 위해서 245.239sec 정도가 걸리는데요. 한 3~4분 정도의 시간은 기다리셔야 합니다.

 

자, 이제 위 데이터를 가지고 데이터의 조회 쿼리를 실행해보도록 하겠습니다.

 

먼저 sno는 이미 Clustered Index로 설정되었으므로, sno를 기준으로 데이터를 조회해보겠습니다. 그러면 아래와 같이 정말 빠른 시간 안에 해당하는 데이터를 조회해오는 것을 확인할 수 있습니다.

 

sno으로 조회

 

그런데 만약 'sname'으로 학생을 조회하면 어떻게 될까요? 'sname'으로 학생을 조회했을 때는 아래 그림에서 볼 수 있다시피 0.238 sec가 걸린 것을 볼 수 있습니다. 위에서 'sno'를 통해 조회했을 때보다 적어도 몇 백배는 더 느려진 것을 확인할 수 있습니다.

 

sname으로 조회

 

백 만개의 테이블 레코드를 풀 스캔(Full-Scan)했기 때문에 위와 같은 결과가 나온 것입니다.

 

그런데 만약 우리의 비즈니스 로직이 학생의 이름을 통한 조회가 빈번히 필요로 한다면 어떻게 될까요? 매 번 학생을 조회할 때마다 오랜 시간이 걸리기 때문에 쿼리의 성능이 좋지 못하겠죠.

 

따라서, 이러한 상황을 개선하기 위해 아래와 같이 sname을 가지고 인덱스를 생성해보겠습니다. 인덱스를 새로 생성할 때는 테이블의 데이터를 넣는 시간보다는 훨씬 적은 시간이 걸립니다.

 

sname으로 인덱스 생성

 

그리고 이전에 했던 것과 똑같은 쿼리로 sname을 통한 조회를 해보겠습니다.

 

sname을 인덱스로 설정하고, sname으로 조회

이전에 sname을 인덱스로 사용하기 전에는 0.238sec가 소요됐는데, 현재는 0.00069sec가 소요된 것을 알 수 있습니다. 조회에 관한 쿼리의 성능이 매우 향상된 것입니다.

 

 

4. 인덱스를 사용할 때 고민해볼 점

3-1. Where절

인덱스는 기본적인 쿼리 구조인 SELECT, FROM, WHERE 절 중에서 WHERE 절에 들어가는 컬럼을 대상으로 합니다. 어떻게 보면 당연한 말이겠지만 WHERE 절에 쓰이지 않는 컬럼을 인덱스로 생성해봤자 조회를 할 때 해당 컬럼이 어떤 도움도 주지 못하게 되기 때문이죠.

 

3-2. DML(Data Manipulation Language)

인덱스는 기본적으로 조회 시 성능 향상을 위한 자료구조라고 했습니다. 이는 역으로 생각하면 조회를 제외한 다른 쿼리에는 오히려 인덱스의 사용이 악영향을 미칠 수도 있다는 사실을 말하는데요.

 

위에서 말했듯이 Clustered Index의 경우 데이터의 삽입이나 삭제, 업데이트가 일어날 때 데이터를 재정렬해야 하기 때문에 리소스가 발생합니다. 그리고 Non-Clustered Index 역시 인덱스 테이블에 새로운 인덱스를 생성하고 원데이터에 대한 포인터를 생성해야 하는 리소스가 발생하고, 테이블에서 원데이터가 삭제되더라도 인덱스 테이블은 남아있기 때문에 불필요한 값들이 남아있게 되는 문제가 생길 수 있습니다.

 

이러한 이유로 자주 업데이트, 삭제, 삽입이 일어나는 컬럼의 경우에는 인덱스로 설정할 때 고민이 필요합니다.

 

3-3. 카디널리티(Cardinality)

카디널리티가 높을수록 인덱스 설정에 좋은 컬럼입니다. 이는 한 컬럼이 갖고 있는 값의 중복 정도가 낮을수록 좋다는 것을 말하는데요. 

 

예를 들어, PK로 설정된 컬럼은 테이블의 모든 레코드가 고유한 값을 가지기 때문에 중복 정도가 가장 낮고, 이는 카디널리티가 높다고 말할 수 있습니다. 그래서 되도록이면 카디널리티가 높은 컬럼을 인덱스화하여 조회 시 필요한 데이터를 바로 찾아낼 수 있게 하는 것이 좋습니다.

 

 

---

 

이번 포스팅에서는 인덱스(INDEX)의 개념과 Clustered, Non-Clustered Index를 공부했습니다. 그리고 MySQL을 이용해서 인덱스를 사용했을 때 쿼리의 조회 성능이 얼마나 개선되는지를 살펴봤는데요.

 

다른 포스팅에서는 실제 개발을 하면서 인덱스를 사용하게 될 때, 그 경험을 정리해보겠습니다.

 

감사합니다.