CH 5 인덱스(5.3) | Wonny's note

5.3 B-Tree 인덱스

B-Tree 의 B는 Balanced 를 의미한다. B-Tree는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지하고 있다.

5.3.1 구조 및 특성

B-Tree는 트리 구조의 최상위에 하나의 루트 노드 가 존재하고 그 하위에 자식 노드가 붙어있는 형태다. 트리 구조의 가장 하위에 있는 노드를 리프 노드라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 브랜치 노드라고 한다. 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고있다.

인덱스의 키값은 모두 정렬되어 있지만 데이터 파일의 레코드는 정렬되어 있지 않다. 레코드 생성시 insert된 순서대로 저장되어 있다고 생각하기 쉽지만, 일반적으로 DBMS는 레코드가 삭제된 공간을 재활용 하므로 순서대로 되어있지 않다.

인덱스는 테이블의 키 칼럼만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가지게 된다.

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

인덱스 키 추가

새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. B-Tree에 저장될 때는 저장될 키값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다. 만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리되야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것으로 알려졌다.

새로운 인덱스 추가 작업에 대한 비용은 대략적으로 계산이 가능하다. 테이블에 레코드를 추가하는 작업 비용을 1이라고 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1~1.5 정도로 예측하는것이 일반적이다. 하지만 여기서 주의해야 할 점은 작업 비용이 CPU에서 들어가는 비용이 아니라 디스크에서 이루어 지기 때문에 시간이 오래걸린다는 점이다.

MyISAM스토리지 엔진은 “delay-key-write” 파라메터를 설정해 인덱스 키 추가 작업을 미뤄서 처리할 수 있는데, 이는 동시작업에 적합하지 않다. InnoDB 스토리지 엔진은 키를 추가하는 작업을 조금 더 효율적으로 처리하는데, 상황에 따라 인덱스 키 추가적업을 지연시킬지 바로처리할지를 결정한다. 그 과정은 다음과 같다.

사용자의 쿼리 실행
InnoDB의 버퍼 풀에 새로운 키 값을 추가해야 할 페이지가 존재한다면 즉시 키 추가 작업 처리
버퍼 풀에 B-Tree의 리프 노드가 없다면 인서트 버퍼에 추가할 키값과 레코드의 주소를 임시로 기록해 두고 작업 완료
백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 머지해야 할 인덱스 키값이 있는지 확인한 후, 있다면 병합함
데이터베이스 서버 자원의 여유가 생기면 Mysql 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 머지시킴

인덱스 키 삭제

B-Tree의 키값이 삭제되는 작업은 간단하다. B-Tree에 저장된 키 값을 찾아 삭제 마크를 남긴다.

인덱스 키 변경

B-Tree의 키 값의 변경작업은 먼저 키값을 삭제한 후, 다시 새로운 키값을 추가하는 형태로 처리된다.

인덱스 키 검색

인덱스를 구축하는 이유는 바로 빠른 검색을 위해서다. B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있다. 부등호 비교나 값의 뒷부분이 일치하는 경우에는 B-Tree인덱스를 이용한 검색이 불가능하다. 또한 인덱스를 이용한 검색에서 중요한 사실은 인덱스의 키값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다는것이다.

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

인덱스 키값의 크기

InnoDB 엔진은 디스크에 데이터를 저장하는 가장 기본 단위 페이지(Page) 또는 블록이라고 하며, 디스크의 모든 읽기 쓰기의 기본단위가 된다. 인덱스도 페이지 단위로 관리되며, B-Tree의 브랜치, 리프 노드를 구분한 기준이 바로 페이지 단위이다.

이진(Binary) 트리는 각 노드가 자식 노드를 2개만 가지는데 B-Tree가 이진트리라면 인덱스 검색이 상당히 비효율적일 것이다. 일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조이다. B-Tree의 자식 노드의 갯수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다.

만약 인덱스의 키가 16바이트고 InnoDB의 페이지 크기가 16KB이면 인덱스 키 16바이트와 자식노드 정보 12바이트를 추가시켜서 계산하면 16*1024/(16+12) = 585 개 저장 가능하다. 인덱스 키 값이 커지면 디스크로 부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미한다.

또한 인덱스 키 값의 길이가 길어지면 인덱스를 캐시해 두는 버퍼 풀에 캐시할 수 있는 레코드 수가 줄어들게 되므로 메모리의 효율이 떨어지게 된다.

B-Tree 깊이

인덱스의 키 값이 늘어나면 B-Tree의 깊이가 3인 경우, 키값이 16바이트 일때 최대 2억(585 x 585 x 585)개 정도의 키값을 담을 수 있지만 키값이 32바이트로 늘어나면 5천만(372 x 372 x 372)개로 줄어든다. B-Tree의 깊이는 검색수행시 디스크를 몇번이나 랜덤하게 읽어야 하는지와 직결되는 문제이므로 인덱스의 키 값이 커지면 디스크 읽기 작업이 많아진다.

선택도(기수성)

인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스키값 가운데 유니크한 값의 수를 의미한다. 전체 인덱스 키값은 100개인데, 그중에서 유니크한 값의 수는 10개라면 기수성은 10이다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

칼럼의 유니크값과 검색 효율에 대한 예를 들어보겟다

CREATE TABLE tb_city(
	country VARCHAR(10),
	city VARCHAR(10),
	INDEX ix_country (country)
);

위와같은 테이블을 만들고 다음과 같은 상황을 가정하자

tb_city 에는 1만건의 레코드 존재
각 국가와 도시가 중복되어 저장되있지 않음

그리고 다음과 같은 쿼리를 실행해보자

1	select * from tb_test where country='korea' and city='seoul';

country의 유니크 값이 10개
country 칼럼의 유니크 값이 10개 이므로 10000/10 해서 1000개 정도의 값이 일치하리라 예측된다. 하지만 검색된 1000건 가운데 city=’seoul’은 1건이므로 999건은 불필요하게 읽은 것으로 볼 수 있다.
country의 유니크 값이 1000개
country 칼럼의 유니크 값이 10개 이므로 10개 정도의 값이 예측되며 해당하는 레코드는 1개 이므로 9건이 불필요하게 읽어졌다.

이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미치게 된다.

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 인덱스를 이용한 읽기의 손익 분기점을 판단할 필요가 있는데, 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 더 비용이 많이 드는 작업인 것으로 예측한다. 즉, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.

손익 분기점인 20~25%를 넘어서는 경우 옵티마이저는 인덱스를 이용하지 않고 직접 테이블을 처음부터 끝까지 읽어서 처리할 것이다.

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

인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 루트노드에서 부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가서 시작지점을 찾는다. 시작위치부터 리프노드의 레코드만 순서대로 읽는다. 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 반환한다.

인덱스를 스캔하는 방향과는 상관없이 해당 인덱스를 구성하는 칼럼의 정순 또는 역순으로 정렬된 상태의 레코드를 가져온다. 이는 별도의 정렬 과정이 수반되는 것이 아니라 인덱스 자체의 정렬 특성 때문에 자동으로 그렇게 된다.

인덱스의 검색 조건에 해당하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다. 그래서 검색된 레코드 건수 만큼 랜덤I/O가 실행 되는데 이 작업은 비용이 많이드는 관계로 인덱스 사용 여부에 영향을 미친다.

인덱스 풀 스캔

일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다. 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다. 인덱스 뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않는다.

인덱스에 포함된 칼럼만으로 쿼리를 처리할 경우 테이블의 레코드를 읽을 필요가 없다. 인덱스의 전체 크기는 테이블 자체의 크기보다 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O로 쿼리를 처리할 수 있다.

루스 인덱스 스캔

루스 인덱스 스캔은 말 그대로 느슨하게 듬성듬성 인덱스를 읽는 것을 말한다. 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간마다 필요치 않은 인덱스 키값은 무시하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 Group by 또는 집합 함수 가운데 Max(), Min() 함수에 대해 최적화 하는 경우에 사용된다.

5.3.5 다중 칼럼(Multi-column) 인덱스

인덱스가 다중으로 설정되어 있을 때 인덱스 구성은 첫번째 칼럼에 의존해서 정렬되어 있다. 다중 칼럼 인덱스에서 인덱스 내에 각 칼럼의 위치가 상당히 중요하며, 신중히 결정해야 하는 이유는 인덱스 순서에 따른 컬럼 정렬이 바뀌기 때문이다.

B-Tree 인덱스의 정렬 및 스캔 방향

인덱스의 정렬

일반적으로 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 칼럼의 정렬을 설정할 수 있다. 인덱스의 모든 칼럼을 오름차순 또는 내림차순으로만 생성하는 것은 아무런 문제가 되지 않는다. 하지만 가끔 인덱스를 구성하는 칼럼 가운데 오름차순과 내림차순을 혼합해서 만들어야 할 때가 있다. Mysql에서는 칼럼의 값을 역으로 변환해서 구현하는 것이 유일한 방법이다.

인덱스의 스캔 방향

인덱스는 항상 오름차순으로만 정렬돼 있지만 인덱스를 최소값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다는 것을 옵티마이저는 알고있다. 인덱스를 역순으로 정렬되게 할 수는 없지만 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다. 인덱스를 오름차순으로 일그면 최종적으로 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과이며, 내림차순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 되는 것이다.

쿼리의 order by 처리나 min(), max() 함수 등의 최적화가 필요한 경우, mysql 옵티마이저는 인덱스의 읽기 방향을 전환해서 사용하도록 실행 계획을 만들어 낸다.

5.3.7 B-Tree 인덱스의 가용성과 효율성

여기서는 어떤 조건에서 인덱스를 사용할 수 있고 없는지, 또한 일부만 이용하게 되는지도 함께 살펴보겟다.

비교 조건의 종류와 효율성

다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등비교인지 아니면 범위조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라진다.

다음과같은 예를 들어보자

테이블 dept_emp 는 dept_no 와 emp_no 가 인덱스로 설정되어 있다.
케이스 A : dept_no + emp_no
케이스 B : emp_no + dept_no

그리고 다음과 같은 쿼리를 날려보자

1 2	select * from dept_emp where dept_no='d002' and emp_no >= 10114;

케이스 A의 경우 dept_no에 해당하는 레코드를 찾고, 그 이후에는 dept_no에 해당하는 값이 아닐때 까지 죽 읽기만 하면 된다. 하지만 케이스B는 범위 조건에 맞는 emp_no를 찾고 거기서 dept_no 를 다시 조회해야 한다.

케이스A 에서 두번째 인덱스인 emp_no는 비교 작업의 범위를 좁히는데 도움을 준다. 하지만 케이스B 에서 emp_no는 비교작업의 범위를 좁히는데 아무런 도움이 되지 않는다.

공식적인 명칭은 아니지만 케이스A같이 작업의 범위를 결정하는 조건을 “작업 범위 결정 조건”이라 하고, 케이스B 처럼 작업 범위를 좁히지 못하고 단순히 거름종이 역할만을 하는 것을 “필터링 조건” 또는 “체크 조건” 이라고 표현한다.

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것이다. 여기서 왼쪽이라 함은 하나의 칼럼 내에서뿐만 아니라 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용된다.

케이스 A : Index(first_name)
케이스 B : Index(dept_no, emp_no)

하나의 칼럼으로 검색할 경우 값의 왼쪽부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다. 또한 다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

케이스 A

1	select * from employees where first_name like '%mer';

위 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다. 그 이유는 검색 칼럼의 가장 첫 글자를 비교해야 하는데 처음값이 고정되지 않았기 때문이다.

케이스 B

1	select * from dept_emp where emp_no>=10144;

인덱스가 dept_no를 기준으로 정렬되어 있는데 emp_no만으로 검색을 하면 효율적인 검색이 되질 않는다.

가용성과 효율성 판단

기본적으로 B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없다.

NOT-EQUAL로 비교된 경우(“<>”, “NOT IN”, “NOT BETWEEN”, “IS NOT NULL”)
LIKE “%??” (앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
스토어드 함수나 다른 연산자로 인덱스 칼럼이 변경된 후 비교된 경우
NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)
문자열 데이터 타입의 골레이션이 다른 경우

다른 일반적인 DBMS에서는 NULL 값은 인덱스에 저장되지 않지만 MYSQL에서는 NULL 값도 인덱스로 관리된다.

1	....where column is null

다중 칼럼으로 만들어진 인덱스는 어떤 조건에서 사용될 수 있고, 어떤 경우에는 절대 사용될 수 없는지 살펴보자. 다음과 같은 인덱스가 있다고 가정해보자.

1	index ix_test(col_1, col_2, col_3, ... ,col_n)

작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
- col_1 칼럼에 대한 조건이 없는경우
- col_1 칼럼의 비교 조건이 위의 인덱스 사용불가 조건 중 하나인 경우
작업 범위 결정 조건으로 인덱스를 사용하는 경우(i는 2보다 크고 n보다 작은 임의의 값을 의미)
- col1~col(i-1) 칼럼까지 equal 형태로(또는 in) 비교
- col_i 칼럼에 대해 다음 연산자 중 하나로 비교
  - equal
  - 크다 작다 형태
  - like로 좌측 일치 패턴

작업 범위 결정 조건으로 인덱스를 사용하는 쿼리 패턴은 이 밖에도 상당히 많이 있겟지만, 대표적인 것들을 기억해 두면 좀 더 효율적인 쿼리를 쉽게 작성할 수 있을 것이다.