[DB] 인덱스란? B+Tree 구조부터 스캔 방식까지 정리

📌 데이터베이스 인덱스란?

데이터베이스 인덱스(Idex)는 검색 속도를 향상시키기 위한 자료구조로, 책의 색인(index)처럼 원하는 데이터를 빠르게 찾기 위한 도구이다.
정렬된 구조를 유지하기 때문에 조회 성능은 뛰어나지만, INSERT, UPDATE, DELETE 시에는 성능이 떨어질 수 있다.
(정렬 유지와 재구성 비용 때문)

 

 

✅ 인덱스는 어떤 자료구조로 구현될까?

대부분의 관계형 데이터베이스(RDBMS)는 B-Tree 또는 B+Tree 기반 인덱스 구조를 사용한다.
(MySQL의 InnoDB 스토리지 엔진 기준으로 정리할 예정)

 

 

🌳 B+Tree 인덱스 구조

• B+Tree는 B-Tree의 변형으로 모든 실제 데이터(레코드 위치)는 리프 노드에만 존재
• 항상 정렬된 상태 유지
  (→ 범위 조회가 빠르다, 순차 접근이 용이하다.)

📦 구조 구성

1. 루트 노드(Root Node) : 최상위 노드, 검색 시작 지점
2. 브랜치 노드(Branch Node) : 중간 노드, 탐색 경로
3. 리프 노드(Leaf Node) : 실제 레코드 주소 또는 PK 값 저장

📘 InnoDB 기준 특징

• 클러스터 인덱스(Primary Key Index) : 리프 노드에 실제 레코드 전체를 저장
• 보조 인덱스(Secondary Index) : 리프 노드에 해당 레코드의 PK 값만 저장 → 다시 PK 인덱스를 한번 더 타야 한다. (인덱스 더블 스캔 발생)

 

 

🔍 인덱스 스캔 방식 정리

인덱스를 이용한 검색 시, MySQL은 여러 가지 방식으로 인덱스를 탐색한다.

1️⃣ 인덱스 레인지 스캔 (Index Range Scan)

• 조건에 따라 검색 범위가 정해진 경우
• 시작 리프 노드부터 조건 만족하는 키까지 순차적으로 스캔
• index seek → index scan → 데이터 조회 순으로 동작
• 랜덤 IO 발생 가능성이 있다.
• 범위 조건 (BETWEEN, >=, <)에 적합
• 가장 빠른 스캔 방식

2️⃣ 인덱스 풀 스캔 (Index Full Scan)

• 인덱스 전체를 처음부터 끝까지 읽는 방식
• 인덱스 조건이 앞 컬럼이 아닌 중간(B, C 등) 컬럼으로 검색 시 발생
• 인덱스는 사용하지만 → 실제 레코드는 안 읽을 수도 있다.
• 풀 테이블 스캔보다는 성능 좋을 수 있다.

3️⃣ 루스 인덱스 스캔 (Loose Index Scan)

• 필요한 일부 키만 건너뛰며 선택적으로 스캔
• 중간 불필요한 인덱스 키는 생략
• GROUP BY, MIN(), MAX() 등 최적화 사용
• 타이트 스캔(순차적) 방식과 대비되는 개념

 

💥 인덱스 사용 시 장단점 요약

구분	장점	단점
조회 시	빠른 검색, 정렬 효율적	-
삽입/수정/삭제 시	-	정렬 유지 비용, 인덱스 갱신 필요로 성능 저하
너무 많은 인덱스	-	인덱스 유지 비용 증가, 쿼리 성능 오히려 저하 가능

 

 

🧠 요약 키워드

항목	키워드
자료구조	B+Tree, 리프 노드에 실제 레코드(PK)
인덱스 종류	클러스터 인덱스(Primary), 보조 인덱스(Secondary)
스캔 방식	Range Scan, Full Scan, Loose Scan
단점	INSERT/UPDATE/DELETE 성능 저하, 공간 낭비 가능

 

 

📘 마무리 요약

인덱스를 조회 성능을 높이는 강력한 도구지만 잘못 설계되면 오히려 성능을 떨어뜨릴 수 있다.
인덱스가 어떤 자료구조로 동작하는지, 그리고 스캔 방식이 어떤 상황에서 어떻게 사용되는지를 아는 것은 백엔드 개발자에게 필수적인 지식이다.