B-Tree 인덱스

B-Tree 인덱스

• ‘B’는 “Balanced”를 의미한다. 즉 B Tree는 균형 트리다.
• DBMS에서는 주로 B+ Tree 또는 B* Tree가 사용된다.
• 칼럼의 값을 변형시키지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지하고 있다.

구조 및 특성

• 루트 노드 : 트리 구조의 최상위 노드
• 리프 노드 : 트리 구조의 최하단 노드
  • 실제 데이터 레코드를 찾기 위한 주소 값을 가지고 있다.
• 브랜치 노드 : 루트 노드와 리프 노드 중간에 있는 노드
• 인덱스의 키값은 모두 정렬되어 있지만 데이터 파일의 레코드는 정렬되어 있지 않고 임의의 순서대로 저장되어 있다.
  • 레코드가 삭제되어 빈 공간이 생기면 다음 INSERT는 가능한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문

InnoDB 테이블에서는 기본적으로 PK 순서대로 정렬되어 저장된다. (클러스터링 테이블)

PK값 자체가 레코드의 주소 역할을 한다.

인덱스 키 추가 및 삭제

인덱스 키 추가

• B Tree상에 저장될 키값의 위치를 검색한다.
• 레코드의 키값과 주소 정보를 리프 노드에 저장한다.
• 리프 노드가 꽉 차서 저장할 수 없을 때는 분리한다.
  • 상위 브랜치까지 처리 범위가 넓어짐
    • 쓰기 작업에 비용이 많이 든다.

테이블에 레코드를 추가하는 작업을 1이라고 하면, 인덱스에 키를 추가하는 작업은 1.5로 예측한다. 비용의 대부분이 메모리가 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 하기 때문에 시간이 오래 걸린다.

InnoDB엔진은 인덱스 추가 작업을 상황에 따라 바로 처리할 것인지, 나중에 백그라운드에서 처리할 것인지 결정한다.(버퍼링)

인덱스 키 삭제

해당 키값이 저장된 B Tree 의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료된다. 디스크 I/O는 여전히 필요한 작업이다.

인덱스 키 변경

1. 키값을 삭제한다.
2. 갱신되는 키값을 다시 추가한다.

인덱스 키 검색

• 루트 노드부터 리프 노드까지 이동하면서 비교 작업을 수행한다.(트리 탐색)
• UPDATE나 DELETE를 처리하기 위해 레코드를 먼저 검색해야 할 경우에도 빠른 검색이 가능하다.
• 검색은 완전 일치 또는 값의 앞부분(leftmost part)만 일치하는 경우에 사용할 수 있다.
  • 부등호 비교나 값의 뒷부분이 일치하는 경우는 인덱스를 이용한 검색이 불가능하다.
• 인덱스의 키값에 변형이 일어난 뒤 비교되는 경우에는 빠른 검색이 불가능하다.
• InnoDB 테이블에서 지원하는 레코드 락이나 갭 락은 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식
  • UPDATE나 DELETE 시에 적절한 인덱스가 없으면 불필요하게 많은 레코드를 잠근다.
  • 인덱스의 설계가 중요하다.

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

인덱스 키값의 크기

InnoDB 엔진은 디스크에 데이터를 저장하는 기본 단위를 페이지 또는 블록이라고 하며 디스크의 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 또한 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이다. 인덱스도 페이지 단위로 관리된다.

B Tree의 자식 노드의 갯수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. InnoDB의 모든 페이지 크기는 16KB로 고정되어 있다.

인덱스의 키가 16바이트, 자식 노드 주소가 12바이트라고 가정하면, 하나의 인덱스 페이지에 16*1024 / 16+12 = 585개 키를 저장 가능하다. 키 값이 커지면 하나의 인덱스 페이지에 저장 가능한 키의 수도 줄어들게 된다.

• 인덱스 키 값이 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만클 느려지게 된다.
• 또한 InnoDB 버퍼 풀의 크기는 제한적이므로 인덱스의 크기가 커지면 캐시해 둘 수 있는 레코드의 수가 줄어들게 된다.

B Tree 깊이

트리의 깊이는 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다.

인덱스 키값의 크기가 커지면 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 수가 적어지고, 따라서 같은 레코드 수라 하더라도 트리가 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.

선택도 (기수성)

모든 인덱스 키값 가운데 유니크한 값의 수를 의미한다.

인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 빠르게 처리된다.

읽어야 하는 레코드의 건수

옵티마이저는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 읽는 것보다 4~5배 비용이 더 드는 작업으로 예측한다.

많은 레코드( 전체 레코드의 20~25% 이상 )을 읽을 때는 옵티마이저는 인덱스를 사용하지 않고 직접 테이블을 처음부터 끝까지 읽어서 처리한다.

Reference

책 Real MySQL, 이성욱 저