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%이상이면 풀 스캔이 더 빠를 수 있다.
Last updated