B-Tree

B-Tree(B(Balanced)-Tree)란?

Database에서 데이터가 저장되는 자료구조

구조 및 특성

RDBMS에서 btree의 변형인 B+Tree, B*-Tree 유형도 사용

인덱스는 테이블의 키 칼럼만 가지고 있으므로 키칼럼을 읽어 실제 데이터가 있는 곳에 가서 조회해야 한다.

최상위	Root Node
중간	Branch Node
하단(실제 데이터 컬럼을 찾아가는 주솟값을 가지고 있음)	Leaf Node

B-Tree 인덱스 키 추가 및 삭제

인덱스 키 추가, 삭제, 변경 등은 MySQL v5.5 이후 (InnoDB엔진) 체인지 버퍼를 통해 지연 처리 가능

• 인덱스 키 추가
  • 저장될 키 값을 이용해 B-Tree내부의 적절한 위치 검색
  • 저장될 위치가 정해지면 데이터의 위치를 담는 leaf Node에 저장
• 인덱스 키 삭제
  • 삭제할 키값이 저장된 b-tree노드를 찾아 마킹
• 인덱스 키 변경
  • 인덱스의 키 값만 변경하는 것이 불가능하므로 먼저 삭제 후 추가해야 함
• 인덱스 키 검색(트리탐색)
  • Root Node → Branch Node → Leaf Node순서대로 탐색

---

B-Tree 인덱스 사용에 영향을 미치는 요소

1. 인덱스 키 값의 크기

• 인덱스의 페이지 크기와 키값에 따라 인덱스가 가지는 노드 개수 결정 됨
• innodb_page_size 시스템 변수를 통해 페이지 사이즈 설정 가능
• 기본 : 16KB, 4~64KB까지 설정 가능

2. B-Tree 깊이

• B-Tree 깊이는 MySQL에서 값을 검색 시 디스크를 읽어야 하는 횟수와 직결됨
• 인덱스 키값의 크기가 커질 수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수 감소 그러므로 같은 레코드 건수라도 B-Tree깊이가 깊어져서 디스크 읽기 수가 증가

3. 선택도(기수성 Cardinality)

• 인덱스 키 값 가운데 유니크 한 값의 수
• 유니크한 값의 개수가 낮을 수록 검색 대상이 증가하므로 성능에 영향을 주는 요소가 됨

4. 읽어야 하는 레코드의 건수

• 테이블의 레코드를 직접 읽는것보다 인덱스를 통해 테이블의 레코드를 읽는 것이 높은 비용의 작업
• 인덱스를 통해 읽어야 하는 레코드 수가 전체 중 20 ~ 25%를 넘어가면 테이블의 전체 레코드를 조회하는 게 효율적

---

B-Tree 인덱스를 통한 데이터 읽기

MySQL이 인덱스를 이용해 레코드를 읽는 방법 소개

1. 인덱스 레인지 스캔

인덱스 접근 방법 중 대표적이며 빠른 방법

Btree의 필요한 영역을 스캔하는 방법

Root → Branch → Leaf Node를 차례대로 스캔하여 필요한 Leaf Node만 스캔하는 방식

Leaf Node에서 저장된 레코드 주소로 데이터를 읽어올 때 레코드마다 random I/O가 발생하여 인덱스로 읽어야 할 데이터가 전체의 20 ~ 25%가 넘는다면 인덱스를 통해 레코드를 읽기보다는 테이블을 통해 직접 읽는 것이 효율적

2. 인덱스 풀 스캔

• 인덱스의 처음부터 끝까지 모두 읽는 방식
• 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번쨰 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용
• 예) index 구성 : column A, column B, column C 쿼리 조건절 사용된 칼럼 : column B, column C
• 인덱스에 설정된 칼럼만으로 쿼리 결과를 뽑을 수 있을 때 인덱스 풀 스캔이 적용
• 테이블 풀 스캔 > 인덱스 풀 스캔 > 인덱스 레인지 스캔

3. 루스(Loose) 인덱스 스캔

• Loose의 말뜻처럼 듬성듬성 인덱스를 스캔하는 방식
• MySQL 8.0부터 지원되며 다른 상용 RDBMS의 인덱스 스킵 스캔과 유사
• 인덱스 레인지 스캔과 유사 하지만 중간중간 필요하지 않은 인덱스 키값은 무시하고 다음 필요한 인덱스를 읽음

4. 인덱스 스킵 스캔

ALTER TABLE employees ADD INDEX ix_gender_birth(gender, birth_date);

employees테이블의 gender, birth로 구성된 결합칼럼 인덱스 생성

하지만 아래 쿼리에서는 위에서 생성한 인덱스를 사용할 수 없다.

인덱스의 첫 번째 칼럼이 where절에 검색조건으로 와야 하기 때문이다.

인덱스 스킵 조건을 통해 아래의 쿼리에서도 인덱스에 접근가능하게 할 수 있다.

-- 인덱스 사용 못함
SELECT * FROM employees WHERE birth_date >= '1995-01-01';

-- 인덱스 사용 가능
SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1995-01-01';

MySQL 8.0부터 도입된 인덱스 스캔 설정 활성화를 통해 위의 쿼리에서도 인덱스에 접근가능하게 할 수 있다.

SET optimizer_swithch='skip_scan'=on';

gender에서 유니크 값을 모두 조회해 위의 쿼리 실행 시 gender에 대한 조건을 추가하여 쿼리를 다시 실행한다.

조건절에 빠진 인덱스 칼럼의 distinct value 개수가 적고 후행 컬럼의 distinct value 개수가 많을 경우 사용 유리

→ distinct value 개수가 적다

예) 컬럼 gender : ‘M’, ‘W’처럼 중복 없이 값이 적은 경우를 말한다.

---

[참고]

real MySQL 8.0

http://wiki.gurubee.net/pages/viewpage.action?pageId=4949506

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=weekamp&logNo=221600846268