[Real MySQL] 8-2. 인덱스: 구현 (B-Tree)

"Real MySQL" 책을 정리한 포스팅 입니다

 

1. 특성

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

 

리프 노드

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

 

2. 키 추가 및 삭제

• 레코드를 저장하거나 변경하는 경우 필요

 

추가

• 저장될 키 값을 이용해 추가될 위치 검색 (B-Tree 인덱스 상에서)
• 적절한 위치를 찾아내면, 리프 노드에 저장

 

삭제

• 해당 키 값이 저장된 리프 노드를 찾아 삭제 표시
• 지연 삭제 (버퍼링)

 

변경

• 먼저 키 값을 삭제
• 새로운 키 값 추가

 

검색

• 루트 노드 -> 브랜치 노드 -> 최종 리프 노드 (비교 작업)
• 빠름: 100% 일치 또는 앞부분만 일치
• 느림: 키 값의 뒷부분으로 검색
• 불가: 키 값 변형

 

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

인덱스 키 값의 크기

페이지 (블록)

• 데이터 기본 단위
• 모든 읽기 및 쓰기 작업의 최소 작업 단위
• 기본 크기: 16KB (innodb_page_size)

 

노드

• 키 값 + 자식 노드 주소

 

자식 노드

• 키 값 + 행 주소 (논리적)
• 수: 가변적
• 페이지 크기와 키 값이 크기에 따라 달라집니다.

 

깊이

• 깊어지면 디스크 읽기가 더 많이 필요해짐
• 키 값의 길이가 커지면 하나의 인덱스 페이지가 담을 수 있는 키 값의 개수가 적어짐

 

선택도 (기수성)

• 모든 인덱스 키 값 가운데 유니크한 값의 수
• 선택도가 높아 인덱스 키 값 가운데 중복된 값이 많아지만 쓸데없는 읽기낭비가 많아진다.
• 유니크한 인덱스 키 값의 개수가 많을 수록 선택도가 낮아집니다.

 

읽어야 하는 레코드 건수

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

 

4. 데이터 읽기

인덱스 레인지 스캔

• 인덱스를 통해 한건 이상을 읽는 경우에 사용하는 방법입니다.
• 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
• 레코드 한건 단위로 랜덤 I/O가 일어납니다.

 

과정

• 인덱스 탐색: 인덱스에서 조건을 만족하는 값의 저장된 위치 찾기
• 인덱스 스캔: 인덱스 시작점에서 순서대로 쭉 읽는다

 

상태 변수

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

 

인덱스 풀 스캔

• 인덱스의 처음부터 끝까지 모두 읽는 방식

 

사용

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

 

루즈 인덱스 스캔

• 듬성듬성하게 인덱스를 읽는 것을 의미
• 읽는 중에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리

 

사용

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

 

인덱스 스킵 스캔

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

 

조건

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

 

효율적인 작업

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

 

다중 컬럼 인덱스

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

 

정렬 및 스캔 방향

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

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

 

 

인덱스 스캔 방향

• 쿼리가 그 인덱스를 사용하는 시점에 읽는 방향에 따라 역순의 정렬 효과를 얻을 수 있다.

 

내림차순 인덱스

• 인덱스 키의 큰 값이 B-Tree 의 왼쪽으로 정렬된 인덱스
• 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조
• 정순 스캔 : 왼쪽에서 오른쪽으로 스캔
  • 페이지 잠금
• 역순 스캔 : 오른쪽에서 왼쪽으로 스캔
  
  • 정순 스캔보다 30%정도 느립니다.

 

가용성과 효율성

비교 조건의 종료와 효율성

• 각 컬럼의 순서와 조건에 따라 인덱스 컬럼 활용 형태가 달라지며 효율도 달라진다.
• 필터링
  • 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업
  • 비교 작업의 범위를 좁히는데 도움을 주지 못하는 컬럼
• 작업 범위 결정 조건
  • 작업의 범위를 결정하는 조건
  • 비교 작업의 범위를 좁히는데 도움을 주는 컬럼

 

가용성

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

 

가용성과 효율성 판단

• 아래 경우는 작업 범위 결정 조건으로 사용할 수 없습니다.
  • NOT EQUAL : <>, NOT IN, NOT BETWEEN, IS NOT NULL
  • LIKE '%??'
  • 컬럼이 변형된 경우 : 스토어드 함수(DAYOFMONTH), 연산자(SUBSTRING)
  • 데이터 타입이 서로 다른 비교
  • 문자열 데이터 타입의 콜레이션이 다른 경우