인덱스(index)란?
데이터베이스에서 테이블의 검색 속도를 높이기 위한 자료구조이다.
이 인덱스라는 것이 무엇이길래 검색 속도를 높이는데 효율적인 것일까?
보통 데이터베이스에서 특정 데이터를 찾기 위해서 테이블을 조회한다면, 테이블에 있는 모든 정보를 읽느라 시간이 오래 걸릴 것이다. 하지만 그 특정 데이터의 위치를 알려주는 데이터가 있다면 그 데이터를 보고 한번에 내가 원하는 특정 데이터의 위치로 갈 수 있는 것이다.
이 인덱스를 설명하기 위해서 주 예시로 책의 색인을 예로 든다. 책을 읽을 때 앞에서부터 천천히 넘기면 내가 원하는 주제를 찾기 힘들다. 하지만 맨 앞 혹은 맨 뒤에 수록되어있는 찾아보기(색인)을 통해서 내가 원하는 주제를 한번에 찾아갈 수 있다.
데이터베이스에서 이 색인의 역할을 하는 것이 바로 인덱스이다.
인덱스의 구조는?
일반적으로 키(Key)와 값(Value)으로 구성된다. 이 키는 검색에 사용이 되는 값이며, 값은 레코드를 가리키는 포인터이다. 즉, 키를 통해서 검색을 하고 검색해서 나온 값을 가지고 해당 위치로 갈 수 있는 것이다.
인덱스는 해시 테이블(Hash Table), B트리(B-Tree), B+트리(B+Tree) 구조를 사용할 수 있다.
해시 테이블(Hash Table)
데이터들을 해시 값으로 매핑한 테이블로, 데이터를 아주 빠르게 찾아낼 수 있는 자료구조이다.
이 해시 테이블은 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간복잡도를 가지고 있으며, 해시 함수를 이용하여 키값을 배열의 인덱스로 변환하고 이 인덱스에 해당하는 배열의 원소에 값을 저장한다.
하지만 이 해시테이블은 서로 다른 키(Key)가 같은 값(Value)를 반환하는 상황인 해시 충돌이 발생할 수 있다.
이 해시 충돌을 해결하기 위해서는 체이닝과 개방주소법이 있으나 이는 나중에 다시 포스팅을 하도록 하겠다.
하지만 이 해시 테이블은 실제로 인덱스에서 잘 사용이 되지 않는다.
해시 테이블은 등호 연산에 최적화되어있기 때문이다. 하지만 데이터베이스에서는 부등호 연산이 자주 사용이 되는데 해시 테이블은 정렬되어 있지 않으므로 크거나 작은 값을 빠른 시간 내에 찾을 수 없다.
B트리(B-Tree)
이진 트리를 확장해 하나의 노드가 가질 수 있는 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이며, 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조이다.
B트리는 여러 개의 노드로 구성이 된다.
가장 위의 노드를 루트 노드라고 하고, 가장 하위 노드를 리프 노드, 그 사이 노드를 서브 노드라고 한다.
이때 각 노드는 하나의 데이터 페이지와 연결되어 있으며, 이러한 노드들이 트리 구조를 형성하여 데이터를 빠르게 검색할 수 있도록 한다.
B트리 인덱스의 동작 순서는 다음과 같다.
- 인덱스 노드를 검색하여 검색 키와 일치하는 서브 트리를 선택
- 선택된 서브 트리에서 다시 검색을 수행
- 검색 키와 일치하는 데이터를 찾으면 종료
B트리의 경우, 키 값과 데이터 값이 노드 안에 함께 저장이 되기 때문에 노드의 크기가 크고 디스크 I/O 작업이 많아지는 문제가 있다. 때문에 B트리 구조보다는 B+트리 구조를 더 많이 사용한다.
B+트리(B+Tree)
B+트리는 B트리의 변형 중 하나로 데이터베이스 인덱스와 파일 시스템 사용에 더 적합할 수 있도록 만들어졌다.
B트리의 노드가 크고 디스크 I/O 작업이 많아지는 문제를 개선하기 위해서 B+ 트리에서는 데이터 노드의 포인트만 갖고, 모든 데이터는 리프 노드에만 저장한다. 또한 리프 노드는 서로 연결된 리스트의 형태를 이룬다.
그렇다면 B+ 트리의 장점은 무엇일까?
첫번째로, 더 적은 I/O 작업을 수행한다.
리프 노드만 디스크 I/O 작업을 수행하므로, 더 적은 I/O 작업을 수행한다. B트리와 달리 노드의 크기가 크지 않아서 한 번에 많은 양의 데이터를 읽을 필요가 없기 때문이다.
두번째로, 범위 검색의 속도가 빠르다.
모든 데이터는 리프 노드에만 저장이 된다. 따라서 범위 검색을 더 빠르게 처리할 수 있다.
세번째로, 더 많은 데이터를 처리할 수 있다.
인덱스 블록의 크기의 조정이 유연하다. 때문에 더 많은 데이터를 처리할 수 있다.
네번째로, 성능이 더 좋다.
B트리와 마찬가지로 검색 성능이 뛰어나지만, 범위 검색 및 저장 공간에서도 더 나은 성능을 가진다. 또한 B+트리는 더 작은 크기의 노드들을 읽은 후에 리프 노드에 도착하기 때문에 데이터를 읽어오는 비용이 줄어든다.
따라서, 인덱스는 주로 B+트리 구조를 사용한다!
인덱스의 장점과 단점
지금까지 나온 인덱스의 장점을 정리해보면
테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있으며, 전반적인 시스템의 부하를 줄일 수 있다!
는 것이다.
그렇다면 이렇게 좋은 인덱스, 과연 단점은 없을까?
장점이 있다면 단점도 있기 마련이다. 인덱스의 단점에 대해서 알아보자.
인덱스의 단점으로
첫번째, 인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 필요하다는 것이다.
인덱스를 관리하기 위해서는 결국 인덱스 테이블이 필요하고 이 테이블을 생성하면 결국 저장공간을 차지하게 된다.
두번째로, 인덱스를 관리하기 위해서는 추가 작업이 필요하다.
인덱스는 항상 최신의 정렬된 상태로 유지를 해야 원하는 값을 빠르게 탐색할 수 있다. 따라서 인덱스가 적용된 컬럼이 INSERT, UPDATE, DELETE가 수행이 된다면 인덱스에는 추가된 작업들이 필요하다.
- INSERT : 새로운 데이터에 대한 인덱스를 추가
- UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가
- DELETE : 삭제한 데이터의 인덱스를 사용하지 않음 처리
세번째, 인덱스를 잘못 사용할 경우 오히려 성능이 저하가 된다.
인덱스를 관리하기 위해서는 두번째 단점처럼 추가로 된 작업이 필요하다. 하지만 INSERT, DELETE, UPDATE 등이 빈번한 속성이 인덱스를 걸게 된다면 어떻게 될까?
UPDATE, DELETE의 연산은 기존의 인덱스를 사용하지 않음 처리를 진행한다. 삭제를 하지 않기 때문에 INSERT나 DELETE, UPDATE 등이 빈번하게 이루어진다면 인덱스의 크기가 매우 커지고 이는 오히려 성능 저하를 불러일으키게 된다.
인덱스를 사용하면 좋은 경우
그렇다면 성능이 좋지만 잘 사용해야하는 인덱스, 언제 사용해야하는걸까?
인덱스를 사용하면 좋은 경우는 다음과 같다.
-
규모가 작지 않은 테이블
: 예를 들어 50개의 데이터가 있는 경우는 굳이 인덱스를 사용하지 않고 풀 스캔을 사용하더라도 충분히 빠를 수 있다. 즉, 데이터의 양이 적으면 적을수록 효율을 내기 힘들다는 것이다.
-
INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
: 데이터가 추가되거나 값이 바뀔 경우, 삭제될 경우 값들을 정렬해주기 위해서 인덱스는 새로운 작업들을 진행해야한다. 자주 발생하는 컬럼이라면 자주 정렬을 진행해야하기 때문에 데이터베이스의 속도를 저하시킬 수 있다.
등..
이처럼 인덱스는 좋으니까 사용해야지~ 라고 생각해서 무작정 적용했다가 성능 저하를 일으키는 것보다 인덱스를 사용하면 좋은 경우를 잘 생각하여 적용을 해보는 것을 추천한다!
