RDB Index

1. 개념

1.1. 랜덤I/O vs 순차I/O

랜덤I/O

헤드가 디스크의 여러 위치로 빠르기 이동해야 하기 떄문에 탐색 시간이 길어집니다. 비연속적인 위치에서 데이터를 읽거나 쓰는 방식으로 성능이 저하됩니다. 데이터가 디스크의 여러 위치에 흩어져 있을 때 주로 발생합니다

• 데이터를 읽고 쓰는 위치가 임의적. 디스크 헤드 이동이 많이 발생하고 디스크 회전 대기 시간이 길어질 수 있습니다.

• 특정 위치에 빠르게 접근하여 데이터를 처리할 수 있으므로 소량의 데이터를 여러 곳에서 읽어야하는 경우 유리합니다. (단, 필요로 하는 데이터의 위치를 알고 있다면)

• 물리적 디스크의 특성상, I/O 성능이 낮아질 수 있습니다. HDD에서는 랜덤 접근이 비효율적입니다.

순차I/O

헤드가 디스크에서 연속적으로 데이터를 읽기 떄문에 탐색 시간이 줄어들어 성능이 훨씬 빠릅니다. 연속적인 데이터 블록을 순서대로 읽거나 쓰는 방식으로, 디스크에 저장된 데이터가 연속적인 위치에 저장되어 있을 때 주로 발생합니다.

• 데이터를 순차적으로 처리하므로, 디스크 헤드가 한번에 긴 데이터 블록을 읽거나 쓸 수 있어서 I/O 효율성이 높습니다.

• 대용량 데이터를 빠르게 처리할 수 있으며, 성능이 매우 우수합니다. 일반적인 HDD나 SSD 모두 순차I/O에서 높은 성능을 보입니다.

• 특정 위치에 있는 데이터를 즉시 접근하기 보다는, 전체 데이터 흐름을 따라 읽거나 써야 하기 떄문에 유연성이 떨어질 수 있습니다.

1.2. 인덱스

인덱스는 데이터베이스에서 검색 성능을 높이기 위해 사용되는 자료 구조입니다. 인덱스가 없으면 풀 테이블 스캔이 발생하지만, 인덱스를 사용하면 인덱스를 통해 필요한 레코드의 위치를 빠르게 조회합니다.

인덱스는 주로 B-트리 구조로 구현되며, 이는 균형 잡힌 트리로서 삽입, 삭제, 검색 시 일정한 성능을 보장합니다. 하지만 인덱스는 삽입, 수정, 삭제 작업 시 추가적인 오버헤드를 발생시킵니다.

2. 동작 방식

2.1. B- 트리

• 균형 이진 트리와 비슷하지만, 각 노드가 여러 개의 자식 노드를 가질 수 있는 구조.

• 삽입, 삭제, 검색이 log(n)의 시간 복잡도

• 내부 노드에는 해당 노드의 키 값과, 자식 노드로 이동하기 위한 포인터가 포함. 검색 대상이 내부 노드의 키 값에 맞는 경우에는 리프 노드까지 가지 않고도 데이터를 얻을 수 있습니다.

• 범위 검색시 logn * n의 시간 복잡도

2.2. B+ 트리

• 균형 이진 트리와 비슷하지만, 각 노드가 여러 개의 자식 노드를 가질 수 있는 구조.

• 삽입, 삭제, 검색이 log(n)의 시간복잡도

• 모든 리프 노드는 양방향 연결 리스트 형태로 연결되어 있어서, 범위 검색의 단일 레코드를 찾게 되면 연속해서 데이터를 읽기가 효율적입니다.

• 범위 검색시 logn + k의 시간 복잡도

• 내부노드에 해당 키 값을 저장하지 않기때문에, 해당 키 값을 저장하는 공간에 더 많은 리프노드의 주소들을 저장할 수 있습니다. 결국 같은 양의 데이터를 저장하기 위한 트리의 높이가 더 낮아지고, 데이터를 찾기 위해 디스크를 접근하는 횟수도 줄어듭니다.

2.3. 해시

• 해시 인덱스라 부르고, 해시 테이블은 해시 인덱스에서 사용되는 자료 구조.

• 특정 값에 대해 해시 함수를 적용하여 데이터가 저장된 위치를 빠르게 찾는 방식입니다. 이 방식은 정확한 값을 검색할 때 매우 효율적이지만, 범위 검색에는 적합하지 않습니다.

• 입력된 키 값을 기반으로 고유한 해시 값을 계산하고, 계산된 해시 값은 특정 버킷에 매핑됩니다.

• 단일 검색시 O(1)의 시간 복잡도 (인덱스 접근 → 버킷 접근 → 레코드 확인)

• 범위 검색시 계속된 랜덤I/O 검색으로, B+트리의 순차I/O보다 오버헤드 존재하기 떄문에 비효율적.

• 해시 충돌 해결 방법: 체이닝 & 오픈 어드레싱(다른 빈 버킷을 찾아 데이터 저장)

3. 인덱스 설정 기준

• 카디널리티: 유일한 값의 개수를 의미. (카디널리티가 낮은 경우 비추. 예: 남/여)

• 검색 패턴: 검색 조건에 자주 사용되는 컬럼

• 데이터 수정 빈도: 삽입, 삭제, 수정 시 인덱스 테이블도 같이 수정됨.

4. 인덱스의 종류

4.1. 커버링 인덱스

인덱스 테이블에서 조회 후, 테이블로 이동하지 않고 데이터를 조회할 수 있는 경우.

CREATE INDEX idx_department_name ON employees (department, id, name);
이 인덱스는 department, id, name 열을 포함합니다. 이제 동일한 쿼리를 실행하면:

SELECT id, name FROM employees WHERE department = 'Sales';

인덱스가 id, name을 모두 포함하고 있기 때문에, 추가적인 데이터가 필요없으므로 원본 테이블로 이동할 필요가 없습니다.

4.2. 다중 컬럼 인덱스(복합 인덱스)

• 두 개 이상의 컬럼을 하나의 인덱스로 묶어 한번에 여러 조건을 기반으로 검색 성능을 최적화 할 수 있는 인덱스.

• 컬럼의 순서에 따라 성능이 달라집니다.

4.3. 클러스터링 인덱스

데이터베이스 테이블의 물리적인 저장 순서를 인덱스의 순성와 일치시키는 방식.

• 테이블당 단 하나만 존재 가능. 기본키 / 고유키에 따라 정렬

• InnoDB 같은 스토리지 엔진에서는 자동으로 기본 키가 클러스터링 인덱스가 됨.

5. 인덱스 스캔 방식

• 인덱스 유니크 스캔: 기본 키나 유니크 인덱스에 대해 정확한 값일치 검색을 수행하는 경우

• 인덱스 레인지 스캔: 검색할 데이터의 범위가 정해 졌을 때 사용되는 스캔 방식

• 인덱스 풀 스캔: 인덱스의 처음부터 끝까지 모든 레코드를 순차적으로 스캔. 테이블 풀 스캔보다 효율적 (덱스는 테이블의 전체 컬럼을 읽지 않고, 필요한 컬럼만 포함하고 있기 때문)

6. 인덱스 작동 확인 방법

• 쿼리 실행 계획 확인: EXPLAIN / EXPLAIN ANALYZE

• 쿼리 성능 테스트

7. 인덱스 사용 주의 사항

• 인덱스의 개수: 많을 수록 삽입, 삭제, 수정시 오버헤드

• 중복인덱스: 동일한 컬럼에 여러개의 인덱스가 있는지 확인

• 카디널리티 고려: 유일한 값의 개수가 많을 수록 성능 향상

• 충분히 데이터양이 큰지 확인: 검색 결과가 전체의 15~20%이상이면 풀 스캔이 더 빠를 수 있다.