[Database] 인덱스(Index)

foresec·2023년 6월 20일

Computer Science

목록 보기

5/28

DB Index

1. 목적

RDBMS에서 검색 속도를 높이기 위한 기술
Table의 Column을 색인화함
-> 해당 Table의 Record를 Full scan하지 않음
-> 색인화된(B+Tree) 구조로 Index 파일 검색으로 검색 속도 향상

2. 과정

테이블을 생성하면 MYD, MYI, FRM 3개의 파일이 생성됨

FRM : 테이블 구조가 저장된 파일
MYD : 실제 데이터가 있는 파일
MYI : Index 정보가 들어가 있는 파일

인덱싱하는 경우 비워져있더 MYI가 생성됨
사용자가 Select 쿼리로 Index를 사용하는 Column을 탐색 시, MYI 파일의 내용을 검색

3. 장점 및 단점

장점

테이블을 검색하는 속도와 성능이 향상됨
그에 따라 시스템의 전반적인 부하를 줄임
(인덱스로 인해 데이터들이 정렬된 형태를 가짐)

단점

인덱스 관리용 추가 작업이 필요
ex) INSERT(새로운 데이터에 대한 인덱스를 추가), DELETE (삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행), UPDATE(기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가)
추가 저장 공간 필요
데이터의 인덱스를 제거하는 것이 아니라 사용하지 않음으로 처리하고 남겨두기 때문
잘못 사용하는 경우 오히려 검색 성능 저하
전체 데이터의 10 ~ 15% 이상의 데이터를 처리하거나 데이터의 형식에 따라 성능이 낮아질 수 있음
ex) 성별의 경우 값의 range가 적기 때문에 인덱스를 읽고 나서 다시 많은 데이터를 조회하기 때문에 비효율적

4. Index 사용이 용이한 경우

규모가 큰 테이블
INSERT, UPDATE, DELETE 작업이 자주 발생하지 않는 컬럼
WHERE나 ORDER BY, JOIN 등이 자주 사용되는 칼럼
데이터의 중복도가 낮은 컬럼

+) B+Tree

B-Tree와 B+Tree

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이나, 모든 데이터를 한번 순회하는데는 트리의 모든 노드를 방문해야하므로 비효율적임. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장
또한, B+Tree는 반드시 leaf node에서만 데이터가 저장되기 때문에 중간 nodeㅔ에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있음

그 외 대표적인 예로 해시테이블도 있음

장점 및 단점

장점

leaf node를 제외하고 데이터를 저장하지 않아 메모리가 확보됨. 즉, node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아져 검색 속도를 높일 수 있음
Full Scan시 leaf node에만 데이터가 저장되어 있고, leaf node끼리 Linked list로 연결되어 있어 선형시간(O(n))이 소모됨