Database Index 에 관하여: Index 의 개념, 자료구조, 효율적인 인덱스 생성 전략 (DB Index)

Index의 개념

인덱스란, 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

우리가 사전을 이용해 단어를 찾을 때, index 라는 단어를 찾기 위해 a 부터 찾기 보다는, 알파벳 별로 색인을 두고 i 에서 시작하는 것이 효율적이다. (요즘은 영어사전 세대가 아니라고 하던데.. 허허)

 

이와 같이 대용량 데이터베이스를 조회 시 인덱스를 생성하여 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있다.

장단점

장점

• 조회 성능 향상
• 시스템 부하 개선

단점

• 인덱스 관리를 위한 DB 내 저장 공간 필요
• 관리 포인트 증가
• 잘못 사용될 경우 오히려 성능이 저하될 수 있음

Index 의 자료구조

인덱스를 구현하기 위해 다양한 자료구조를 사용할 수 있다. 대표적으로 해시 테이블과 B-Tree 가 있다.

1. 해시 테이블

• {key:value} 로 데이터를 저장하는 자료구조. key 값을 이용해 고유한 인덱스를 생성하며, 그 인덱스에 저장된 값을 가져오는 구조이다.
• 시간복잡도: O(1)
• 해시 함수는 정확히 해당 키-값 에 매칭되어야 사용할 수 있으며, 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성하기 때문에, 부등호, LIKE 연산이 자주 사용되는 검색 조건에 적합하지 않다.
• 이를 보완하기 위해 B-Tree 자료구조를 사용한다.

2. B-Tree

• 가장 일반적인 인덱스. 각각의 DBMS는 B-Tree 를 변형하여 B+Tree, B+-Tree 등으로 사용하기도 한다.
• 인덱스는 페이지 단위로 저장되며, 인덱스 키를 바탕으로 항상 정렬된 상태를 유지한다.
• 리프 노드(데이터 노드) 인덱스(key)와 데이터(value; PK(RowID)) 를 가지며, 모든 노드에 데이터(value) 를 저장한다

페이지(블럭)?

• 디스크와 메모리에 데이터를 읽고 쓰는 최소 작업 단위
• PK(RowID), 인덱스, 테이블 등은 모두 페이지 단위로 관리된다.

즉, 쿼리를 통해 어떤 레코드를 읽고자 할 때, 결국 하나의 페이지(블럭) 를 읽어야 한다.

레코드를 찾는데 1개의 페이지만으로 처리가 안된다면 다른 페이지를 읽어야 하는데, 추가 페이지를 읽는 디스크 I/O 때문에 성능이 떨어지게 된다.

 

또한, 디스크 I/O 를 통해 페이지를 읽어오면 버퍼 풀이라는 메모리에 캐싱해두게 되는데, 개별 데이터의 크기가 커지면 페이지 자체의 크기가 커지게 되어, 메모리에 캐싱해 둘 수 있는 페이지 수가 줄어들게 된다.

 

그렇기 때문에, 페이지에 저장되는 개별 데이터의 크기를 최대한 작게 하여, 한 페이지에 많은 데이터를 저장할 수 있도록 하는 것이 중요하다.

3. B+Tree

• DB 인덱스를 위해 B-Tree 를 개선시킨 자료구조. MySQL 의 DB engine인 InnoDB 는 B+Tree 구조로 이루어져있다.
• 리프 노드(데이터 노드) 인덱스(key)와 데이터(value; PK(RowID)) 를 가지며, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스만을 가진다.
• 시간복잡도: O(log2n)
• B+Tree 의 리프노드들을 LinkedList 로 연결하여, 순차 검색이 용이하도록 인덱스에 맞게 최적화

인덱스가 필요한 이유

인덱스는 페이지 단위로 저장되며, 인덱스 키를 바탕으로 항상 정렬된 상태를 유지한다고 하였다.

 

예를 들어, 회원번호를 PK 로, 회원명을 인덱스로 가지는 테이블이 있다고 가정하자.

이 테이블에서 '홍길동' 이라는 회원을 찾고자 회원명으로 조회한다고 했을 때, 인덱스를 통해 리프 노드에 도달하고, 인덱스 키에 저장되어 있는 레코드의 값(PK(RowID)) 을 찾아와 이 값을 통해 최종적으로 데이터를 조회하게 된다. 즉, 인덱스를 통해 데이터를 조회 할 때에는 아래의 2가지 작업이 수행되는 것이다.

 

1. 인덱스를 통해 PK 를 찾고
2. PK 를 통해 해당 레코드를 찾는다

그냥 테이블에 접하여 데이터를 읽으면 1번의 작업만 수행되니까 이것이 더 효율적인 게 아닌가? 왜 인덱스를 통해 조회하는 것이 더 효율적일까?

 

우리는 흔히 DB 에 값이 순서대로 저장되어 있다고 생각하여, 특정 값을 꺼내 오는게 쉬울 것이라 생각한다. 하지만 DBMS 는 우리가 원하는 레코드가 어디에 있는지 모르므로, 모든 테이블을 뒤져서 (Full Scan) 데이터를 찾아야한다. 데이터가 적으면 괜찮겠지만, 데이터가 많으면 많을수록 이는 엄청난 디스크 읽기 작업을 수행하게 된다.

 

하지만 인덱스를 사용한다면, 인덱스를 통해 PK(RowID) 를 찾고, PK(RowID) 를 통해 레코드를 바로 가져올 수 있기 때문에 디스크 읽기가 줄어들게 된다.

 

그렇다면 Table Full Scan 과 Index Scan 의 손익 분기점은 어디일까?

 

인덱스를 통해 레코드 1건을 읽는 것이 4~5배 정도 비싸기 때문에, 조회 대상이 전체 테이블 레코드의 20~25% 를 넘어가면 Table Full Scan 이 더 효율적이라고 할 수 있겠다.

옵티마이저는 상황에 맞추어 Table Full Scan / Index Scan 을 할지 결정하여 실행 계획에 맞게 쿼리를 실행한다.

인덱스는 어떨 때 효과를 나타낼까?

1. 대규모 데이터를 가진 테이블

앞서 설명하였듯이, Table Full Scan 과 Index Scan 의 손익 분기점을 고려하여야 한다.

데이터가 적은 테이블이라면 Full Scan 을 태우는 것이 더 효과적일 것이나, 데이터가 많으면 많을수록 Index Scan 이 더 효율적일 것이다.

 

단, 물리적인 Data 양보다 Clustering Factor 가 더 큰 영향을 미치므로, 페이지(블럭) 을 관리하는 것이 중요하다.

 

Clustering Factor(군집성 계수)?

• 특정 index의 키 값 정렬 순서대로 table data 가 물리적으로 군집된 정도를 나타낸 수치.
• 인덱스를 스캔하는 동안 접근하게 되는 페이지(블럭) 의 갯수

2. 조회가 주로 일어나는 컬럼

INSERT, UPDATE, DELETE 가 빈번한 속성에 인덱스를 걸게 되면, 인덱스의 크기가 비대해져서 성능이 오히려 저하된다.

 

WHY?

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

• INSERT: 새로운 데이터에 대한 인덱스를 추가 (인덱스는 항상 정렬된 상태를 유지하므로, 적절한 위치 탐색 후에 인덱스가 저장됨)
• UPDATE: 기존 인덱스를 '사용하지 않음' 처리(삭제 마킹 쓰기 작업 - 실제 삭제하지는 않음)하고, 갱신된 데이터에 인덱스를 추가함
• DELETE: 삭제하는 데이터의 인덱스를 '사용하지 않음' 처리(삭제 마킹 쓰기 작업 - 실제 삭제하지는 않음)

즉, UPDATE/DELETE 가 빈번하게 발생되는 컬럼에 인덱스를 생성할 경우, 실제 데이터는 10만 건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스로 인해 성능 저하가 야기된다.

3. JOIN, WHERE, ORDER BY 에 자주 사용되는 컬럼

조회가 빈번히 일어나는 컬럼에 인덱스를 생성하여야 검색 대상을 효율적으로 필터링 할 수 있다.

4. 데이터의 중복도가 낮은 컬럼

카디널리티가 높을수록 검색 대상이 줄어들어 인덱스의 효율이 높아진다.

 

카디널리티(Cardinality; 기수성)?

• 유니크한 값의 수. (카디널리티가 높다 == 중복도가 낮다)

인덱스를 사용하지 않는 경우

full table scan 은 아래 경우에 주로 일어난다.

• WHERE / ON 절에 인덱스를 이용할 수 있는 조건이 없는 경우
• 테이블 레코드 건수가 너무 적어, 인덱스를 이용하는 것 보다 전체 테이블 스캔이 더 빠른 경우
• 인덱스 스캔을 통해 일치되는 레코드 건수가 너무 많은 경우

인덱스의 컬럼 순서

multi-PK 와 마찬가지로, 인덱스는 여러 개의 컬럼으로 구성될 수 있다.

다중 컬럼 인덱스에서 중요한 것은, 항상 이전 컬럼에 의존하여 다음 컬럼이 정렬된다는 것이다. 그렇기 때문에, 다중 컬럼 인덱스를 생성할 시에는 카디널리티가 높은 순으로 컬럼 순서를 결정하여야 검색 대상이 줄어들어 빠르게 처리할 수 있다.

 

인덱스를 정렬 순서대로만 읽을 수 있는 것은 아니다. 인덱스를 읽는 방향은 옵티마이저의 실행 계획에 따라 결정되므로, 인덱스 정순 스캔 / 인덱스 역순 스캔이 가능하다. 하지만 인덱스 정순 스캔이 인덱스 역순 스캔보다 빠르므로, 인덱스 생성 시에 적절하게 생성하는 것이 중요하겠다.

 

References.

• https://mangkyu.tistory.com/96
• https://mangkyu.tistory.com/286
• https://tech.kakao.com/2018/06/19/mysql-ascending-index-vs-descending-index/