DB 인덱스

왜 인덱스가 필요한가

DB를 사용하면서 데이터의 양(Row)이 늘어남에 따라 실행 결과의 속도의 차이가 난다. 특히 JOIN, 서브 쿼리 사용 시 발생하는 곱연산에 따른 데이터의 양은 엄청나게 증가하게 된다. 이러한 데이터의 증가로 인해 WHERE 조건절로 필요한 데이터만 추출해서 사용하였는데 DB 인덱스를 사용하면 보다 빠르고 쿼리의 성능을 높일 수 있다.

인덱스

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 예를 들어 두꺼운 책에서 원하는 내용을 찾고 싶다고 가정해보자. 원하는 내용을 찾기 위해 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸리고 비효율적이다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다. 색인을 이용하면 책에서 원하는 내용을 훨씬 빠르게 찾을 수 있는 것처럼 테이블에서 index를 이용하면 원하는 데이터를 빠르게 찾을 수 있다.

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

테이블의 특정 칼럼(Column)에 인덱스를 생성하면, 해당 칼럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 칼럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장한다. 

데이터 = 책의 내용, 인덱스 = 책의 목차, 물리적 주소 = 책의 페이지 번호 라고 생각할 수 있다. 

인덱스의 장단점

장점

WHERE

테이블을 만들고 데이터가 쌓이게 되면 데이터(Row)는 순서에 상관 없이 섞이게 된다. 이렇게 되면 WHERE절로 특정 조건의 데이터를 검색할 때, 데이터의 처음부터 끝까지 찾아봐야 하는 단점이 생긴다. 이것을 풀 테이블 스캔 (Full Table Scan), 줄여서 풀 스캔(Full Scan)이라고 한다.

하지만 인덱스를 사용한 인덱스 테이블 스캔(Index Table Scan)시 데이터들이 정렬되어 저장되어 있는 인덱스 테이블을 사용하므로 WHERE절 사용시 조건에 맞는 데이터들을 더 빠르게 찾을 수 있다.

이것이 인덱스를 사용하는 가장 큰 이유이다.

ORDER BY

인덱스를 사용하면 ORDER BY를 사용하여 정렬해야 하는 번거로움을 피할 수 있다. 사실 ORDER BY는 굉장히 큰 작업이므로 피해주는 것이 좋은데 인덱스를 사용하면 자동으로 정렬되어 있기 때문에 ORDER BY를 피할 수 있다.

MIN, MAX

위에서 말한 것처럼 인덱스 테이블은 자동으로 정렬되어 있으므로 굳이 MIN, MAX를 쓰지 않아도 첫 번째 레코드가 MIN, 마지막 레코드가 MAX인 것을 알 수 있다.

단점

DML

INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 데이터들을 다시 정렬을 해야 한다. 또한 위의 그림에 나와 있듯이 인덱스 테이블, 원본 테이블 두 군데의 데이터 수정 작업을 해줘야 한다는 단점도 발생한다. 따라서 인덱스를 사용하려면 데이터의 변경이 잦은 테이블보다 검색 위주의 테이블에 사용하면 좋다.

인덱스 스캔

검색 위주의 테이블이라도 무조건적인 인덱스 스캔이 좋은 것은 아니다. 인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 낫다. 예를 들어 100만개의 데이터가 있는 테이블과 1개의 데이터가 있는 테이블을 비교해보자. 전자의 경우 데이터가 너무 많으므로 풀스캔보다 인덱스 스캔이 낫다. 그러나 후자의 경우 굳이 인덱스 스캔을 할 필요 없이 풀스캔이 더 빠를 것이다.

속도 향상

인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하기 때문에 무턱대고 인덱스를 만들어서는 결코 안 된다. 즉, 속도 향상이란 장점과 따라오는 단점들의 비용을 비교해서 인덱스를 만들지 말지를 결정해야 한다.

인덱스 자료구조

해시 테이블(Hash Table)

해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다. (key, value)로 쌍을 표현하며, key값을 이용해 대응되는 value값을 구하는 방식이다. 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 자료구조이다.

해시 테이블을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치)로 구현하는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않는다. 왜나하면 해시 테이블은 등호(=) 연산에 최적화되어있기 때문이다. 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

예를 들어 "지금"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용된다.

B+Tree

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다. 

인덱스에서 B-Tree 대신 주로 B+Tree를 사용하는 이유는 뭘까?
해시 테이블에서 언급했듯이 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 된다. 이러한 이유로 비록 B+Tree는 O(log2n)의 시간복잡도로 해시테이블의 시간복잡도인 O(1)보다 느린 속도를 지니지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

B-Tree 예시

B+Tree 예시

B+Tree vs B Tree

• B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다.
• B+Tree에서 leaf node끼리는 Linked list로 연결되어있다.
• B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다

B+Tree 장점

1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다. 

2. Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.

B+Tree 단점

반면, B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 하는 단점이 있다.