03-02. Index
Last updated
Last updated
데이터베이스 인덱스는 테이블의 특정 컬럼에 대한 검색 성능을 최적화하기 위해 설계된 데이터 구조입니다.
마치 책의 색인처럼, 데이터베이스가 방대한 데이터 속에서 원하는 레코드를 빠르게 찾아낼 수 있도록 돕습니다.
인덱스는 선택된 컬럼의 값을 정렬된 형태로 저장하며, 이를 통해 전체 테이블을 순차적으로 스캔(Full Table Scan)하지 않고도 필요한 데이터를 효율적으로 조회할 수 있습니다.
예를 들어, 수백만 행의 고객 테이블에서 특정 이메일 주소를 찾을 때, 인덱스가 없으면 모든 행을 확인해야 하지만, 인덱스가 있다면 단 몇 번의 탐색으로 결과를 반환합니다.
하지만 인덱스는 장점만 있는 것이 아닙니다.
데이터 삽입(INSERT), 수정(UPDATE), 삭제(DELETE) 작업이 발생할 때마다 인덱스도 함께 갱신되므로 쓰기 성능에 부담을 줄 수 있습니다.
또한, 인덱스는 별도의 저장 공간을 차지하므로 디스크 사용량이 증가합니다.
따라서 실무에서는 적절한 인덱스를 설계해야 합니다.
예를 들어, 읽기 중심의 분석용 데이터베이스라면 인덱스를 적극 활용하고, 쓰기 중심의 트랜잭션 시스템이라면 최소화하는 식으로 전략을 세웁니다.
인덱스를 설정하면 데이터베이스는 해당 컬럼을 기반으로 B-Tree 또는 변형인 B+Tree 데이터 구조를 생성합니다.
B-Tree는 키 값과 데이터 위치를 가리키는 포인터로 구성된 노드들이 계층적으로 연결된 트리입니다.
데이터베이스는 이 구조를 활용해 검색 요청이 들어오면 루트 노드에서 시작해 키 값을 비교하며 하위 노드로 이동, 최종적으로 원하는 데이터의 물리적 위치를 찾아냅니다.
예를 들어, WHERE id = 100 쿼리가 실행되면 B-Tree는 'id' 값을 기준으로 트리를 탐색해 해당 레코드의 주소를 즉시 반환합니다.
B-Tree 외에도 데이터베이스 엔진에 따라 해시 테이블이나 비트맵 같은 다른 구조를 사용할 수 있지만, B-Tree는 범위 검색과 정렬된 데이터 접근에 강점이 있어 가장 널리 사용됩니다.
B-Tree는 자체적으로 균형을 유지하는 다진 트리(multiway tree) 로, 각 노드가 여러 개의 키와 해당 키에 대응하는 자식 노드 포인터를 가집니다.
루트 노드에서 시작해 리프 노드까지 이어지며, 모든 리프 노드는 동일한 깊이를 유지합니다. 이 구조는 디스크 기반 데이터베이스에 최적화되어 있는데, 노드당 많은 키를 저장해 트리의 깊이를 얕게 유지하고, 디스크 I/O를 최소화합니다.
이제 시간복잡도를 살펴보면
인덱스 사용 시: B-Tree의 탐색은 이진 검색과 유사하지만, 다중 키 덕분에 시간복잡도는 O(logn) 입니다. 여기서 n은 레코드 수이며, 로그의 밑은 B-Tree의 차수(order) 또는 한 노드가 가질 수 있는 최대 자식 노드의 수에 따라 달라집니다.
인덱스 미사용 시: 테이블 전체를 순차적으로 스캔해야 하므로 시간복잡도는 O(n) 입니다. 데이터가 클수록 성능 차이가 극명해집니다. 예를 들어, 1,000,000행에서 특정 값을 찾을 때 인덱스 없이 최대 1,000,000번 비교해야 하지만, B-Tree 인덱스라면 일반적으로 20번 이내에 완료됩니다.
B-Tree의 변형인 B+Tree는 리프 노드에만 데이터를 저장하고, 리프 노드 간 링크를 추가해 범위 검색 성능을 더 개선합니다. MySQL의 InnoDB 엔진은 B+Tree를 기본으로 사용합니다.
B-Tree 인덱스는 문자열의 접두사(왼쪽부터 시작)를 기준으로 정렬되므로, LIKE 'abc%' 같은 접두사 검색에서는 효과적으로 동작합니다.
예를 들어, WHERE name LIKE 'John%'는 'John'으로 시작하는 모든 이름을 빠르게 찾습니다.
그러나 와일드카드(% 또는 _)가 문자열의 시작 부분에 사용되는 접미사 검색(LIKE '%son')이나 중간 검색(LIKE '%oh%')에서는 정렬 순서를 활용할 수 없어 인덱스가 적용되지 않거나 매우 비효율적입니다.
이 경우 데이터베이스는 Full Table Scan을 수행하며, 성능이 O(n)에 가까워집니다.
이를 해결하려면 특수 인덱스를 사용해야 합니다:
Full-Text Index: 단어 단위로 텍스트를 분리해 인덱싱하며, 검색 엔진처럼 동작합니다. 예: MATCH(column) AGAINST('keyword').
Reverse Index: 문자열을 뒤집어 저장한 후 인덱싱해 접미사 검색을 지원합니다.
먼저 클러스터드 인덱스는 테이블 데이터를 특정 키 순서대로 물리적으로 정렬해 저장합니다.
그래서 테이블당 하나만 가능하고, 마치 책 내용 자체가 순서대로 정렬된 것과 같죠. 덕분에 범위로 검색하거나 정렬된 결과를 볼 때 아주 빠릅니다. 주로 기본 키에 사용되는데 다만, 데이터를 수정하거나 새로 넣을 때 재정렬 때문에 쓰기 작업이 좀 느려질 수 있다는 점은 생각해야 합니다.
반면에 넌클러스터드 인덱스는 데이터와는 별도로 '찾아보기'처럼 색인을 만들어두는 것입니다.
실제 데이터가 어디 저장되어 있는지 그 위치 주소를 가지고 있죠. 그래서 한 테이블에 여러 개 만들 수 있고, 특정 값을 찾거나 다양한 조건으로 검색할 때 유용해요. 데이터를 찾을 때 한 단계를 더 거칠 수는 있지만, 쓰기 부담은 클러스터드 인덱스보다 상대적으로 덜한 편입니다.
보통 기본키가 아닌 키에 인덱스를 설정하면 이 넌클러스터드 인덱스가 설정됩니다.