Index ?
추가적인 작업 (write)과 저장 공간을 활용하여 데이터 베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
인덱스를 활용하면, 데이터를 조회하는 SELECT, UPDATE, DELETE 성능 함께 향상되지만,만일 index 사용하지 않는 컬럼을 조회해야 한다면 전체를 탐색해야 하는 Full table scan을 진행해야 하며 하나의 데이터 탐색을 위해 전체 테이블을 확인해야 하는 과정은 상당히 비효율적이다.
장점
- WHERE 절의 효율성 증대
- ORDER BY에 의한 SORT 과정 피할 수 있음
- MIN, MAX 값에 대해 효율적인 처리 가능
- 시스템 부하 줄일 수 있음
- 테이블 ROW의 고유성 강화 가능
단점
- 인덱스 관리를 위해 DB의 10%에 해당하는 저장공간 필요 (공간복잡도가 올라가는 문제 발생)
- 인덱스 관리 위해 추가적인 작업 필요 (정렬된 상태 유지 필요)
- 인덱스 잘못 사용 시 오히려 성능 저하되는 역효과 발생 가능
DBMS 내에서 인덱스 관리는?
항상 최신 정렬된 상태를 유지해 원하는 값을 빠르게 탐색하도록 한다. 인덱스가 이미 적용된 컬럼에 다음과 같은 연산을 추가적으로 진행해 오버헤드가 발생하게 된다.
- SELECT : 새로운 데이터에 대한 인덱스를 추가
- DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
- UPDATE : 기존의 인덱스를 사용하지 않음 처리 후 갱신된 데이터에 대해 인덱스 추가
위 연산이 자주 일어나는 attribute에 인덱스를 사용하게 되면 인덱스 크기가 매우 커져 성능이 저하되는 경우가 발생함.
따라서, 사용되지 않는 인덱스는 바로 제거해주는 것이 좋고
다음과 같은 경우에 인덱스를 사용하면 좋다!!!
- 규모가 작지 않은 테이블
- 삽입, 갱신, 삭제가 자주 발생하지 않는 Column
- JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼 (기준이 되는)
- 데이터의 중복도가 낮은 컬럼
Index 자료구조
1) Hash Table
Hash Table 기반의 DB 인덱스는 (데이터=col값, 데이터위치)를 사용하여 컬럼 값으로 생성된 해시를 통해 인덱스를 구현한다.
그러나, 해시가 등호 연산에만 특화되어 있어 부등호 연산이 자주 사용되는 DB 검색에는 해시 테이블이 적합하지 않다.
2) B-Tree
Binary search tree와 유사, key값을 이용해 찾고자 하는 데이터를 tree구조로 찾는 것.
한 노드 당 여러 데이터 저장 가능.
각 노드 내 데이터는 정렬된 상태이고 자식 노드는 (N+1)개
각 노드에는 여러 KEY를 가지고 있고, Key에 대응하는 데이터도 존재장점
- 항상 O(logN) / 균일성 (어떤 값에 대해서도 항상 정렬되어있기에 같은 시간에 결과를 얻음)
- 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능
- 균형 트리 (root ~ leaf 까지 거리가 일정한 트리 구조)
단점
- 생성 처음에는 균형 트리이지만, 테이블 (삽입, 갱신, 삭제)등의 변경의 반복을 통해 균형이 깨지게 되고 성능이 약화된다. 이를 해결하기 위해 인덱스 재구성을 통해 트리의 균형을 되찾는 작업이 반드시 필요한데, 이는 트리 깊이가 깊어지고, overhead가 커지게 되는 문제가 발생한다.
- Sequential access에 취약하다. (B-Tree는 하향식으로 데이터를 찾아가기에 복잡함.)
- 어쨌든 모든 데이터를 한 번 순회하여 데이터를 찾아야 함.
3) B+Tree
- B-Tree의 문제를 보완하기 위해 등장
leaf node에만 인덱스와 함께 데이터를 저장하고 나머지 노드들은 데이터를 위한 인덱스(key)만 갖는다.
leaf node들은 LinkedList로 연결되어 있다.
B+Tree에선 반드시 leaf node에만 데이터가 저장되기에 중간 node에서 key를 올바르게 찾기 위해 key 즉, 인덱스가 중복될 수 있다.장점
- leaf node 제외하고 데이터 저장이 없기에 메모리를 더 확보할 수 있다.
- 한 노드에 더 많은 포인터를 가질 수 있으므로 트리는 더 얕아져 검색 속도가 빠른 편
- Full scan의 경우 B-Tree 보완. 최상의 경우만 비교하면 B-Tree는 루트노드에서 발견할 수 있는 한편, B+Tree는 leaf노드까지 가야할 수도 있음.
- 부등호 연산 등 문제 보완 부분이 많아 현재 RDBMS에서 가장 많이 사용하는 기본적인 자료구조
검색과정은 B-Tree와 동일하지만, 삽입, 삭제의 경우 B-Tree와 차이를 보인다.
삽입 / 삭제 비교
- 1) 삽입의 경우 (key 수가 최대보다 적은 leaf node에 삽입되는 경우)
1) 삽입의 경우 (key 수가 최대인 leaf node에 삽입되는 경우)
2) 삭제의 경우 (key가 leaf 노드 가장 앞에 위치하는 경우)
Fractal-Tree 알고리즘
- B-Tree의 단점을 보완하기 위해 고안된 알고리즘으로 독점적인 특허로 등록되어 MySQL의 스토리지 엔진인 TokuDB에 적용되어 있다.
- B-Tree 인덱스에서 인덱스 키를 검색하거나 변경하는 과정 중에 발생하는 가장 큰 문제는 디스크의 랜덤 I/O가 상대적으로 많이 필요하다는 것인데 Fractal-Tree에서는 이러한 점을 최소화하고, 이를 순차 I/O로 변환해서 처리할 수 있다.
- 즉, 값을 변형하지 않고 인덱싱하며 범용적인 목적으로 사용할 수 있는 측면에서 B-Tree와 거의 유사하지만 데이터가 저장되거나 삭제될 때 처리 비용을 상당히 줄일 수 있게 설계된 것이 특징이다.
- 인덱스 키가 추가되거나 삭제될 때 B-Tree인덱스보다 더 많은 정렬 작업이 필요하며, 이 때문에 더 많은 CPU처리가 필요할지 모르지만 인덱스의 단편화가 발생하지 않도록 구성할 수 있고, 인덱스의 키값을 클러스터링 하기 때문에 B-Tree보다는 대용량 테이블에서 높은 성능을 보장한다.
- 평균적인 처리 능력이 이론적으로 B-Tree보다 400배 가량 빠르며, 실제로 TokuDB의 키 추가 및 삭제작업은 InnoDB보다 100배 가량 빠른 처리 속도를 보여준다.
- 하지만 InnoDB보다 동시성처리가 불안정하다는 단점이 있다.
