[MySQL] B-Tree 인덱스

인덱스를 설명할 때에는 주로 책 뒤에 색인을 사례로 말하는 경우가 많다. 사실 DBMS도 크게 다르지 않다. 색인을 통해 페이지 번호를 알아내는 것처럼 DBMS도 인덱스를 통해 컬럼의 값을 미리 정렬, 보관하고 필요하면 꺼내쓰는 형식이기 때문이다. 여기서 중요한 것은 정렬이다. 

정렬을 해두었을 때 장단점이 있다. 장점은 데이터를 찾는게 쉽다. 서점에 가면 책이 ㄱ,ㄴ,ㄷ 순으로 되어있기 때문에 원하는 책을 찾는게 좀더 쉽다. 만약 이 순서대로 되어있지 않다면 책장 전체를 살펴봐야하고, 심할경우 서점 전체를 살펴봐야한다. 

단점은 Create/Update/Delete 등 데이터가 갱신될때마다 재정렬해줘야 하기 때문에 시간이 오래걸린다는 것이다. 즉 DBMS에서 인덱스를 사용한다는 것은 Create/Update/Delete 의 속도를 희생하여 조회속도를 올리는 것이라 할 수 있다. 따라서 인덱스를 하나 더 추가한다는 것의 의미는 데이터의 저장속도에 얼마나 더 희생시킬 것인지와, 읽기 속도를 얼마나 빠르게 할 것인지 결정하는 것이다. 그래서 where조건에 사용되는 컬럼이라고 전부 인덱스를 생성하면 데이터 저장 성능이 떨어지고 인덱스 크기만 비대해져 역효과가 나기도 한다.

DBMS에서 자주 사용하는 인덱스는 크게 2가지로 B-Tree 인덱스와 해시 인덱스가 있다. 여기서는 B-Tree만 다룬다.

---

# B-Tree 인덱스란?

컬럼의 원래 값을 볂여시키지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지하고 있다. 전문 검색과 같은 특수한 사항이 아닌 경우 대부분 B-Tree를 사용할 정도로 일반적이다. 

참고로 B-Tree 의 "B"는 "Binary(이진)"의 약자가 아니라 "Balanced"를 의미한다. 

B-Tree는 3개의 노드(Node)로 분류된다. 

- Root Node: 최상위 노드 

- Leaf Node: 최하위 노드 

- Branch Node: 루트와 리프 노드를 연결하는 노드. 

# Data Block: 테이블 row의 실제 저장소.

B-Tree에 저장될 때는 저장될 키값을 이용해 B-Tree상의 적당한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키값과 주소정보를 B-Tree의 리프노드에 저장한다. 만약 리프노드가 꽉 찼다면 리프노드가 분리되어야 하며, 이는 상위 브랜치 노드까지 처리범위가 확대된다. 이러한 이유로 B-Tree는 쓰기작업에 비용이 많이 드는것으로 알려져있다. 

인덱스 키 추가 

테이블에 레코드 추가하는 비용을 1로 기준했을 때, 인덱스를 추가할 떄에는 1~1.5로 보는 것이 일반적이다. 그래서 테이블 인덱스가 3개있다면 조회시 5.5의 비용(1.5*3) 정도로 예측할 수 있다. 중요한건 이 비용의 대부분이 메모리와 CPU의 처리가 아닌, 디스크로부터 인덱스 페이지를 읽고 쓰는게 대부분이다.

인덱스 키 변경

먼저 키값을 삭제한 후, 다시 새로운 키값을 추가하는 형태로 처리된다. 단순히 키값만 변경하는 것은 불가능하다. 

# Tip) 인덱스를 바꿀 수 없는 상황이라면 어떻게 하는게 좋을까?

실제로 인덱스를 수정하는 것은 매우 많은 부하를 일으키기에 때에 따라선 조절이 불가능할 때도 있다.

그럴땐 IN을 이용해 다른 중복값이 높은 다른 인덱스를 이용할 수 있도록 수정한다.

중복값이 많을수록 IN 의 효율이 증가한다.

인덱스 키 삭제

삭제의 경우는 리프노드를 찾아 삭제마크만 하면 작업이 완료된다.  

인덱스 키값 크기 

인덱스는 페이지 단위로 관리도며, 루트/브랜치/리프 노드를 구분한 기준이 페이지단위 이다. 인덱스를 구성하는 키값의 크기가 커지면 디스크로부터 읽어야하는 횟수가 늘어나고 느려짐을 의미한다. 그리고 메모리(Buffer pool)에 캐시해둘 수 있는 레코드 수도 줄어든다는 의미이다. 

때론 인덱스를 사용하지 않는게 더 효율적

조회하는 데이터가 전체의 25%이상이면 인덱스를 사용하지 않는것이 유리하다. 테이블에서 직접 레코드를 1건 읽는것에 비해 3~5배정도 비용을 더 많이 쓰는 작업으로 예측하기 때문에, 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는 필터링 방식으로 처리하는 것이 효율적이다.

인덱스를 사용하지 못하는 경우

- EQUAL로 비교되지 않는 경우:  

where col <> 'Y'  

where col NOT IN (1, 2, 3) 

where col NOT BETWEEN 1 AND 10 

where col IS NOT NULL << MySQL 에서는 NULL값도 인덱스로 관리됨 

- Like 문으로 뒷부분일치하게 문자열 패턴을 비교하는 경우 

where col like '%TEST' 

- 인덱스 컬럼이 변형되는 경우 

where substring(col, 1) = 'A' 

- 데이터타입이 서로 다른 비교 

where char_col = 10

단일, 복합 인덱스 스캔 효율

- 단일 컬럼 인덱스 => 중복이 적고, 종류가 많을수록 유리함.

예) 회원번호, 계좌번호

- 복합 컬럼 인덱스 => 중복이 높은순서대로 잡는것이 유리함

예) 성별-연령대-회원번호, 은행명-통장종류-계좌번호

In은 범위조회가 아니다.

해당 값을 찾기위해 수직적으로 탐색을 시작함.

실질적으로 IN쿼리는 아래와 같은 방법으로 수행한다.

@작성쿼리 

select * 

from t 

where c1 in ('A', 'K') 

@실제수행 

select * 

from t 

where c1 = 'A' 

union all 

select 

from 

where c1 = 'K'

참조 

[MySQL] B-Tree 인덱스 

http://12bme.tistory.com/138