[Database] Index

Index

Index란?

• Index는 DB 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조
• 특정 컬럼에 Index를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장
• Index를 생성한 컬럼에 WHERE 조건을 거는 경우, Full scan을 통해 데이터를 조회하지 않고 Index에 저장된 데이터의 물리적 주소로 통해 데이터를 조회하게 됨 → 적은 I/O 사용으로 검색 속도 향상

 

Index 사용 시 장점

• 데이터가 정렬 되어있다는 점을 활용하여, 검색을 효율적으로 할 수 있음
• WHERE 절 수행 시, Index는 정렬되어 있는 상태임으로 조건에 맞는 데이터를 빠르게 찾아낼 수 있음
• ORDER BY 절 수행 시, Index에 데이터가 정렬되어 있기 때문에 추가적인 정렬 과정을 피할 수 있음
• MIN, MAX 수행 시, Full scan 없이 Index를 통해 처음과 끝 값만 가져오면 됨

 

Index 사용 시 주의점

인덱스 컬럼의 가공

• 인덱스 컬럼을 조건절에서 가공하면 정상적으로 인덱스를 사용할 수 없음 (부정형 비교도 마찬가지) → 가공할 경우 range scan이 아닌 full scan으로 작동됨

# 조건절의 인덱스 컬럼을 변경한 경우 
WHERE age * 10 > 20

# 다음과 같이 컬럼 그대로 사용 
WHERE age > 20 / 10

인덱스 컬럼의 개수

• DML 작업(insert, delete, update)이 빈번한 테이블에는 인덱스를 생성하지 않는 것이 좋음 → 데이터가 수정될 때마다 인덱스를 정렬해야 되기 때문
• 단일 테이블에 인덱스가 많으면 속도가 느려짐 (테이블 당 4~5개 정도 권장)

인덱스 컬럼 사용

• 검색할 데이터가 전체 데이터의 20% 이상이면 인덱스 사용하지 않음 → 데이터 페이지의 대부분을 읽어야 하고, 인덱스 관련 페이지도 읽어 작업량이 크기 때문
• 검색할 데이터가 전체 데이터의 10%~25% 정도일 때 인덱스를 사용하는 것이 효율적이고 그 이상이면 full scan이 더 빠름

인덱스 중복

• 아래 예시처럼 idx3 선두 컬럼이 idx1과 idx2를 포함하는 경우 인덱스 중복이라고 함
• idx1과 idx2는 불필요한 인덱스 → 인덱스가 많으면 속도가 느려지기 때문에 불필요한 인덱스는 삭제하는 것이 필요

CREATE TABLE tbl (
		a INT PRIMARY KEY,
		b INT,
		c INT,
		d INT 
);

# 인덱스 중복 
CREATE INDEX idx1 ON tbl(a,b);
CREATE INDEX idx2 ON tbl(a,b,c);
CREATE INDEX idx3 ON tbl(a,b,c,d);

# 해당 인덱스만 남기고 나머지 삭제 
CREATE INDEX idx3 ON tbl(a,b,c,d);​

 

Index의 종류

Clustered Index

• 테이블 전체가 정렬된 Index가 되는 방식
• Index로 지정한 Column을 기준으로 실제 물리적인 데이터 페이지가 정렬됨
• 각 페이지는 고유의 페이지 번호를 가지고 있음
• Clustered Index는 테이블 당 하나만 생성할 수 있음
• 데이터가 많이 저장된 상태에서 ALTER를 통해 Clustered Index를 추가한다면, 많은 데이터를 정렬해야 해서 많은 리소스를 사용

Non-Clustered Index

• 정렬된 별도의 Index 페이지를 생성하고 관리
• Index 페이지와 데이터 페이지는 구분되어 있음
• index 페이지는 Index로 지정한 Column을 기준으로 정렬됨
• index 페이지의 Leaf Node는 데이터 페이지의 특정 행을 가리키는 데이터 페이지 번호 + #오프셋를 가짐
• 실제 데이터 페이지는 정렬되지 않으므로 Clustered Index에 비해 삽입, 수정, 삭제 작업이 비교적 빠름

차이점

• clusterd index는 index 페이지에 실제 데이터를 가지고 있지만, non-clustered index는 데이터의 주소 값을 가지고 있음
• clustered index는 실제 데이터가 정렬되어 있지만, non-clustered index는 실제 데이터가 정렬되어 있지 않음

B+tree 구조

• DBMS에서 보편적으로 사용되는 Index 구조로 자식 노드가 2개 이상인 트리
• Root Node(기준)/Branch Node(중간)/Leaf Node(말단)으로 구성되며 계층적 구조
• 상위 노드의 값보다 작은 값은 왼쪽 하위 노드에 저장하고, 큰 값은 오른쪽 하위 노드에 저장
• Root Node과 Branch Node에는 key만 두고, data는 담지 않음
• Leaf Node에만 key와 data를 저장
• Leaf Node는 양방향 연결 리스트로 앞뒤 Node에 대한 주소 값을 가짐
• 하나의 노드는 데이터베이스에서 하나의 페이지(블록)에 해당

Unique Scan과 Range Scan

수직적 탐색

• Root Node에서 Leaf Node까지 수직적으로 내려가며 데이터를 찾는 과정
• 인덱스 스캔 시작 지점을 찾을 때 사용

 

수평적 탐색

• 수직적 탐색을 통해 찾은 인덱스 스캔 시작 지점에서 시작하여, 찾고자 하는 데이터를 모두 찾을 때까지 Leaf Node를 수평적으로 스캔
• 검색 조건에 일치하지 않는 데이터를 만나면 탐색 종료

 

Unique Scan

• 수직적 탐색으로 조건에 해당하는 데이터를 하나만 찾음
• index로 지정한 column이 unique해야 함 → column에 중복값이 있을 경우 Range Scan

<Unique Scan 예시>

• index는 a이고 “Select * from tbl where a = 2”를 수행할 때

1. 수직적 탐색으로 데이터 찾기

 

Range Scan

• 수직적 탐색으로 인덱스 스캔 시작점을 찾은 후, 수평적 탐색으로 조건에 해당하는 데이터를 찾음

<Range Scan 예시>

• index는 a이고 “Select * from tbl where a between 2 and 7”를 수행할 때

1. 수직적 탐색으로 인덱스 스캔 시작점 찾기

1. 수평적 탐색으로 데이터 찾기

 

 

참고:

https://hudi.blog/db-index-and-indexing-algorithms/

https://hudi.blog/db-clustered-and-non-clustered-index/

https://blog.naver.com/hgstudy_/222523205918

https://velog.io/@alicesykim95/DB-%EC%9D%B8%EB%8D%B1%EC%8A%A4Index%EB%9E%80

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree