[MySQL] B-Tree 인덱스-1

B-Tree는 데이터베이스의 인덱싱 알고리즘 중 가장 일반적으로 사용된다.

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

 

페이지

인덱스의 저장방식에 대해 이해하려면 페이지에 대한 이해가 필수이다.

페이지는 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 작업 단위이다. 일반적인 인덱스를 포함해 PK와 테이블 등은 모두 페이지 단위로 관리된다.

따라서 페이지에 저장되는 개별 데이터의 크기를 최대한 작게 하여, 1개의 페이지에 많은 데이터들을 저장할 수 있도록 하는 것이 중요하다.

페이지에 저장되는 데이터가 크기가 클수록 디스크 I/O가 많아지고, 메모리에 캐싱할 수 있는 페이지의 수가 줄어들 수 있다.

(디스크I/O를 통해 페이지를 읽어오면 버퍼 풀이라는 메모리에 캐싱해둔다.)

 

B-Tree의 기본적인 구조

B-Tree는 트리 구조의 최상위 하나에 루트 노드가 존재하고, 그 하위에 자식 노드가 붙어있는 형태이다.

트리 구조의 가장 하위에 잇는 노드를 리프 노드, 루트 노드와 리프 노드 중간의 노드를 브랜치 노드라고 한다.

 

B-Tree 자료구조의 특징을 간단하게 보면, 먼저 이진 트리와 다르게 하나의 노드에 여러 값이 들어갈 수 있다.

만약 노드의 데이터 수가 N개라면, 자식 노드의 수는 N+1 개가 되어야하며, 루트 노드를 제외한 모든 노드는 최소 (차수/2)개의 데이터를 가져야한다.

노드 내의 키는 정렬되어있어야 하며, 균형을 위해 leaf노드로 가는 모든 경로의 비용이 같아야한다.

 

B-Tree의 인덱스 구조

인덱스의 키 값은 정렬되어있지만, 데이터 파일의 레코드는 정렬되어있지 않다. 많은 사람들이 데이터 파일의 레코드는 INSERT 된 순서로 저장된다고 생각하지만 그렇지 않다.

(레코드의 변경 없이 INSERT만 수행하면 맞겠지만, MySQL은 기본적으로 레코드의 삭제 등으로 빈공간이 생기면 해당 공간을 활용하여 INSERT된다.)

 

인덱스는 테이블의 키 칼럼만 가지고 있으므로, 결국 나머지 칼럼들을 읽으려면 데이터 파일에서 해당 레코드를 찾아야한다.

이를 위해 인덱스의 리프 노드는 실제 데이터파일에 저장된 레코드의 주소를 가리키게 된다.

 

결국 큰 흐름 자체는 인덱스를 통해 레코드 주소를 찾음 -> 주소를 통해 실제 레코드를 찾음 정도가 된다.

 

하지만 MySQL에서는 MyISAM 테이블과 InnoDB테이블 사이에 세컨더리 인덱스를 통해 실제 레코드를 찾는 과정의 차이가 있다.

(MyISAM vs InnoDB에서 봤듯이 MyISAM은 세컨더리 인덱스가 물리적인 주소를, InnoDB는 논리적 주소를 가지기 때문)

 

 

정확히 이해하는데 상당히 오래걸린 이 InnoDB 테이블의 경우 그림을 보자.

이 그림은 세컨더리 인덱스 (왼쪽 영역) 가 실제 레코드 주소를 가리키는게 아닌 프라이머리키의 주소를 가리킨다.

상기했듯이 InnoDB테이블은 프라이머리 키를 주소처럼 사용하기 때문에 만약 세컨더리 인덱스를 통한 검색의 경우 (위 그림의 경우도 pk가 아닌 name을 칼럼으로 가지는 세컨더리 인덱스) 리프노드에서 바로 실제 레코드를 찾는것이 아닌 프라이머리 키의 주소를 찾는다.

 

이후 과정은 기존 인덱스의 과정과 같이 프라이머리키 인덱스를 통한 탐색을 진행하면 된다.

만약 위의 경우에서 where emp_no = "1" 같은 pk 검색을 시도 시 InnoDB가 자동적으로 생성한 프라이머리 인덱스 탐색만 진행하면 된다.

 

반면 MyISAM 테이블은 세컨더리 인덱스가 실제 레코드의 주소를 가리킨다.

이렇게만 보면 InnoDB 테이블은 모든 세컨더리 인덱스 검색 시 반드시 프라이머리 인덱스 검색 과정을 거쳐야하기 때문에 성능이 떨어질 것 처럼 보이지만, 사실은 각각의 장단점을 가지고 있다. (클러스터링 인덱스 부분에서 다시 살펴볼 예정)

 

B-Tree 인덱스 키 추가

테이블의 레코드를 저장,변경하는 경우 인덱스 키 추가나 삭제 작업이 당연히 발생할 것이다.

 

새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키가 즉시 저장될 수도 있고 아닐 수도 있다.

저장 시에, 저장될 키 값을 이용해 B-Tree의 적절한 위치를 검색하고, 위치가 결정되면 트리의 리프 노드에 레코드 키 : 주소를 저장하는데,

만약 리프노드가 꽉 차는 경우에는 리프노드가 분리된다.

리프노드의 분리는 결국 상위 브랜치노드의 처리범위가 넒어짐을 뜻하고, 이로인해 B-Tree는 새로운 키를 추가하는 작업의 비용이 많이 들기로 알려져있다. 

(작업의 비용이 많이 드는 이유는, 새로운 키를 추가하는 과정이 디스크로부터 인덱스 페이지를 읽고 쓰는데 시간을 소요하기 때문)

 

인덱스 키 삭제

B-Tree에서 키 값이 삭제되는 경우는 간단하다. 그냥 해당하는 리프노드를 찾아서 삭제마크만 하면 끝이다.

이역시 디스크 I/O가 필요한 작업인데, InnoDB테이블에서는 이 작업이 버퍼링되어 지연 처리 될 수 있다. (악영향은 x)

 

인덱스 키 변경

인덱스의 키 값은 그 값에 따라 저장될 리프노드가 결정되므로, 키 값의 변경은 단순히 인덱스상의 값을 변경하는 것으로는 불가능하다.

따라서 키 값을 삭제 -> 추가 하는 형태로 처리된다. InnoDB 테이블에서는 역시나 지연처리 될 수 있다.

 

인덱스 키 검색

결국 많은 희생을 감수하며 인덱스를 구축하는 이유는 바로 빠른 검색을 위해서다.

지금까지 봤듯이 인덱스를 검색하는 작업은 B-Tree의 루트 노드 -> 브랜치 노드 -> 리프 노드를 거치며 비교 작업을 수행하는데

이 과정을 트리 탐색이라고 한다. 이 트리탐색은 SELECT시 뿐만 아니라 UPDATE, DELETE를 처리하기 위해서도 사용된다.

 

B-Tree 인덱스를 이용한 검색은, 100%일치 혹은 값의 앞부분만 일치하는 경우에 사용할 수 있다.

B-Tree 인덱스는 정렬된 구조를 유지하기 때문에 부등호를 활용한 범위 탐색에도 사용할 수 있다.

또한 인덱스의 검색 기능을 사용하기 위해서는 인덱스의 키 값에 변형을 가하면 안된다.

(간단한 예로는, name 컬럼에 UPPER함수를 적용해 검색하려는 경우 인덱스를 타지 못하고 테이블을 풀스캔함)

 

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

인덱스 키 값의 크기

인덱스도 결국 상기한 페이지 단위 로 관리되며, 앞에서 루트, 브랜치, 리프 노드를 구분하는 기준도 페이지이다.

이진트리는 각 노드가 자식 노드를 딱 2개 가지는, 만약 DBMS의 B-Tree가 이진 트리였다면 인덱스 검색이 비효율적이였을 것이다.

 

일반적으로 MySQL의 B-Tree는 자식 노드의 개수가 가변적이다. 자식 노드 개수의 기준은 인덱스의 페이지크기, 키 값의 크기이다.

당연하게도 인덱스의 키 값의 크기가 커지면 하나의 페이지에 저장할 수 있는 키의 개수가 적어지고, 이는 두 가지 문제를 초래한다.

 

- Page를 여러번 읽게 될 수 있다. (디스크 I/O가 여러번 발생할 수 있다)

만약 SELECT 쿼리가 레코드를 500개 읽어야하는데 페이지 하나를 읽는 것으로 해결될 수도 있지만, 인덱스 키 값의 크기가 큰 경우 여러번 읽어야할 수도 있다.

 

- 메모리 효율이 떨어진다.

InnoDB 버퍼 풀 부분에서도 이야기했지만, 버퍼 풀의 크기는 한정적이고, 페이지 단위로 버퍼링하기 때문에

결국 인덱스 키 값의 크기 증가는 버퍼에 캐시할 수 있는 레코드 수가 줄어들게 되고, 메모리 효율이 떨어지게 된다.

 

B-Tree의 깊이

페이지가 늘어난다는 것은 즉 B-Tree의 깊이가 깊어짐을 의미한다. B-Tree 인덱스의 깊이를 직접 제어할 방법은 없다.

결국 똑같은 이야기이지만 인덱스 키 값의 증가는 동일한 개수의 인덱스 키에 대해 많은 페이지를 필요로 하게 되고,
이로인해 같은 레코드 건수에 대한 읽기라도 B-Tree의 깊이가 깊어져 디스크 I/O가 더 많이 필요하게 된다.

 

선택도(카디널리티)

인덱스에서 선택도와 카디널리티는 거의 같은 의미로 사용되며, 뜻 또한 모든 인덱스 키 값 중 유니크한 값의 수를 의미한다. 

전체 인덱스 키 값 100개 중, 유니크 값이 10개라면 카디널리티는 10이다. 중복된 값이 많아질 수록 카디널리티가 낮아진다.
당연히 검색 시 인덱스는 카디널리티가 높을 수록 검색 대상이 줄어들기 때문에 빠르게 처리된다.

(헷갈릴 수 있지만 유니크 값이 10개라는 것은 값의 종류가 10개다 정도로 이해해도 될 듯 하다.)

 

만약 1만 건의 레코드가 있는 tb_test 테이블이 있다고 해보자. country 칼럼으로만 인덱스가 생성된 상태이다.

케이스 a : country 칼럼의 유니크한 값의 개수가 10개

케이스 b : country 칼럼의 유니크한 값의 개수가 1000개

SELECT * FROM tb_best WHERE country='KOREA' and city='SEOUL';

 

MySQL에서는 인덱스의 통계 정보 (유니크한 값의 개수)가 관리되기 때문에, city의 카디널리티는 작업 범위에서 영향을 미치지 못한다.

위 쿼리 실행 시 케이스 a는 평균 1000건, b는 평균 10건이 조회될 수 있음을 인덱스 통계 정보를 통해 예측할 수 있다.

 

만약 a와 b 모두 실제 모든 조건을 만족하는 레코드가 1개 있었다면  a의 인덱스는 적합하지 않은 것이다.

b는 1건의 레코드를 위해 9개의 레코드만 더 읽은것이지만, a는 1개의 레코드를 위해 999개의 쓸모없는 레코드를 더 읽은 셈이다.

 

읽어야 하는 레코드의 건수

테이블에 레코드가 100만건이 저장되어있다고 가정해보자.

만약 그중 50만건의 레코드를 읽어야하는 상황이라면, 전체 테이블을 모두 읽어 50만건을 버리는게 효율적일지,

아니면 인덱스를 통해 필요한 50만건만 읽어오는 것이 효율적인지 판단해야한다.

 

일반적인 DBMS의 옵티마이저는 인덱스를 통해 레코드를 1건 읽는 것이 테이블에서 직접 읽는 것보다 4~5배 더 비용이 드는 것으로 측정한다. 따라서 인덱스를 통해 읽어야할 레코드 건수가 전체 테이블 레코드의 20~25%를 넘어서면 테이블을 직접 모두 읽어서 필요한 레코드만 읽어내는 방식이 더 효율적일 수도 있다.