소개

B-Tree 의 B는 "Balanced"를 의미한다. 전문 검색과 같은 특수 요건이 아닌 경우 대부분의 인덱스는 거의 B-Tree 를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

5.3.1 구조 및 특성

B-Tree 는 트리구조의 최상위에 하나의 "루트노드 "가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다. 트리 구조의 가장 하위에 있는 노드를 "리프노드" 라고 하고, 트리구조에서 루트노드도 아니고 리프노드도 아닌 중간의 노드를 "브랜치 노드" 라고 한다. 인덱스의 키값은 모두 정렬돼 있지만 데이터 파일의 레코드는 정렬대 있지 않고 임의의 순서대로 저장돼 있다. 많은 사람들이 데이터 파일의 레코드는 Insert 순서대로 저장된 것으로 생각하지만 그렇지 않다. 만약 테이블의 레코드를 전혀 삭제나 변경없이 Insert 만 수행한다면 맞을 수도 있지만, 레코드가 삭제되어 빈 공간이 생기면 그다음의 Insert 는 가능한 삭제된 공간을 재활용 하도록 DBMS가설계 되어 있다. 리프노드는 데이터 파일에 저장된 레코드이 주소를 가지계 된다.

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

인덱스 키 추가
B-Tree 에 저장될때는 저장될 키값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree 의 리프노드에 저장한다. 만약 리프노드가 꽉차서 더는 저장할 수 없을 때는 리프노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이러한 작업탓에 B-Tree 는 상대적으로 쓰기 작업에 비용이 많이 드는 것으로 알려졌다. 대락젹으로 테이블에 레코드를 추가하는 작업비용이 1이라고 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1~1.5 정도로 예측하는 것이 일반적이다. 중요한 것은 이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 하기 때문에 시간이 오래 걸린다는 것이다. MyISAM 이나 Memory 스토리지 엔진은 Insert 문장이 실행되면 즉시 새로운 키값을 B-Tree 인덱스에 반영한다. 즉 B-Tree 에 키를 추가하는 작업이 완료될때까지 클라이언트는 쿼리의 결과를 받지 못하고 기다리게 된다. InnoDB 는 좀더 지능적으로 처리하는데, 상황에따라 지연시켜 나중에 처리할지 아니면 바로 처리할지 결정한다.
인덱스 키 삭제
B-Tree 의 키값이 삭제하는 경우는 상당히 간단하다. 해당 키값이 저장된 B-Tree 의 리프노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다.
인덱스 키 변경
인덱스의 키값은 그 값에 따라 저장될 리프노드의 위치가 결정되므로 B-Tree 의 키값이 변경되는 경우에는 단순히 인덱스 상의 키값만 변경하는 것은 불가능하다. B-Tree 의 키값 변경작업은 먼저 키값을 삭제한후, 다시 새로운 키값을 추가하는 형태로 처리된다.
인덱스 키 검색
인덱스를 검색하는 작업은 B-Tree 의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프노드까지 이동하면서 비교작업을 수행한다. 인덱스를 이용한 검색의 중요한 사실은 인덱스의 키값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree 의 빠른 검색 기능을 사용할 수 없다는 것이다.

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

인덱스의 키값의 크기 InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록 이라고 하며, 디스크 모든 읽기 및 쓰기 작업의 최소 작업단위가 된다. 인덱스도 결국은 페이지 단위로 관리되며, 루트와 브랜치, 그리고 리프노드를 구분하는 기준이 바로 페이지 단위다.
하나의 인덱스페이지(16KB)에 몇 개의 키를 저장할 수 있을까? 계산해보면 16*1024/(16+12) = 585 개 저장할 수 있다. 그런데 인덱스키값이 커지면 저장할수 있는 개수가 줄어 디스크로부터 읽어야 하는횟수가 늘어나고, 그만큼 느려진다는 의미이다.
B-Tree 깊이
B-Tree 인덱스의 깊이는 상당히 중요하지만 직접적으로 제어할 방법이 없다. 인덱스의 키갑의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 개수가 작아지고, 그때문에 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미한다. 실제로는 아무리 대용량 데이터 베이스라도 B-Tree 의 깊이가 4~5 이상까지 깊어지는 경우는 거의 발생하지 않는다.
선택도(기수성)
인덱스에서 선택도(selectivity) 또는 기수성(cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키값 가운데 유니크한 값의 수를 의미한다. 인덱스 키값 가운데 중복된 값이 많아지면 많아질수록 카디널리티가 낮아진다. 인덱스는 카디널리티가 높을 수록 검색대상이 줄어들기 때문에 그만큼 빠르게 처리된다.
읽어야 하는 레코드의 건수 인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것 보다 높은 비용이 드는 작업니다. 인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있는데, 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는것이 테이블에서 직접 레코드를 1건 읽는 것보다 4~5 배정보 비용이 많이 드는 작업으로 예측한다. 즉 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25% 를 넘어서면 인덱스를 이용하지 않고 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.

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

Mysql이 인덱스를 이용하는 대표적인 방법 3가지

인덱스 레인지 스캔
가장 대표적인 접근 방식으로 나머지 2가지 접근방식보다 빠른 방법이다. 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 루트노드 부터 브랜치 노드 리프노드로 찾아 들어 시작해야 할 위치를 찾으면 그때부터는 리프노드의 레코드만 순서대로 읽으면 된다.
인덱스 풀 스캔
인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.
루스 인덱스 스캔
오라클의 인덱스 스킵 스캔이라고 하는 작동방식과 비슷하다. 루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간마다 필요치 않은 인덱스 키값은 무시하고 다음으로 넘어가는 형태로 처리한다.

5.3.5 다중 컬럼 인덱스

두개 이상의 컬럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 하며, 또한 2개 이상의 칼럼이 연결되었다고 해서 'Concatenated Index '라고도 한다. 두번째 컬럼의 정렬은 첫번째 칼럼에 의존해서 정렬된다. 다중 컬럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치가 상당히 중요하며 또한 아주 신중히 결정해야 하는 이유가 바로 여기에 있다.

5.3.6 B-Tree 인텍스의 정렬 및 방향

인덱스의 정렬
안타깝게도 Mysql 은 인덱스를 구성하는 칼럼 단위로 정렬방식을 혼합해서 생성하는 기능은 아직 지원하지 않는다.
인덱스 스캔 방향
인덱스를 역순으로 정렬되게 할 수는 없지만 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬효과를 얻을 수 있다. 인덱스를 오름차순으로 읽으면 최종적으로 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과이며, 내림차순으로 일그면 그 결과는 내림차순으로 정렬된 상태가 되는 것이다.

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

쿼리의 where 조건이나 group by 또는 order by 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 한다.

비교조건의 종류와 효율성
다중 컬럼 인덱스에서 컬럼의 순서와 그 칼럼에 사용되는 동등비교 인지 아니면 크다 작다와 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지며, 그 효율 또한 달라진다. 작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능속도를 높이지만 체크 조건은 많다고 해서 쿼리의 처리 성능을 높이지는 못한다.
인덱스의 가용성
B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것이다. 어기서 왼쪽이라 함은 하나의 컬럼 내에서 뿐만아니라 다중 컬럼 인덱스의 칼럼에 대해서도 함께 적용된다. LIKE 검색은 인덱스를 이용할 수 없다.
가용성과 효율성 판단
기본적으로 B-Tree 인덱스의 특성상 다음 조건에선 사용할 수 없다.
1. NOT-EQUAL로 비교된 경우 ("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")
2. LIKE '%??'( 앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
3. 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우( substring(columns, 1,1) )
4. NOT-DETERMINUSTIC 속성의 스토어드 함수가 비교주건에 사용된 경우 ( where column = determinstic_function() )
5. 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우 )
6. 문자열 데이터 타입의 콜레이션이 다른 경우 (where utf8_bin_char_column) = euckr_bin_char_column)

대표적인 것들을 기억해 두면 좀더 효율적인 쿼리를 작성할 수 있다. 여기의 내용은 B-Tree 인덱스의 특징이므로 Mysql 뿐 아니라 대부분의 RDBMS 에도 동일하게 적용된다.