[DB] DB Index

DB Index

---

1. 인덱스란?

인덱스란, 주기적인 쓰기 작업과 저장 공간을 활용해 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 책을 예로 들었을 때, 우리가 원하는 내용을 찾기 위해 책의 모든 내용을 뒤져보는 것은 오랜 시간이 걸리는 비효율적인 일이다. 그렇기 때문에 책의 맨 앞이나 맨 뒤에 색인이라는 항목을 추가하는데, 데이터베이스에서 인덱스란 책에서의 색인과 같다.

데이터베이스에서도 원하는 데이터를 찾기 위해 테이블의 모든 데이터를 탐색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성해 빠르게 조회할 수 있도록 한다.

위의 그림과 같이, 유저가 쿼리를 날렸을 때 인덱스를 통해 찾고자 하는 데이터의 위치를 확인하고 그 데이터를 사용자에게 전달한다. 인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE 나 DELETE 의 성능에도 영향을 미친다. 그 이유는 해당 연산을 수행하기 위해 대상을 먼저 조회해야 하기 때문이다.

// Garu 라는 이름을 수정하기 위해서는, Garu 이라는 이름을 가진 데이터를 먼저 조회해야 한다.

UPDATE USER SET NAME = 'DonGaru' WHERE NAME = 'Garu';

만약 인덱스를 사용하지 않은 컬럼을 조회해야 하는 상황에는 전체를 탐색하는 Full Scan 을 수행해야 한다. Full Scan 은 전체를 비교해 탐색하기 때문에 당연히 처리 속도가 떨어질 수밖에 없다.

 

2. 인덱스의 관리

DBMS 는 인덱스를 항상 최신 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE 가 수행되면 각각 다음의 연산을 추가적으로 수행해야 하며 그에 따른 오버헤드가 발생한다.

• INSERT : 새로운 데이터에 대한 인덱스 추가
• UPDATE : 기존의 인덱스를 '사용하지 않음' 처리하고 갱신된 데이터에 대한 인덱스 추가
• DELETE : 삭제하는 데이터의 인덱스를 '사용하지 않음' 처리

 

3. 인덱스 사용의 장점과 단점

장점

• 테이블을 조회하는 속도를 향상시킬 수 있다.
• 전반적인 시스템의 부하를 줄일 수 있다.

단점

• 인덱스를 관리하기 위해 추가적인 저장공간이 필요하다.
• 데이터 관리 외에 인덱스 관리를 위한 추가적인 작업이 필요하다.
• 인덱스를 잘못 사용하는 경우 오히려 성능이 저하될 수 있다.

만약 CREATE, UPDATE, DELETE 가 빈번한 컬럼에 인덱스를 걸게 되면 인덱스의 크기가 비대해져 성능이 오히려 저하되는 역효과가 발생할 수 있다. 그러한 이유 중 하나는 UPDATE 와 DELETE 연산 때문인데, 앞서 언급한 대로 UPDATE 와 DELETE 는 기존의 인덱스를 삭제하는 것이 아니라 '사용하지 않음' 처리를 한다. 만약 어떤 테이블에 UPDATE 와 DELETE 가 빈번하게 발생한다면 실제 데이터는 10만 건인데 인덱스는 100만 건이 넘어가게 되는 등, SQL 문 처리 시 비대해진 인덱스로 인해 성능이 오히려 떨어지게 된다.

 

Index 의 효율적인 사용

---

1. 인덱스의 특징

인덱스는 WHERE 절에서 효과가 있다.

인덱스는 SELECT - FROM - WHERE 절 중 WHERE 절에 사용할 컬럼에 대한 효율화라 볼 수 있다. WHERE 절을 사용하지 않고 인덱스가 걸린 컬럼을 조회하는 것은 인덱스가 성능에 아무런 영향을 주지 못한다.

 

예를 들어, '학생' 테이블에 학번, 이름, 전화번호 가 있다고 가정해보자. 인덱스는 학번과 전화번호에 걸려 있다. 다음 중 인덱스가 영향을 주는 쿼리는 어떤 것이 있을까?

1. SELECT '학번' FROM '학생';
2. SELECT '전화번호' FROM '학생' WHERE '이름' = '김철수';
3. SELECT * FROM '학생' WHERE '학번' = 1;

정답은 당연히 3번이다. 1번은 WHERE 절을 사용하지 않아 인덱스가 영향을 주지 않고, 2번은 WHERE 절을 사용했지만 해당 절에서 사용한 컬럼이 인덱스가 적용되지 않은 컬럼이기 때문에 영향을 주지 않는다.

 

무조건 많이 설정하면 성능이 좋아질까?

인덱스는 테이블마다 하나 혹은 여러 개의 컬럼에 대해 설정할 수 있다. 단일 인덱스를 여러 개 생성할 수도 있고, 여러 컬럼을 묶어 복합 인덱스를 설정할 수도 있다.

그러나 무조건 인덱스를 많이 설정하는 것이 검색 속도를 향상시키는 데 도움을 주지 않는다. 인덱스는 데이터베이스의 저장 공간을 사용해 테이블 형태로 저장되므로 개수와 저장 공간은 비례한다.

따라서, 조회 시 자주 사용하고 고유한 값 위주로 인덱스를 설정하는 것이 성능에 도움이 된다.

 

DML (Data Manipulation Language) 각각에 어떤 영향을 미칠까?

SELECT 쿼리는 성능이 눈에 띄게 향상되지만 INSERT, UPDATE, DELETE 쿼리에서는 때에 따라 다르다.

• UPDATE, DELETE 는 WHERE 절에 잘 설정된 인덱스로 조건을 붙여주면 조회할 때 성능에 영향을 준다.
  (수정, 삭제할 데이터를 조회할 때의 속도가 빨라지는 것이지, 수정 자체의 속도가 빨라지는 것이 아니다.)
• INSERT 의 경우는, 새로운 데이터가 추가되면서 기존 인덱스 페이지에 저장되어 있던 탐색 위치가 수정되어야 하므로 효율이 좋지 않다.

즉, 인덱스는 원하는 데이터를 빠르게 찾을 때 빛을 발한다.

 

어떤 컬럼에 인덱스를 설정하는 게 좋을까?

테이블의 목적 등에 따라 인덱스의 개수는 달라질 수 있지만 일반적으로 한 테이블 당 3~5 개 정도의 인덱스가 적당하다. 인덱스는 컬럼을 정해 설정하는 것이므로 후보 컬럼의 특징을 잘 파악해야 한다. 아래 4가지 기준을 잘 고려하면 효율적으로 인덱스를 설정할 수 있다.

• 카디널리티 (Cardinality)
• 선택도 (Selectivity)
• 활용도
• 중복도

---

카디널리티 (Cardinality)

카디널리티가 높을수록 인덱스 설정에 좋은 컬럼이다.

(= 한 칼럼이 갖고 있는 값의 중복 정도가 낮을수록 좋다.)

 

카디널리티는 컬럼에 사용되는 값의 다양성 정도, 즉 중복 수치를 나타내는 지표이다. 후보 컬럼에 따라 상대적으로 중복 정도가 낮다, 혹은 높다로 표현한다.

 

예를 들어, 10개의 행을 갖는 '학생' 테이블에 학번과 이름 컬럼이 있다고 하자. 학번은 학생마다 고유하게 부여받는 값이므로 10개의 값 모두가 고유한 값이다. 이름은 동명이인이 있을 수 있으니 1 ~ 10 의 카디널리티 값을 갖는다. 즉, 상대적으로 학번이 이름에 비해 카디널리티 값이 높으므로 인덱스로 설정하기에 알맞다.

---

선택도 (Selectivity)

선택도가 낮을수록 인덱스 설정에 좋은 컬럼이다.

5 ~ 10% 가 일반적으로 적당하다.

 

선택도는 데이터에서 특정 값을 얼마나 잘 선택할 수 있는지에 대한 지표이다. 선택도는 다음과 같이 계산할 수 있다.

선택도 (Selectivity) 
    = 컬럼의 특정 값의 row 수 / 테이블의 총 row 수 * 100
    = 컬럼의 값들의 평균 row 수 / 테이블의 총 row 수 * 100

예를 들어, 10개 행을 갖는 '학생' 테이블에 학번, 이름, 성별 컬럼이 있다고 하자. 학번은 고유하고, 이름은 동명이인이 2명씩 존재하고, 성별은 남녀 의 비율이 5:5 이다.

• 학번의 선택도 = 1 / 10 * 100 = 10% (동일한 학번이 존재하지 않으므로 어떤 값의 row 수는 모두 1)
• 이름의 선택도 = 2 / 10 * 100 = 20% (두 명마다 같은 이름을 가지므로 값들의 평균 row 수는 2)
• 성별의 선택도 = 5 / 10 * 100 = 50% (10명 중 5명이 남자, 5명이 여자로 특정 값의 row 수가 모두 5)

즉, 선택도는 특정 필드값을 지정했을 때 선택되는 레코드 수를 테이블 전체의 레코드 수로 나눈 비율이다.

---

활용도

활용도가 높을수록 인덱스 설정에 좋은 컬럼이다.

 

활용도는 해당 컬럼이 실제 작업에서 얼마나 활용되는지에 대한 값이다. 수동 쿼리 조회, 로직과 서비스에서 쿼리를 날릴 때 WHERE 절에서 자주 활용되는지를 통해 판단할 수 있다.

---

중복도

중복도가 없을수록 인덱스 설정에 좋은 컬럼이다.

 

중복도는 중복되는 인덱스 여부가 있는지에 대한 값이다. 인덱스 성능에 대한 고려 없이 마구잡이로 설정하거나, 다른 부서 / 다른 작업자의 분리된 요청으로 같은 컬럼에 대해 인덱스가 중복으로 생성된 경우를 볼 수 있다.

 

인덱스도 테이블 형태로 생성되므로, 속성을 가지고 그 속성을 컬럼으로 관리한다. 이 속성이 다를 때 같은 컬럼이라 할지라도 중복으로 인덱스 설정이 가능하다. 같은 컬럼에 대해 중복 인덱스 설정이 되어있다 하더라도 SQL 자체 연산이 빠른 쪽으로 데이터를 조회하지만, 인덱스도 결국 메모리의 일부를 사용하기 때문에 필요없는 항목은 삭제하는 것이 좋을 것이다.

---

인덱스를 설정할 때 고려해야 할 특징들을 위와 같이 정리했지만, 실제로 인덱스를 효율적으로 적용하는 것은 어떤 데이터를 다루느냐, 그 데이터가 어떤 특징을 가지고 있느냐를 추가적으로 고려해야 하기 때문에 위의 수치만을 가지고 절대적으로 판단할 수 있는 것은 아닌 것 같다.

 

인덱스의 자료구조

---

인덱스를 구현하기 위해 여러 자료구조를 사용할 수 있다. 아래에서는 가장 대표적인 해시 테이블과 B+Tree 에 대해 설명하겠다.

 

1. 해시 테이블 (Hash Table)

해시 테이블은 (Key, Value) 형태로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key 값을 이용해 고유한 Index 값을 생성하고 그 Index 에 데이터를 저장하거나 Index 에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB Index 는 (데이터=컬럼의 값, 데이터의 위치) 를 (Key, Value) 로 사용해 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현했다. 해시 테이블의 탐색 시간복잡도는 O(1) 이며 매우 빠른 검색을 지원한다.

 

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 매우 제한적인데, 그러한 이유는 해시 연산이 등호 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성으로 인해 부등호 연산이 자주 사용되는 데이터베이스 검색에 해시 테이블이 적합하지 않다.

예를 들어, "나는" 으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받을 수 없게 된다. 이러한 이유로 데이터베이스의 인덱스 저장을 위한 자료구조로는 B+Tree 가 많이 사용되고 있다.

 

2. B+Tree

B+Tree 는 DB 의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree 를 개선한 자료구조이다. B+Tree 는 모든 노드에 데이터를 저장한 B-Tree 와는 다른 특성을 가지고 있다.

• 리프 노드 (데이터 노드) 만 인덱스와 함께 데이터 (Value) 를 저장하고, 나머지 노드 (인덱스 노드) 들은 데이터를 위한 인덱스 (Key) 만을 갖는다.
• 리프 노드들은 Linked List 로 연결되어 있다.
• 데이터 노드의 크기는 인덱스 노드의 크기와 같지 않아도 된다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 B-Tree 의 리프 노드들을 Linked List 로 연결해 순차검색을 용이하게 하는 등 B-Tree 를 인덱스에 맞게 최적화했다. (물론 Best Case 에 대해, 리프 노드까지 가지 않고 데이터를 탐색할 수 있는 B-Tree 에 비해 무조건 리프 노드까지 탐색해야 데이터를 찾을 수 있다는 단점도 존재한다.)

이러한 이유로, 비록 B+Tree 는 O(logn) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 적합한 자료구조로 사용되고 있다.

 

아래 그림은 InnoDB 에서 사용된 B+Tree 의 구조이다.

InnoDB 의 B+Tree 는 일반적인 구조보다 더욱 복잡하게 구현이 되어있다. InnoDB 에서는 같은 레벨의 노드끼리는 Linked List 가 아닌 Double Linked List 로 연결이 되어있고, 부모 노드와 자식 노드들은 Singly Linked List 로 연결되어있다.

 

 

#Reference.

유림's Blog

[Database] 인덱스(index)란?