인덱스
인덱스는 데이터베이스의 테이블에 대한 검색속도를 향상시키는 기능이자 자료구조입니다.
대부분의 DB에서 이 기능을 지원합니다.
보통 책의 맨 끝부분에 있는 찾아보기 페이지와 비슷하다고 볼 수 있습니다.
만약 우리가 특정 내용을 찾아보려고 했을때 찾아보기 페이지가 없었다면 우리는 책의 모든 내용을 쭉 훑어봐야 합니다.
이를 DB와 비교해 본다면
인덱스는 찾아보기 페이지이며 모든 내용을 쭉 훑어 보는 행위가 Full Table Scan입니다.
※ Full Table Scan
Full Table Scan은 말 그대로 테이블의 데이터들을 모두 스캔한다는 의미입니다.
Full Table Scan은 순차적으로 접근 하기 때문에 접근 비용이 감소됩니다.
Full Table Scan은 적용 가능한 인덱스가 없거나 처리 범위가 넓거나, 크기가 작은 테이블에 엑세스 하는 경우에 사용합니다.
인덱스는 메모리나 특정 공간에 B-Tree 형태로 저장되게 됩니다 ( 제품마다 다를 수 있습니다. )
※ B-Tree
B-Tree는 탐색 성능을 높이기 위해 높이를 항상 균형있게 유지하는 Balanced Tree의 일종입니다.
모든 leaf node가 같은 level로 유지되도록 자동으로 밸런스를 맞추게 됩니다.
여기서 자식 node의 개수가 2개 이상이며, node 내의 키가 1개 이상일 수 있습니다.
node의 자식 수 중 최댓값이 n이라면 n차 B-Tree라고도 합니다.
B-Tree의 조건은 아래와 같습니다.
1. node의 key의 수가 k개라면, 자식 node의 수는 k+1개 입니다.
2. node의 key는 반드시 정렬된 상태여야 합니다.
3. 자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 나뉘게 됩니다.
4. Root node는 항상 2개 이상의 자식 node를 갖습니다. 단 Root node가 leaf node인 경우 제외
5. 모든 leaf node들은 같은 level에 있어야 합니다.
그렇다면 왜 B-Tree가 탐색에 있어 빠를까요?
만약 위와 같은 B-Tree가 존재한다고 가정해 봅시다.
여기서 35를 찾는다고 가정 하면 아래와 같은 순서를 밟습니다.
1. 하향식으로 루트 노드부터 대소 관계를 구별합니다 ( 20 < 35 < 40 )
2. 35는 20과 40 사이에 존재하기 때문에 그 사이의 자식 포인터를 타고 이동합니다.
3. 30, 35, 33을 비교합니다.
4. 35는 33보다 크기 때문의 33의 자식노드로 들어가고 35를 찾을 수 있게 됩니다.
위와 같이 B-Tree는 탐색도 빠를 뿐만 아니라 항상 좌,우 자식 노드 개수의 밸런스를 유지하기 때문에 최악의 경우에도
O(logN)의 시간복잡도를 가지기 때문에 대용량의 테이블에서도 어느정도의 성능을 예상할 수 있습니다.
하지만 좋아 보이는 기능도 항상 Trade off가 있기 마련
인덱스는 아래와 같은 단점이 있습니다.
1. 다른 기능의 성능이 떨어집니다.
- 인덱스는 데이터 조회에만 특화되어 있고 B-Tree를 기반으로 동작하기 때문에 INSERT / UPDATE / DELETE 성능에 영향을 미치게 됩니다. 위 세가지 동작은 데이터의 변경점이 생기기 때문에 인덱스를 재정렬하는 등의 추가 작업이 필요하므로 성능이 떨어지게 됩니다.
2. 추가 저장 공간이 필요합니다.
- 인덱스는 DB에 저장된 데이터의 주소를 인덱스의 Key값으로 가지기 위해 별도 공간이 필요하게 됩니다. 전체 테이블 영역의 30 ~ 50%까지 잡아 놓을 만큼 저장 공간이 꽤나 필요합니다.
위와 같은 단점 때문에 인덱스는
규모가 큰 테이블,
데이터의 Range가 넓고, 중복도가 낮은 컬럼,
조회가 주이거나 정렬된 상태가 유용한 컬럼,
INSERT, UPDATE, DELETE 작업이 자주 발생하지 않는 컬럼
WHERE이나 ORDER BY, JOIN 등에 자주 사용되는 컬럼에 적용하는 것이 유리합니다.