인덱스
레코드의 접근 경로에 대한 내용입니다.
인덱스란 <key, value>형태로 구성된 데이터 구조로, key값에는 인덱스 컬럼 값, value에는 레코드의 주소(=포인터)를 저장하고 있습니다.
인덱스는 레코드가 실제 저장된 물리 주소와 맵핑되어 있으므로, 물리적 구조에 빠르게 접근할 수 있는 방법을 제공합니다. 즉, 인덱스는 레코드의 빠른 검색을 위한 도구라고 볼 수 있습니다.(인덱스가 없으면, 특정 값을 찾기 위해 모든 데이터의 페이지를 확인하는 FULL TABLE SCAN이 필요하기 때문)
이처럼 인덱스는 빠른 검색에는 좋지만, 삽입/수정/삭제 작업에서는 성능이 느려질 수 있습니다. 예를 들어, 주로 사용되는 B-tree 기반 인덱스는 항상 정렬되어 있습니다. 삽입/수정/삭제 작업이 발생할 때마다 재정렬이 이루어져야 하기 때문에 추가적인 작업 시간이 더 발생하게 됩니다.
인덱스 종류 - 자료구조에 따른 분류
1) 트리 기반 인덱스
트리 기반 인덱스는 인덱스를 저장하는 블록들이 균형 트리 구조로 저장됩니다. 이는 부모 노드를 기준으로 자식 노드가 좌/우 정렬된 트리 구조를 통해 효율적인 탐색을 가능하게 합니다.
대표적으로 B-Tree와 B+Tree가 있으며, 루트 노드, 브랜치 노드, 리프 노드로 구성됩니다.
B-Tree 인덱스:
B-Tree는 균형 이진검색트리를 일반한 자료 구조를 통해, 노드들을 관리합니다. 한 노드에 다수의 키 값을 저장할 수 있으며, 부모 노드는 여러 개의 자식 노드를 가질 수 있습니다. B-Tree의 차수에 따라 자식 노드의 최대 개수가 결정됩니다. 평균적으로 O(logN)의 탐색 속도를 가지며, 모든 리프 노드는 같은 레벨에 위치합니다.
노드 내부에는 여러 키 값이 저장되며, 각 키 값은 자식 노드의 값 범위를 결정합니다.
예를 들어, "100"과 "155"이라는 키 값은 해당 노드 아래의 키 값들이 어떤 값 범위를 가지는지 알려줍니다. 이처럼, B-tree 인덱스는 현재 찾고자 하는 노드가 있을 법한 경로를 찾아 빠르게 탐색해나갑니다.
B-tree 인덱스의 또 다른 주요 특징은 "대수 확장성"입니다. 이는 트리의 깊이(트리의 높이)가 리프 노드 수에 비해 매우 느리게 확장하는 특성입니다. 즉, 노드 수가 증가하는 속도에 비해, 탐색해야 하는 트리의 깊이는 천천히 증가한다는 것이죠.
B-Tree의 각 노드에는 키 값과 데이터를 저장할 수 있습니다. 그러나 구현에 따라 데이터는 리프 노드에만 저장되기도 합니다.
B+Tree 인덱스:
B+Tree는 B-Tree를 확장한 구조로, 데이터는 리프 노드에만 저장되며, 브랜치 노드는 탐색을 위한 키 값을 저장하여 리프 노드로 이어지는 경로를 결정합니다.
SELECT 문에서 WHERE 절에 인덱스 컬럼이 사용된 경우, 루트 노드 → 브랜치 노드 → 리프 노드 순으로 탐색하여 데이터를 찾습니다.
또한, B+Tree의 리프 노드들은 링크드 리스트 형태로 연결되어 있어, 리프 노드 간 순차 탐색이 필요할 때 매우 효율적입니다.
이와 같은 구조적 장점으로 인해 상용 DBMS에서 B+Tree 인덱스가 주로 사용됩니다.
2) Hash 인덱스
Hash 인덱스는 인덱스 키 값을 해시 함수로 변환하여 해시 값에 따라 데이터를 저장하고 검색합니다. 이를 통해 특정 키 값의 검색은 평균적으로 O(1) 의 시간 복잡도로 매우 빠르게 수행됩니다. 하지만, 인덱스 키 값이 해시값으로 정해지기 때문에, 범위 쿼리(e.g., BETWEEN, >, <)나 Prefix 비교(e.g., LIKE 'abc%')가 지원되지 않습니다. hash 기반 인덱스에서 범위 검색이나 prefix 비교가 이루어질 경우, 풀 테이블 스캔이 발생합니다.
따라서 Hash 인덱스는 정확한 키 검색(e.g., =)에 적합하지만, 범위 조건이나 정렬 기반 검색이 필요한 경우에는 트리 기반 인덱스(B+Tree) 사용이 더 적합합니다
그 이외의 인덱스 종류
클러스터링 인덱스
인덱스의 키 순서에 따라, 레코드가 물리적으로 정렬되는 방식입니다.
범위 쿼리(BETWEEN, >, <)나 순차 검색처럼 비슷한 인덱스를 가지는 레코드들을 효율적으로 조회하기 위해 등장 하였습니다. Mysql의 innoDB 엔진도 기본적으로 클러스터링 인덱스를 사용하며, 기본키가 클러스터링 인덱스 역할을 수행합니다.
이는 인덱스 기반 검색 속도가 빠르다는 장점이 있지만,
하나의 릴레이션에 대해 하나의 인덱스만 생성 가능하며, 데이터 삽입/삭제 발생 마다 순서를 재정렬해야 한다는 단점도 있습니다.
커버링 인덱스
SQL문에서 요청하는 모든 컬럼이 인덱스인 경우입니다.이 경우, 인덱스 테이블만 조회하여도 레코드를 반환할 수 있으므로, 테이블의 실제 데이터를 조회할 필요가 없습니다. 디스크 I/O 요청이 줄어들지만, 쓰기 작업의 경우 인덱스 크기가 커지면 성능이 느려질 수 있습니다.
다중 컬럼 인덱스
2개 이상의 컬럼을 조합하여 생성된 인덱스입니다. 커버링 인덱스와 다르게, 질의에 인덱스 모든 컬럼이 포함되어 있을 필요는 없습니다. 하지만, 다중 컬럼 인덱스는 선행 컬럼부터 포함하여 검색이 들어갈때 인덱스를 활용할 수 있습니다. 예를 들어, 선행 컬럼 없이 후행 컬럼으로만 레코드 검색이 요청되는 경우, 다중 컬럼 인덱스를 활용할 수 없습니다. 즉,여러개의 컬럼으로 구성된 인덱스인 만큼, 검색 순서 등의 패턴이 성능에 영향을 줍니다.
인덱스 설계
어떤 컬럼을 인덱스로 선정 할지는 여러 기준을 고려해볼 수 있습니다.
WHERE 절에서 자주 사용되는 컬럼(검색 조건), unique 제약조건이 준수되는 컬럼, ORDER BY/GROUP BY 연산이 빈번하게 수행되는 컬럼 등이 있습니다.
또한 사용하는 DBMS의 엔진 특성도 고려하면 좋습니다.
예를 들어, InnoDB는 기본 키를 클러스터링 인덱스로 저장하며, 클러스터링 인덱스와 보조 인덱스 모두 B+Tree로 구현됩니다. 이때, 인덱스는 정렬된 상태를 유지해야 합니다. 하지만, uuid와 같이 값이 연속적이지 않은 값을 인덱스 키 값으로 활용 한다면, 페이지 분할이나 재조정 등이 빈번하게 발생하여 성능이 느려질 수 있습니다.
인덱스 스캔
인덱스 스캔은 단일 인덱스를 검색하는지, 일정 범위의 인덱스만 검색하는지, 전체적인 인덱스 검색이 필요한지에 따라 스캔 방식이 나뉩니다.
Index Unique Scan (인덱스 고유 스캔), Index Range Scan (인덱스 범위 스캔), Index Full Scan (인덱스 전체 스캔) 등이 있습니다.
예를 들어, B+tree 인덱스에서 일정 범위의 인덱스가 조건에 걸려있다면,
루트 노드에서 시작점 리프 노드를 찾아간 뒤, 리프 노드 간의 링크를 통해 종료지점 리프 노트까지 범위 스캔을 수행하게 됩니다.
한편, 검색 컬럼이 모두 인덱스에 포함되는 커버링 인덱스일 경우 테이블 데이터 조회가 필요 없으므로, Index Fast Full Scan (인덱스 빠른 전체 스캔)이 가능합니다.
Reference
CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조
길벗알앤디. (2019). 2020 시나공 정보처리기사 필기. 길벗.
