INDEX란 ?
인덱스(index) 데이터베이스에서 테이블의 조회 및 검색을 더 빠르게 할 수 있는 자료구조이다.
INDEX 사용 이유?
결론 : 조회 및 검색을 빠르게 해서 성능 향상
SELECT문을 사용하여 원하는 조건의 데이터를 검색할 때, 저장된 데이터의 양이 엄청나게 많다면 검색을 위한 순회에 많은 자원과 시간이 소모될 것이다. 이때 도움이 되는게 인덱스이다.
자주 조회되는 Column 에 대한 Index Table을 따로 만들어 SELECT 문이 들어왔을 때 Index 테이블에 있는 값들로 결과 값을 조회해 온다.
그래서 Index를 잘 사용한다면 "검색" 연산을 실행했을 때 성능을 올릴 수 있게 된다.
INDEX가 없다면?
인덱스를 사용하지 않으면, 데이터를 탐색할 때 풀 테이블 스캔(Full Table Scan)이 발생한다. 사용자가 원하는 데이터를 찾기 위해 테이블에 존재하는 모든 행을 읽어내는 방법이다.
풀 테이블 스캔: 풀 테이블 스캔은 전체 데이터를 탐색하므로, 디스크에서 데이터를 읽어 메모리로 적재하는 IO 비용이 많이 발생하는 가장 느린 테이블 스캔 방식이다.
풀 테이블 스캔은 테이블에 인덱스가 존재하지 않거나, 인덱스가 존재한다고 하더라도 데이터베이스의 옵티마이저(Optimizer)가 인덱스 대신 풀 테이블 스캔으로 탐색하는 것이 더 적절하다고 판단할 때 수행된다.
동작
Index Table에서 where에 포함된 값을 검색합니다.- 해당 값의
table_id PK(Primary Key)를 획득합니다.- 가져온
table_id PK값으로 원본 테이블에서 값을조회합니다.
DBMS(Database Management System)은 인덱스를 다양한 알고리즘으로 관리를 하고 있는데 일반적으로 사용되는 알고리즘은 B+ Tree 알고리즘이다.
INDEX의 장점과 단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
만약
CREATE,DELETE,UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.
인덱스 대상 컬럼 선택 기준, 카디널리티
인덱스 대상 컬럼은 카디널리티(cardinality)가 높은 컬럼을 우선적으로 선택해야 유리하다. 카디널리티란 데이터 집합에서 유일한 데이터의 개수를 의미합니다.
예를 들어 대한민국 국민 테이블을 인덱싱할때 카디널리티가 낮은 성별 컬럼 대신 카디널리티가 높은 주민번호 컬럼을 인덱싱 하는 것이 바람직한다.
INDEX 사용시 주의할 점
인덱스는 따로 테이블의 형태로 관리가 된다. 자원을 소모한다는 의미. 때문에 무분별한 인덱스의 사용은 성능에 부정적인 영향을 미칠 수 있다.
- 인덱스는 이진트리를 사용하기 때문에 기본적으로
정렬되어 있다. 이로인해검색과조회의 속도를 향상시킬 수 있지만- 주의!! 잦은 데이터의 변경(삽입, 수정 삭제)가 된다면 인덱스 데이블을 변경과 정렬에 드는 오버헤드 때문에 오히려 성능 저하가 일어날 수 있다.
INSERT : 테이블에는 입력 순서대로 저장되지만, 인덱스 테이블에는 정렬하여 저장하기 때문에 성능 저하 발생
DELETE : 테이블에서만 삭제되고 인덱스 테이블에는 남아있어 쿼리 수행 속도 저하
UPDATE : 인덱스에는 UPDATE가 없기 때문에 DELETE, INSERT 두 작업 수행하여 부하 발생
데이터의 중복이 높은 컬럼(카디널리티가 낮은 컬럼)은 인덱스로 만들어도 무용지물 (예: 성별)
다중 컬럼 인덱싱할 때 카디널리티가 높은 컬럼->낮은 컬럼 순으로 인덱싱해야 효율적입니다.
B+tree 알고리즘
B+tree 알고리즘이란?
특징
- 바이너리 트리와 개념적으로 비슷
- key 값으로 정렬되어 있다.
- childern 노드가 여러개이다.
- 각 노드가 메모리가 아닌 디스크에 저장한다.
- 데이터는 leaf 노드에만 있다.
- 각 노드에 sibling(형제)으로 가는 포인터가 있다.
[더 자세한 특징 설명]
리프 노드에만 데이터 저장: B+ 트리의 리프 노드에는 실제 데이터만 저장되고, 키 값은 인덱스 역할을 수행합니다. 이는 데이터베이스의 범위 검색과 정렬된 결과 반환에 유리합니다.키 값의 중복을 허용하지 않음: B+ 트리는 키 값의 중복을 허용하지 않습니다. 각 키 값은 유일해야 합니다.리프 노드 간의 연결: B+ 트리의 리프 노드는연결 리스트 형태로 연결되어 있어 범위 검색과 순차 접근에 효율적입니다.
B+tree 알고리즘 왜 사용하는가?
[선형탐색]
[B-Tree]
B-Tree는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점이 있습니다.
즉, 모든 데이터를 순회하는 경우, 모든 노드를 방문해야해서 비효율적입니다.
이러한 단점을 해소하고자 B+Tree는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibiling(동기) node는 연결리스트 형태로 이어져 있습니다.
B+tree 장단점
장점
효율적인 탐색: B+ 트리는 균형 잡힌 트리로서, 모든 리프 노드까지 도달하기 위한 경로의 길이가 동일합니다.(데이터 탐색 시간복잡도 O(log N))
범위탐색 유리: leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리함
순차 액세스 성능: B+ 트리의 리프 노드는 연결 리스트로 구성되어 있으며,순차 액세스(Sequential Access)를 지원합니다.
단점
B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함
메모리 요구량: B+ 트리는 대부분의 중간 노드를 메모리에 유지해야 하므로, 메모리 요구량이 크다는 단점이 있습니다. 트리의 크기가 커질수록 메모리 사용량도 증가하므로, 메모리 제약이 있는 환경에서는 문제가 될 수 있습니다.
공간 사용 비효율성: B+ 트리는 각 노드마다 포인터와 키 값을 저장해야 합니다. 이로 인해 트리의 크기가 실제 데이터 크기보다 커지며, 디스크 공간의 낭비를 초래할 수 있습니다.
더 자세한 B+ Tree
Reference & Additional Resources
