Index

Index

Database에서 데이터를 검색할 때, 적재된 데이터의 양이 매우 많거나, 많아질 것이 자명한 경우.

보통 Index를 특정 column에 적용함으로써 쿼리의 성능을 해결하려는 경우가 많다.

오늘은 다음 두 단골 질문에 대해서 정리하려고 한다.

• Index를 적용하면 어떤 원리로 쿼리 성능이 향상되는 것일까?

• Index를 적용하는 것이 무조건 좋은가?

About Index

인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조다.

특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.

아래 그림을 보면 특정 컬럼에 인덱스가 생성됐을 때 컬럼의 데이터들을 오름차순으로 정렬한 모습을 볼 수 있다.

인덱스의 가장 큰 특징은 데이터들이 정렬이 되어있다는 점이다.

이 특징으로 인해 조건 검색이라는 영역에서 굉장한 장점이 된다.

WHERE 절의 효율성

테이블을 만들고 안에 데이터가 쌓이게 되면 테이블의 레코드(row : 행)는 내부적으로 순서가 없이 뒤죽박죽으로 저장이 된다.

그 결과, WHERE 절에 특정 조건에 맞는 데이터들을 검색할 때 풀스캔을 해서 비교한다.

하지만 인덱스 테이블 스캔(Index Table Scan) 시 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건(WHERE)에 맞는 데이터들을 빠르게 찾아낼 수 있는 것이다.

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

ORDER BY 절의 효율성

인덱스를 사용하면 ORDER BY에 의한 정렬(Sort) 과정을 피할 수가 있다.

ORDER BY는 굉장히 부하가 많이 걸리는 작업이다.

정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생되기 때문이다.

디스크 I/O는 데이터를 작성하고 변경할 때 HDD에 저장되는 것을 말한다.

하지만 인덱스를 사용하면 이러한 전반적인 자원의 소모를 하지 않아도 된다.

MIN, MAX의 효율적인 처리

이것 또한 데이터가 정렬되어 있기에 얻을 수 있는 장점이다.

MIN값과 MAX값을 레코드의 시작 값과 끝 값만 가져오면 되기 때문에 풀스캔으로 작업하는 것보다 훨씬 효율적이다.

Cons of Index

인덱스의 가장 큰 문제점은 정렬된 상태를 계속 유지시켜줘야 한다는 점이다.

DML

INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다.

그렇기 때문에 DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋다.

주문데이터, 거래데이터와 같이 DML이 빈번한 테이블에 인덱스를 생성하게 되면 오히려 성능이 저하될 수 있다.

속도 향상을 위해 인덱스를 많이 만드는 것은 좋지 않다.

인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다.

무턱대고 인덱스를 만들어서는 결코 안 된다는 것이다.

즉, 속도 향상에 비해 단점들의 COST를 비교해서 인덱스를 만들지 말지를 정해야 한다.

Data structure of Index

우선 B+ Tree에 대해서 알아보자.

B+Tree는 이름처럼 트리 구조로 되어 있다. 바이너리 트리랑 개념적으로는 비슷하다.

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다.

B+Tree는 모든 노드에 데이터(Value)를 저장했던 BTree와 다른 특성을 가지고 있다.

따라서 Key 값으로 정렬되어 있는 형태인데, 다른 점은 Children 노드가 여러 개라는 점이다.

또한 각각의 노드가 메모리가 아닌 디스크에 있다.

아래 그림을 참조하자. 각 노드들이 디스크에 저장되어 있고 포인터로 찾아가는 방식이다.

또한 각 leaf노드는 형제 노드(sibling)으로 가는 포인터가 있기 때문에 range query에 효율적이다.

그 다음으로는 Hash Table 이 있다.

Hash table

해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다.

해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다.

해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.