[데이터 베이스] Index 정리
목차
1. 인덱스(Index)개념
2. 자료구조
3. 장단점
4. 설계
1. 인덱스(Index) 개념
저번시간에 배웠던 정규화가 DB 쓰기 관련 효율을 향상 시켰다면, 이번 시간에 다루는 인덱스는 DB의 읽기 성능을 향상시키는 방법이다. 인덱스(Index)란 테이블 컬럼의 검색 속도 향상을 위한 자료구조이다. 조회를 많이 하는 컬럼을 따로 복사해서 검색에 최적화된 자료구조로 만들어 놓고 조회시 해당 자료구조를 사용하여 빠르게 조회를 한다.
책의 목차를 생각하면 이해가 쉽다. 예를 들어, 네트워크 전공책에서 TCP/IP 내용을 찾고 싶다면 처음부터 끝까지 페이지를 넘겨가며 찾는 것 보다는 목차를 먼저 확인하고 해당 페이지로 이동을 할 것이다. 인덱스도 책의 목차와 마찬가지로 가이드를 통해 빠르게 값을 검색하게 된다.
인덱스(Index) = 테이블의 컬럼을 복사해서 빠른 검색이 가능하도록 만든 자료구조
인덱스를 사용하는 이유는 뭘까? 인덱스를 사용하지 않는다면 테이블 전체를 확인하는 전체 테이블 스캔(Full Table Scan)을 통해 검색을 하게 된다. 이렇게 되면 모든 데이터를 확인해봐야하기 때문에 선형시간이 걸리게 되며, 데이터가 많아질수록 검색에 많은 시간이 소요된다. 서비스 운영시 검색 요청이 가장 많은 만큼, 검색 시간을 줄일 필요가 있었으며, 이를 위해 인덱스라는 개념이 등장하였다.
전체 테이블 스캔을 하는데 걸리는 시간복잡도가 선형 시간인 O(N) 의 시간이 걸렸다면, 빠른 검색이 가능한 이분 검색 트리(Binary Search Tree) 등을 활용하여 O(logN)의 시간복잡도로 검색 시간을 단축시킨다.
실제 인덱스의 자료구조로 이분 검색 트리를 사용하지는 않고, 이분 검색 트리의 최상위버전인 B+Tree 라는 자료구조를 사용한다. B+Tree에 대해서는 [2. 자료구조] 부분에서 살펴보고, 일단은 '이분 검색 트리와 유사한 자료구조로 인덱스를 만들어서 검색을 빠르게 한다' 까지만 알고 넘어가자.
2. 자료구조
인덱스는 여러 자료구조를 통해 구현될 수 있으며, B+Tree 또는 해시테이블을 사용한다. MySQL, Oracle 등은 B+Tree를 통해 인덱스를 구현하고, MongoDB는 Hash Table을 사용하여 인덱스를 구현한다. 각 B+Tree와 해시테이블이 무엇인지 어떤 특징이 있는지 알아보자.
B+Tree
B+Tree(비플러스 트리)는 B-Tree(비트리)를 개선한 자료구조이며, B-Tree는 이분 검색 트리를 개선한 자료구조이다.
즉, [이분 검색 트리 -> B-Tree -> B+Tree ] 순으로 개선 되어 최종적으로 B+Tree를 인덱스의 자료구조로 활용한다. B+Tree를 알아보기에 앞서 하위 버전인 B-Tree에 대해 알아보자.
B-Tree
기존 이분 검색 트리가 부모 노드를 기준으로 좌,우에 자식 노드를 최대 하나씩 가졌다면, B-Tree는 자식 노드로 최대 M개 가질 수 있도록 하여 더 빠른 검색을 할 수 있게 하였다. 또한, M의 값은 구현에 따라 달라질 수 있으며, 최대 M개의 자식 노드를 갖는 B-Tree를 M차 B-Tree 라고 한다.
기존 이분 검색 트리에 비해 성능은 좋으나, WHERE age>14 AND age<20 이러한 범위가 주어지면, 각 값에 대해 개별적으로 트리에 접근을 해야하는 단점을 가지고 있다.
B-Tree 정리
1. 최대 M개의 자식 노드를 가질 수 있다.
2. 모든 노드에 데이터와 포인터가 들어있다.
3. 각 값 마다 이진트리를 순회해야한다.
B+Tree
이 문제를 개선한 자료구조가 B+Tree 이다. B+Tree는 리프노드에만 값을 두고 리프 노드들을 Linked List로 연결하여 범위에 대한 처리를 빠르게 한 자료구조이다. 중간 노드에는 데이터는 저장하지 않고 포인터만 존재한다.
B+Tree 정리
1. 최대 M개의 자식 노드를 가질 수 있다.
2. 리프노드에만 데이터가 들어가 있으며, 중간노드에는 포인터만 존재한다.
3. 리프노드끼리 Linked List로 연결되어 있어서 부등호 연산(< ,>)에 효율적이다.
Hash Table
해시테이블은 {key: value} 쌍으로 저장되는 자료구조이다. 인덱스로 활용할 때는 컬럼에 해당하는 값을 해시함수로 변환하여 key를 만들고, value에 튜플의 참조값이 들어가게 된다. 이렇게 함으로써 특정 값을 검색할 때, 해시함수로 키를 변환하여 해당 튜플에 접근할 수 있게 된다.
해시함수를 사용한 인덱스의 특징을 정리하면 아래와 같다.
1. 삽입, 검색, 삭제 - 시간복잡도 O(1)
>> B-Tree, B+Tree 보다 빠르다
>> 최악의 경우(해시 충돌 발생) O(N)
2. B+Tree와 달리 부등호(< , >)에 대해 성능이 좋지 않다.
>> (=)에 대해서만 빠르다.
>> 그렇기 때문에 부등호 관계를 많이 사용하는 RDMBS에서는 B+Tree를 사용
3. 장단점
지금까지 인덱스의 개념과 어떤 자료구조를 갖는지 알아보았다. 검색을 빠르게 해주기 때문에 마냥 좋아보이지만 단점도 존재한다. 이번 챕터에서는 인덱스의 장단점을 간단하게 정리하고 넘어가겠다.
장점
1. 테이블 검색 속도를 향상시킨다.
2. 시스템 부하를 줄일 수 있다.단점
1. 인덱스를 저장하기 위한 추가 공간 필요하다.
>> 컬럼을 복사하여 검색에 최적화된 자료구조를 만드는 것이기 때문에 공간을 차지한다.
2. 삽입, 갱신, 삭제가 빈번하면 성능이 저하된다.
>> 기존 테이블과의 동기화를 위해 인덱스도 업데이트 해줘야하며 이때 비용이 발생한다.
4. 인덱스 설계
인덱스를 사용하면 검색을 빠르게 할 수 있는 반면, 삽입· 갱신· 삭제가 빈번하게 일어나는 경우 성능이 저하된다. 인덱스를 효율적으로 사용하기 위해 어떻게 하면 좋은지를 알아보자.
사용하면 효율적인 경우
1. 규모가 큰 테이블
2. JOIN, WHERE, ORDER BY 자주 사용되는 컬럼
3. INSERT, UPDATE, DELETE 자주 발생하지 않는 컬럼
4. 데이터 중복도가 낮은 컬럼(카디널리티가 높은 컬럼)
>> 카디널리티 : 고유한 값의 수(유니크한 값의 수)
5. Select 자주 사용하는 컬럼들 조합
주의 사항
1. 단일 테이블에 인덱스가 많으면 성능이 느려진다(테이블당 4~5개 권장).
2. 데이터 변경이 얼마나 자주 일어나는지 고려해야한다.
3. 사용하지 않는 인덱스는 제거한다.
4. 검색할 데이터가 전체의 20% 이상이면 인덱스를 사용하지 않는다.
>> Index 손익분기점 : 10%~15% 이내의 데이터 출력시 Index를 거치는 것이 효율적이다.
정리
인덱스란 - 특정 컬럼의 빠른 검색을 위해 복사후 검색에 최적화한 자료구조
장점
1. 검색의 속도를 향상시킨다.
2. 전체적인 시스템 부하를 감소시킨다.
단점
1. 인덱스를 위한 별도의 추가 공간이 필요하다.
2. 삽입,갱신,삭제가 빈번할 경우 성능이 저하된다.
자료구조
1. B+Tree
>> 여러개의 자식노드를 가지는 트리이며 리프노드만 데이터를 갖는다.
>> 리프노드는 Linked List로 연결되어 있다.
>> O(logN)의 시간복잡도를 가진다.
>> 부등호 연산(<,>)에 유리하다.
2. Hash Table
>> { key : value } 쌍의 데이터 모음
>> 해시함수로 컬럼 값을 변환하여 key로 사용하며, 튜플의 참조값을 value로 가짐.
>> O(1)의 시간복잡도를 가지며 해시 충돌 시 O(N)이 걸린다.
>> 등호(=) 연산에만 유리하고 부등호 연산(=)의 이점은 없다.
# 사용하면 좋은 상황
1. JOIN, WHERE, ORDER BY 자주 사용하는 컬럼
2. INSERT, UPDATE, DELETE 사용이 빈번하지 않은 컬럼
3. 데이터의 중복도가 낮은 컬럼(카디널리티가 높은 컬럼)
4. 규모가 큰 테이블
[참고 링크]
https://jojoldu.tistory.com/243?category=761883
https://mangkyu.tistory.com/96
https://coding-factory.tistory.com/746