[Database] 인덱스(Index) (1)

우아한테크코스 레벨 4 팀 프로젝트 festabook에서 학습한 내용을 정리한 글입니다.

 

💭 들어가며

처음 인덱스를 공부했을 때는 종류가 너무 많았는데, 막상 살펴보니 MySQL에서 실제로 지원하는 인덱스는 그리 많지 않아 혼란스러웠다. 찾아보니 인덱스의 분류 기준이 국제 표준(ISO)에서 명확히 정의되어 있지 않았고, 각 DBMS마다 지원하는 인덱스의 종류와 구현 방식은 모두 달랐다. 이로 인해 특정 DBMS에서 사용되는 인덱스 용어가 다른 DBMS에서도 혼용되거나, 구두나 문서로 설명되는 과정에서 특정 용어가 일반화된 것으로 보인다.
따라서 이번 글에서는 인덱스의 개념과 이론적 분류 기준을 정리하고, 이후 글에서 MySQL이 실제로 지원하는 인덱스와 그 동작 방식을 구체적으로 살펴볼 예정이다.

이 글은 MySQL(InnoDB) 중심적으로 작성되었다.

 
 

✅ 인덱스

인덱스는 데이터베이스의 검색(SELECT) 성능을 향상시키기 위한 자료구조다. 쉽게 말해, 책의 ‘색인표’처럼 원하는 데이터를 빠르게 찾기 위해 미리 정렬된 구조를 만들어 두는 것이다.
다만, INSERT, UPDATE, DELETE 연산 시에는 인덱스를 함께 갱신해야 하므로 쓰기 작업이 많은 테이블의 경우 오히려 성능이 저하될 수 있다.
 
 

✅ 인덱스 알고리즘

▶ B-Tree

B-Tree 인덱스는 컬럼의 원래 값을 그대로 사용해 인덱싱하는 방식으로, 데이터를 변환하지 않는다. 여기서 ‘B’는 Binary(이진) 트리가 아니라, Balanced(균형) 트리이다.

• 루트 노드(Root Node)를 최상단에 두고, 그 아래로 여러 자식 노드(Child Node)가 연결된다.
• 리프 노드(Leaf Node)는 가장 하단에 위치하며, 실제 데이터 레코드를 가리키는 주소값을 저장한다.
• 모든 리프 노드의 깊이가 동일하다.
• 탐색 속도는 O(log N)이다.

MySQL(InnoDB)에서 사용되는 대표적인 인덱스 구조로, Primary, Unique, Secondary 인덱스 모두 B-Tree 기반으로 동작한다.

MyISAM 엔진은 데이터 파일의 레코드가 순서대로 저장되지 않지만, InnoDB 엔진은 데이터 레코드 자체가 Primary Key 순서로 정렬되어 저장된다.

 

▶ Hash

Hash 인덱스는 Key 값을 해시 함수(Hash Function)를 통해 변환하여 저장하는 방식이다. 즉, 동일한 Key에 대해 항상 같은 해시값을 생성하여 빠른 직접 접근을 가능하게 한다.

• 정확한 일치 검색(=)에 매우 빠르다.
• 정렬된 순서가 없기 때문에 범위 검색은 느려서 범위 검색(BETWEEN, >, < 등) 은 비효율적이다.
• 탐색 속도는 O(1)이다.

 
 

✅ 인덱스 분류 (용어)

분류 기준	Index 종류	설명
유일성	Unique Index	인덱스 키 중복 불가 ex) UNIQUE INDEX, PRIMARY KEY
	Non-Unique Index	인덱스 키 중복 가능 ex) INDEX
구성 컬럼 수	Single Index	단일 컬럼으로 구성 ex) CREATE INDEX idx ON table(col1);
	Composite Index	두 개 이상의 컬럼으로 구성 (Leftmost Prefix Rule 적용) ex) CREATE INDEX idx ON table(col1, col2);
클러스터	Clustered Index	테이블의 데이터 자체가 인덱스 순서로 정렬되어 저장 ex) InnoDB의 PRIMARY KEY
	Non-Clustered Index	데이터는 별도 공간에 저장되며, 리프 노드가 PK를 통해 참조 ex) InnoDB의 SECONDARY INDEX
함수	Function-Based Index	컬럼 자체가 아닌 함수/표현식 결과값에 대해 인덱스를 생성 ex) CREATE INDEX idx_lower_email ON user((LOWER(email)));
기타	Reverse Key Index	인덱스 키의 바이트 순서를 거꾸로 저장 ex) 컬럼 값 1234 → 인덱스 4321
	Inverted Index (Full-Text)	단어 기반 역색인 구조 ex) MySQL의 FULLTEXT INDEX
	R-Tree Index (Spatial)	공간 데이터를 위한 인덱스 ex) MySQL의 SPATIAL INDEX

 
 

📍 참고 자료

• MySQL 공식 문서 - 10.3.1 How MySQL Uses Indexes
• Real MySQL 8.0 - 8.3. B-Tree 인덱스