[데이터베이스] 인덱스(Index)
인덱스(Index)란?
인덱스는 데이터를 더 빠르게 검색하고 조회하는 기능을 제공하는 자료구조이다. 이름이 색인인 것처럼 책의 색인과 유사하게 작동하게 되는데, 책의 한 주제를 찾을 때 첫 장부터 순차적으로 조회하지 않고 목차를 확인하듯 DB 또한 책의 목차와 같이 색인을 통해 데이터를 빠르게 조회할 수 있다.
대부분의 인덱스는 B tree, 해시 구조를 사용하고, 해당 자료구조를 통해 조회 성능을 향상시킨다.
인덱스를 사용하는 이유
인덱스의 필요성은 데이터의 양이 많을 수록 높아진다.
인덱스를 사용하지 않는 경우 원하는 데이터를 검색하고 조회하기 위해서는 모든 데이터를 조회하여 WHERE 절에 맞는 조건이 만족하는지 비교가 필요하다.
데이터 N에 대한 모든 비교가 필요하므로, 조회시 O(N)의 비용이 소모된다. 하지만 인덱스를 활용하는 경우, 모든 데이터를 비교하여 결과물을 찾지 않는다. 많이 사용되는 B+Tree를 활용한 인덱스를 정의하고 데이터를 검색하고 조회하는 경우는 O(logN)의 시간 복잡도를 갖게 된다.
즉, 인덱스를 사용하면 O(N)에서 O(logN)으로 조회 성능을 높힐 수 있다.
인덱스 관리
DBMS에서 인덱스는 정렬된 상태로 유지되어야 빠르게 값을 찾을 수 있다. 만약 인덱스가 존재하는 테이블에 Insert, Delete, Update를 수행하게 되면 해당 데이터에 대한 인덱스를 추가하거나 변경해야 한다.
- Insert : 인덱스를 추가한다.
- Delete : 해당 인덱스를 사용하지 않게끔 처리한다. (삭제하는 것이 아님)
- Update : 사용되는 데이터는 인덱스를 추가하고, 이전 데이터는 사용하지 않게끔 처리한다.
위와 같은 추가 연산이 진행되기 때문에 해당 작업이 빈번하게 발생된다면 그만큼 오버헤드가 발생하게 된다.
인덱스 사용시 주의사항
- 테이블에 write할 때마다 index에도 변경이 발생하기 때문에 update, insert, delete 시 주의해야 한다.
- 테이블의 인덱스는 삭제되지 않기 때문에 빈번하게 update, insert, delete가 발생하게 된다면 크기가 계속해서 커지게 된다. 따라서 인덱스에 의해 오히려 성능이 저하되는 결과를 초래할 수 있어 주의해야 한다.
- index도 테이블이기 때문에 추가적인 저장 공간이 발생한다.
- 이미 생성된 index로도 사용이 가능한데 불필요하게 index를 다시 생성하지 않도록 주의해야 한다.
Covering index
Index 내부에 조회하는 열이 모두 포함되어 있다면 실제 테이블까지 가서 비교할 필요가 없으므로 조회 성능이 높아진다. 때문에 의도적으로 Covering index를 만들어 사용하기도 한다고 한다.
Hash index
Hash index는 해시 테이블을 사용해 데이터를 인덱싱한다. 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 키를 해시 함수에 입력하면 고유 인덱스를 생성하고 해당 인덱스를 활용해 데이터를 저장하거나 조회하게 된다.
해시 테이블을 사용한 인덱스는 O(1)의 시간복잡도를 가져 굉장히 빠른 조회가 가능하다. 하지만 범위에 대한 비교가 불가능하고, 멀티 컬럼 인덱스의 경우 전체 열에 대한 조회만 가능하다. 또한 해시 테이블은 크기가 미리 정해져 있기 때문에 크기보다 더 값을 추가하고 싶다면 rehashing을 진행해야 한다. rehashing은 더 큰 크기의 새로운 배열을 만드는 과정이기 때문에 비용이 발생해 부담이 될 수 있다. 그리고 드물게 동일한 해시 값을 반환해 다른 데이터인 경우에도 동일한 값으로 처리될 수 있다.
장점이 명확한 만큼 단점도 명확하기 때문에 필요에 맞게 사용하는 것이 권장된다.
B+Tree
인덱스에서는 대부분 B-Tree 자료구조 기반을 사용한다. B-Tree는 Balanced Tree의 일종으로, O(logN)의 시간복잡도를 갖는다.
Balanced Tree를 사용하는 이유
다음과 같은 이진트리가 존재한다고 하면, 위 트리에서 조회시 최악의 시간복잡도는 O(N)이 된다. 가장 마지막에 존재하는 leaf node를 조회할 때 O(N)의 시간복잡도를 갖게 되는데, 이런 문제를 보완한 트리가 Balanced Tree이다.
Balanced Tree에는 AVL Tree, Red-Black Tree, B-Tree 등이 있다. Balanced Tree를 사용하면 위처럼 편향된 트리구조를 이루지 않아 O(logN)의 시간복잡도를 보장한다.
B+Tree를 사용하는 이유
그렇다면 Balanced Tree 중 왜 B+Tree를 사용하는 것일까? 같은 O(logN)의 시간복잡도를 가지는데, 왜 다른 Balanced Tree가 쓰이지 않고 B+Tree를 쓰게 되는지 의문이 생긴다.
이유를 알기 위해선 컴퓨터의 메모리 시스템를 알아야 한다.
컴퓨터는 주기억장치와 보조기억장치 데이터, 상태, 명령을 보관하기 위해 사용되는 장치를 말한다. 주기억장치와 보조기억장치의 차이점은 휘발성, 속도, 용량 등이 있는데, B+Tree를 사용하는 이유를 이해하기 위해선 주기억장치와 보조기억장치가 자동하는 원리를 이해할 필요가 있다.
주기억장치의 역할은 실행 중인 프로그램의 코드들과 실행에 필요한 데이터 등을 보관하고 결과 데이터들을 보관하는 곳이다. 그렇기 때문에 데이터가 영구적으로 기록되지 않는 휘발성 특징을 가진 주기억장치는 보조기억장치에 데이터를 영구적으로 저장한다. (주기억장치의 메모리가 부족하면 보조기억장치에 임시적으로 저장하기도 한다.)
보조기억장치는 저장 용량은 가장 크지만 주기억장치에 비해 보조기억장치는 데이터를 처리하는 속도가 느리며, 블록(block) 단위로 데이터를 읽고 쓴다. 블록 단위로 데이터를 읽고 쓴다는 것은 데이터가 필요할 때 해당하는 데이터만을 가져오는 것이 아닌, 해당 범위의 데이터를 가져온다는 의미이다.
여기서 주목해야할 점은 보조기억장치가 속도가 느리다는 점과 블록 단위로 데이터를 읽고 쓴다는 점이다. DB의 데이터 또한 보조기억장치에 저장되기 때문에 속도에 관련이 있다.
보조기억장치의 속도가 느리기 때문에, DB에서 필요한 데이터를 조회해야할 때 당연히 보조기억장치에 적게 접근하는 것이 성능면에서 좋다. AVL Tree와 같은 이진트리의 경우 시간복잡도는 O(logN)이라해도 트리의 레벨이 높다면 그만큼 보조기억장치에 접근하는 횟수도 늘어나게 되므로 성능면에서 효율적이지 않다.
하지만 B+Tree는 Tree의 레벨을 줄여 보조기억장치에 대한 접근을 줄이고, 블록 단위로 조회하는 보조기억장치의 특징을 사용해 하나의 노드 내부에 존재하는 다수의 데이터를 한번에 가져올 수 있다. 하나의 노드에 다수의 데이터를 저장할 수 있으며 자식 노드 또한 2개 이상으로 가질 수 있기 때문이다.
즉, 보조기억장치의 접근을 최소화한 B+Tree가 성능면에서 효율적이기 때문에 DB에선 대부분 B+Tree 기반 인덱스를 사용한다고 볼 수 있다.