[Real MySQL] 8-3. 인덱스: 알고리즘 - B-Tree Index

백은빈, 이성욱 님의 "Real MySQL" 책을 정리한 포스팅 입니다.

 

1. B-Tree Index

• 가장 기본적인 인덱스 타입
• 원래 값을 변형시키지 않는 인덱스

 

구성 요소

항목	설명
트리 구조	- 하나의 인덱스 = 하나의 B+ Tree - 루트 → 중간 노드 → 리프 노드 - 깊이는 데이터 양과 키 크기에 따라 증가
페이지 (Page)	- InnoDB의 읽기/쓰기 최소 단위 - 기본 크기: 16KB (innodb_page_size) - 하나의 노드 = 하나의 페이지
노드 (Node)	- B+ Tree를 구성하는 단위 - (인덱스 키 값 : 자식 노드 주소) 형태로 저장됨 - 리프 노드는 실제 데이터 주소를 가짐
- 리프 노드	- Primary Key Index: key → record 주소 - Secondary Key Index: key → rowID(PK)

 

다중 컬럼 인덱스

• 두 개 이상의 컬럼들로 구성된 인덱스
• 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬돼 있습니다.
  • 첫 번째 컬럼이 먼저 정렬된 후 그 안에서 두 번째 컬럼이 정렬되는 방식
  • 인덱스 내에서 각 칼럼의 위치가 상당히 중요합니다.

 

2. 동작

• 균형 트리 구조를 유지하면서 데이터를 정렬된 상태로 저장하여 성능을 높임

 

추가

항목	내용
과정	- 루트 노드에서 시작하여 브랜치 노드를 따라 리프 노드까지 이동 - 적절한 리프 노드에 키 저장
예외 처리	- 노드 분할: 리프 노드가 가득 찬 경우 키를 반으로 나누어 상위 노드로 승격 (트리 균형 유지)

 

삭제

항목	내용
과정	- 삭제할 키를 리프 노드에서 검색하여 논리적 삭제 수행 (삭제 표시) - 즉시 삭제 대신 지연 삭제
예외 처리	- 삭제 후 키 개수가 특정 기준 이하가 되면 인접 노드와 병합하여 트리의 균형 유지

 

변경

항목	내용
과정	- 기존 키를 삭제한 후, 새로운 키를 추가하는 방식으로 처리
이유	- B-Tree는 정렬된 구조를 유지해야 하므로 키 값을 직접 변경할 수 없음. - 삭제 후 재삽입이 필요함

 

검색

항목	내용
과정	- 루트 노드부터 시작하여 브랜치 노드를 거쳐 리프 노드까지 키 값을 비교하며 탐색
검색 속도	- 빠름: 100% 일치 또는 앞부분 일치 - 느림: 키 값의 뒷부분 일치 - 불가: 키 값이 변형된 경우 (정렬 기반 탐색 구조 깨짐)

 

3. 사용에 영향을 미치는 요소

인덱스 키 값의 크기

• 키 값의 길이가 커지면 한 페이지에 저장할 수 있는 키의 개수가 줄어들어 깊이가 증가됨
• 트리가 깊어질수록 디스크 읽기가 많아짐

 

선택도 (기수성)

• 전체 인덱스 키 중 유니크한 값의 수

조건	설명
선택도 높음	검색 조건에 해당하는 레코드 수 적음 → 효율적
선택도 낮음	중복 많은 값 검색 시 → 많은 레코드 읽게 됨 → 성능 저하

 

 

읽어야 하는 레코드 건수

• 인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있다.
• 읽어야 할 레코드의 건수가 전체 테이블 레코드의 25% 이상이면 풀 테이블 스캔이 효율적

 

4. 데이터 읽기

인덱스 레인지 스캔

• 범위 조회를 할 떄 사용되는 방식
• 한 번에 하나의 레코드를 찾는 랜덤 I/O가 일어납니다.

항목	설명
사용 시점	WHERE 조건절에 인덱스 범위 조회가 걸려 있을 때
과정	1. 인덱스 탐색: 인덱스에서 최소 조건에 해당하는 위치를 찾음 (랜덤 I/O) 2. 인덱스 스캔: 최대 조건까지 데이터를 읽음 (순차 I/O (정순/역순))
장점	효율적 (인덱스를 활용해 필요 범위만 읽음)
단점	범위가 너무 넓으면 많은 I/O 발생 가능
상태 변수	- Handler_read_key: 인덱스 탐색 실행 횟수 - Handler_read_prev: 인덱스 스캔에서 정순으로 읽은 레코드 수 - Handler_read_next: 인덱스 스캔에서 역순으로 읽은 레코드 수 - Handler_read_first: 첫번째 레코드를 읽은 횟수 - Handler_read_last: 마지막 레코드를 읽은 횟수

 

인덱스 풀 스캔

• 인덱스에 저장된 모든 엔트리를 처음부터 끝까지 순차적으로 탐색하는 방식

항목	설명
I/O 특성	순차 I/O (랜덤 접근 없음)
순서 보장	정렬된 결과가 필요할 때 유리 (인덱스 순서대로 읽음)
사용 조건	- WHERE 조건이 복합 인덱스의 첫 번째 컬럼을 사용하지 않을 때 - 데이터 레코드 접근 없이 인덱스만으로 결과를 만들 수 있을 때 (Covering Index)

 

루즈 인덱스 스캔

• 인덱스를 순차적으로 스캔하지 않고, 필요한 인덱스 값만 건너뛰며 읽는 방식

항목	설명
사용 목적	GROUP BY 또는 DISTINCT 시, 각 그룹에서 첫 값만 가져오는 최적화
요구 조건	- 인덱스가 순서로 존재해야 함 (복합 인덱스) - 인덱스만으로 원하는 데이터를 모두 처리할 수 있어야 함 (Covering Index)
동작 방식	- 모든 category에 대해 최소 1회만 디스크 접근
장점	- 필요 없는 중간 레코드를 건너뛰므로 디스크 I/O 감소, 빠른 실행
단점	- GROUP BY 외 쿼리에는 사용되지 않음- 인덱스 조건이 정확히 맞지 않으면 사용 불가
EXPLAIN 결과	Using index for group-by 라고 표시됨

 

예시

SELECT category, MIN(price) FROM products GROUP BY category;

• GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우만
• category + price 복합 인덱스가 있다면, category 별 최소 price 값만 찾고 다음 category로 이동

 

인덱스 스킵 스캔

항목	설명
정의	선행 컬럼의 조건 없이, 그 다음 컬럼의 조건만으로 인덱스를 사용할 수 있도록 하는 방법 선행 컬럼의 모든 유니크 값에 대해 부분 인덱스 스캔을 반복 수행하는 방식
동작 방식	- 선행 컬럼의 모든 유니크 값에 대해 → 해당 값 + 조건 컬럼 조합으로 인덱스 검색 반복 → 결과를 병합
필수 조건	- 조건 컬럼이 인덱스에 포함되어 있어야 함 - 조건 컬럼이 인덱스 정의 순서 상 앞 컬럼 이후여야 함
주의 사항	- 인덱스의 컬럼 순서가 매우 중요 - 인덱스 전체를 부분적으로 여러 번 읽기 때문에, 비효율적일 수 있음
효율적인 경우	- 선행 컬럼의 유니크한 값 개수가 적을 때
EXPLAIN 힌트	index skip scan 또는 DBMS에 따라 다르게 표현됨 (MySQL은 일반적으로 사용 불가, Oracle은 명시적 지원)
장점	- 앞 컬럼 조건 없이도 인덱스 사용 가능 - 추가 인덱스 없이 성능 개선 가능성
단점	- 유니크 값 개수가 많으면 풀 인덱스 스캔 수준의 I/O 발생 가능성 있음

 

예시

SELECT * FROM employees WHERE age = 30;

• department_id + age 복합 인덱스의 경우
• department_id가 조건에 없으므로
• department_id의 유니크한 값마다 age = 30 조회

 

5. 정렬 및 스캔 방향

• 인덱스를 구성하는 컬럼의 정렬을 가지고 결정됩니다.

CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

 

인덱스 스캔 방향

• 인덱스를 사용할 떄 데이터를 읽는 순서에 따라 정렬 방향이 영향을 미칠 수 있음
• 쿼리가 그 인덱스를 사용하는 시점에 읽는 방향에 따라 역순의 정렬 효과를 얻을 수 있다.

 

정순 스캔

• 왼쪽에서 오른쪽으로 스캔
• 페이지 잠금

 

역순 스캔

• 오른쪽에서 왼쪽으로 스캔
• 정순 스캔보다 30% 정도 느립니다.

 

내림차순 인덱스

• 인덱스 키의 큰 값이 B-Tree 의 왼쪽으로 정렬된 인덱스
• 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조
• 역순스캔이므로 성능이 떨어질 수 있음

 

6. 가용성과 효율성

비교 조건

• 각 컬럼의 순서와 조건에 따라 인덱스 컬럼 활용 형태가 달라지며 효율도 달라진다.

 

필터링

• 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업
• 비교 작업의 범위를 좁히는데 효과적인 컬럼일수록 효율적

 

가용성

왼쪽 기준 정렬 기반

• 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것 입니다.
• 뒷부분의 값만으로 인덱스를 효율적으로 활용할 수 없습니다.

 

효율성 판단

아래 경우는 작업 범위 결정 조건으로 사용할 수 없습니다.

• NOT EQUAL : <>, NOT IN, NOT BETWEEN, IS NOT NULL
• LIKE '%??'
• 컬럼이 변형된 경우: 스토어드 함수(DAYOFMONTH), 연산자(SUBSTRING)
• 데이터 타입이 서로 다른 비교
• 문자열 데이터 타입의 콜레이션이 다른 경우