[Real MySQL] 8-3. 인덱스: B-Tree

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

 

1. 특성

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

 

리프 노드

• primary key index: key - record
• secondary key index: key - rowID (PK)

 

2. 키 추가 및 삭제

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

 

추가

과정

1. 저장될 키 값을 이용하여 추가될 위치를 검색
   • 루트 노드에서 시작하여 브랜치 노드를 따라가며 적절한 리프 노드까지 이동
2. 리프 노드에 저장

 

예외 처리

• 노드 분할
  • 리프 노드가 가득 찰 경우, 키를 반으로 나누어 상위 노드로 승격하여 트리를 균형있게 유지

 

삭제

과정

1. 삭제할 키를 검색하여 리프 노드에서 삭제 표시
2. 즉시 삭제하지 않고 지연 삭제 가능

 

예외 처리

• 삭제 후 노드가 너무 비어 있으면?
• 특정 기준 이하로 키 개수가 줄어들면, 인접 노드와 병합하여 트리의 균형을 유지

 

변경

과정

1. 먼저 키 값을 삭제
2. 새로운 키 값 추가

 

이유

• B-Tree는 항상 정렬된 상태를 유지해야 함
• 키 값이 변경되면, 기존의 정렬된 구조가 깨질 수 있음
• 따라서 기존 키를 삭제하고 새로운 키를 추가하는 방식으로 변경을 처리

 

검색

과정

1. 루트 노드로부터 탐색 시작
2. 브랜치 노드를 거쳐 리프 노드까지 이동
3. 키 값을 비교하면서 원하는 데이터를 찾음

 

검색 속도 차이

• 빠름: 100% 일치 또는 앞부분만 일치
• 느림: 키 값의 뒷부분으로 검색
• 불가: 키 값 변형

 

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

페이지 (블록)

• 모든 읽기 및 쓰기 작업의 최소 작업 단위
• 하나의 페이지 안에는 여러 개의 노드가 저장됨

 

노드

• 인덱스 키 값 + 자식 노드 주소

 

기본 크기

• 16KB (innodb_page_size)

 

인덱스 키 값의 크기

자식 노드

• 키 값 + 행 주소 (논리적)
• 하나의 노드가 가질 수 있는 자식 노드의 수는 가변적
• 페이지 크기와 키 값의 크기에 따라 달라짐

 

깊이

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

 

선택도 (기수성)

• 모든 인덱스 키 값 가운데 유니크한 값의 수

 

효율성

• 선택도가 높을수록 중복이 적고 검색 효율이 높음
  • 검색 조건에 해당하는 레코드가 적기 때문에 불필요한 I/O가 줄어듬
• 선택도가 낮으면 (중복이 많으면) 불필요한 읽기 작업이 증가하여 성능이 저하됨
  
  • 같은 인덱스 키 값을 가진 레코드가 많다면, 검색 시 여러 개의 레코드를 조회해야 함

 

최적화 방법

• 선택도가 높은 컬럼을 인덱스로 사용
• 자주 조회되는 컬럼이지만 중복이 많다면 인덱스 생성이 비효율적으로 동작함

 

읽어야 하는 레코드 건수

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

 

4. 데이터 읽기

인덱스 레인지 스캔

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

 

과정

• 인덱스 탐색: 인덱스에서 최소 조건에 해당하는 위치를 찾음
• 인덱스 스캔: 최대 조건까지 데이터를 읽음 

 

상태 변수

• Handler_read_key: 인덱스 탐색 실행 횟수
• Handler_read_prev: 인덱스 스캔에서 정순으로 읽은 레코드 수
• Handler_read_next: 인덱스 스캔에서 역순으로 읽은 레코드 수
• Handler_read_first: 첫번째 레코드를 읽은 횟수
• Handler_read_last: 마지막 레코드를 읽은 횟수

 

인덱스 풀 스캔

• 인덱스의 전체를 읽는 방식
• 처음부터 끝까지 모두 탐색

 

사용

• WHERE 절의 조건이 복합 인덱스의 첫 번째 컬럼이 아닌 경우
• 인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있을 경우 (데이터 레코드까지 읽어야 하는 경우는 사용 X)

 

루즈 인덱스 스캔

• 필요한 인덱스 값만 건너뛰면서 읽음

 

사용

• GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우만

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

• category + price 복합 인덱스가 있다면
• category 별 최소 price 값만 찾고 다음 category로 이동

 

인덱스 스킵 스캔

• 비교 조건에 없는 컬럼을 뛰어넘어 나머지 컬럼만으로도 조회할 수 있는 기능
• 앞에 있는 컬럼의 유니크한 값을 모두 조회해서 주어진 쿼리에 조건을 추가해서 다시 실행하는 형태

 

조건

• 비교 조건의 컬럼의 순서가 인덱스의 순서와 일치해야 함 (인덱스를 구성하는 컬럼의 순서가 매우 중요)
• 쿼리의 조건이 인덱스에 존재하는 컬럼만으로 처리가 가능해야 함

 

예

SELECT * FROM employees WHERE age = 30;

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

 

효율적인 작업

• 선행 컬럼의 유니크한 값의 개수가 적어야 합니다.

 

5. 다중 컬럼 인덱스

• 두 개 이상의 컬럼들로 구성된 인덱스

 

특징

두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬돼 있습니다.

• 첫 번째 컬럼이 먼저 정렬된 후 그 안에서 두 번째 컬럼이 정렬되는 방식
• 인덱스 내에서 각 칼럼의 위치가 상당히 중요합니다.

 

6. 정렬 및 스캔 방향

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

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

 

 

인덱스 스캔 방향

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

 

정순 스캔

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

 

역순 스캔

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

 

내림차순 인덱스

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

 

7. 가용성과 효율성

비교 조건

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

 

필터링

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

 

가용성

왼쪽 기준 정렬 기반

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

 

효율성 판단

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

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