[ SQL ] B-Tree 와 Index

B-Tree, B-+Tree 란? ( Balanced Tree )

- 2진 트리의 확장, 리프 레벨의 좌우 균형을 유지

 

- 세 가지 종류로 나눠지며, 일반적인 DBMS에서는 주로 B-+Tree와 B-*Tree를 사용

 

- B-트리의 창시자인 루돌프 바이어는 ‘B’가 무엇을 의미하는지 따로 언급하지 않았다. 가장 가능성 있는 대답은 리프 노드를 같은 높이에서 유지시켜주므로 균형잡혀있다는 뜻으로 (balanced)의 B라는 것이다. 혹은, 그가 일했던 보잉 과학 연구소(Boeing Scientific Research Labs)에서의 ‘B’를 의미하는다는 의견도 있다.

 

B-Tree

• 2진트리는 자식노드가 2개다 하지만, B-Tree는 자식노드의 최대숫자가 2보다 크다.
• ( 키가 n개 있으면, 이 노드의 자식은 n+1개 ) 
• 한 노드에 n개의 자료가 배치되면 n차 B-Tree라고 한다.
• 노드의 데이터는 반드시 정렬된 상태여야 한다. 

ex ) 3 2 1 x | 1 2 3 o

 

 

• 위 그림처럼 노드의 자식노드 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에, 큰값들은 오른쪽에, 이 사이 값은 중간에 값을 이루게 된다.

 

• 구조 : 
  • 루트노드 - 최상위에 위치한 노드
  • 브랜치 노드 - 중간에 위치한 노드
  • 리프 노드 - 하위에 위치한 노드

 

B-+Tree 

• B-Tree의 형태 중 하나 ( Mysql에 사용되어짐 )
• 리프 노드가 링크드 리스트(linked list)로 서로 연결되어 있고, 저장된 키는 정렬되어 있어서 순차 처리가 용이하다.  ( 범위를 검색하는데 유리함 )
• 키-칼럼 순으로 정렬되어 있기 때문에 특정 위치에서 검색을 시작해서 검색 조건이 일치하지않는 값을 만나는 순간 검색을 멈출 수 있다.

 

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

 

(1)인덱스 키 추가

 

1. 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색
2. 저장될 위치가 결정될 시, 레코드의 키값과 대상 레코드의 주소 정보를 B-tree leaf node에 저장
3. 만약, leaf노드가 가득차서 더는 저장할 수 없을 시 leaf node가 분리 되어야한다.( 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. )
4. 이로인해 상대적으로 쓰기 작업에 비용이 많이 드는 것으로 알려져있다.

InnoDB 스토리지 엔진의 키 추가작업

1. 사용자의 쿼리 실행
2. InnoDB 버퍼 풀에 새로운 키 값을 추가해야 할 페이지(leaf node)가 존재시, 키 추가 즉시 키 추가 작업 처리
3. 버퍼 풀에 leaf node가 없다면, 인서트 버퍼에 추가할 키 값과 레코드의 주소를 임시로 기록해 두고 작업완료 ( 사용자의 쿼리는 실행 완료됨 )
4. 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 merge 해야 할 인덱스 키 값이 있는지 확인한 후, 있다면 병합
5. 데이터베이스 서버 자원의 여유가 생기면 MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 merge시킨다.

• 인서트 버퍼는 MySQL 5.1이하에서는 INSERT로 인한 인덱스 키 추가 작업만 버퍼링 및 지연 처리를 할 수 있었다.
• 5.5 이상의 버전에서는 INSERT 뿐만 아니라 DELETE 등에 의한 인덱스 키의 추가 및 삭제 작업까지 버퍼링해서 지연 처리할 수 있게 기능이 확장되어 체인지 버퍼링(Change Buffering)이라는 이름으로 바뀌었다.

 

(2) 인덱스 키 삭제

 

1. 해당 키값이 저장된 leaf node를 찾아서 삭제 마크를 하면 작업 완료.
2. 삭제 마킹된 인덱스 키 공간은 그대로 방치하거나, 재활용할 수 있다.
3. 마킹 작업은 디스크 쓰기가 필요하므로 디스크 I/O가 필요한 작업으로 버퍼링되어 지연 처리가 될 수도 있다.
4. 하지만, 처리가 지연된 인덱스 키 삭제 또한 MySQL 서버가 내부적으로 처리하므로 사용자에게는 특별한 악영향이 없다.

 

(3) 인덱스 키 변경

 

1. 인덱스의 키값은 그 값에 따라 저장될 리프 노드의 위치가 결정된다. 그러므로, 키값이 변경되는 경우 인덱스상의 키값만 변경하는 것은 불가능
2. 변경을 원할 시 기존 키값 삭제 후 새로운 키값을 추가하게 된다.
3. 그 과정은 위에서 진행한 삭제와 추가 작업으로 진행되어진다.

 

(4) 인덱스 키 검색

 

• 위에서 INSERT, UPDATE, DELETE 작업시 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 바로 검색을 위해서이다.

 

1. 트리탐색 : root node 부터 시작해 branch node 를 거쳐 최종 leaf node 까지 이동하면서 비교 작업을 수행
2. 트리탐색은 select 뿐만 아니라 update나 delete를 처리할 경우에도 인덱스가 있으면 빠른 검색이 가능하다.
3. 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.

( 부등호 (“<>”)비교나 값의 뒷부분이 일치하는 경우에는 불가. )

 

1. 인덱스 키값에 변형이 가해진 후 비교되는 경우에는 절대 빠른 검색 기능을 사용할 수 없다.( 이미 변형된 값은 인덱스에 존재하는 값이 아니기때문에. 주의해야함. )
2. InnoDDB 스토리지 엔진의 인덱스는 InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락(갭 락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다. 

( 따라서 update나 delete문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없다면, 불필요하게 많은 레코드를 잠근다. / 테이블의 모든 레코드를 잠그는것도 가능하다 )

 

• InnoDB 스토리지 엔진에서는 그만큼 인덱스의 설계가 중요하며, 많은 부분에 영향을 미친다.

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

 

• 칼럼의크기, 레코드의 건수, 유니크한 인덱스 키값의 개수에 의해 성능이 영향을 받는다.

(1)인덱스 키 값의 크기

 

• 페이지(page),블록(block) : InnoDB 스토리지 엔진에 데이터를 저장하는 가장기본단위, 버퍼 풀에서 데이터를 버퍼링하는 기본 단위
• MySQL의 B-Tree이 갖는 자식 node의 수? 

    :  인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. 

    ( InnoDB의 모든 페이지 크기는 16KB로 고정되어있다. )

 

• 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어들게 되며, 메모리 효율이 떨어지게 된다.

 

(2)B-Tree 깊이

 

• 인덱스의 깊이(Depth)는 직접적으로 제어할 방법이 없다.
• 인덱스 키값의 크기가 커지면 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 개수가 작아지고, B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.
• 가능한 키값의 크기는 작게 만드는것이 좋다

 

(3)선택도(기수성)

 

• 선택도, 기수성은 거의 같은 의미로 사용된다.
• 모든 인덱스 키값 가운데 유니크한 값의 수 
• 인덱스 키값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지며 선택도 떨어짐

( 선택도가 높을수록 검색 대상이 줄어들며, 빠르게 처리된다. )

 

ex) 

(4)읽어야 하는 레코드의 건수

 

• 인덱스를 통해 테이블의 레코드를 읽는 것은 비교적 높은 비용이 드는 작업이다.
• 일반적인 DBMS의 옵티마이저 에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 더 비용이 많이 드는 작업으로 예측한다.
• 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 직접 테이블을 모두 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는것이 효율적
• MySQL의 옵티마이저가 기본적으로 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리하게되지만, 알아둬야한다.

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

 

(1) 인덱스 레인지 스캔

• 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
• 인덱스의 leaf node 에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다.
• 레코드 한 건 한 건 단위로 랜덤 I/O가 한번씩 실행되어, 인덱스를 통한 읽기 작업은 비용이 많이 드는 작업으로 분류되는것이다.
• 데이터 레코드가 20~25%를 넘게되면, 인덱스를 통하여 읽는것보다 테이블의 데이터를 직접 읽는것이 더 효율적이다.

 

(2) 인덱스 풀 스캔

• 인덱스의 처음부터 끝까지 모두 읽는 방식

( 인덱스의 leaf node를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔 )

 

• 인덱스 레인지 스캔보다는 빠르지않지만 테이블 풀 스캔보다는 효율적 

( 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작기때문에 )

 

(3) 루스 인덱스 스캔

• 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것

(  MySQL의 루스 인덱스 스캔 기능은 아직은 제한적이다. )

 

• 오라클과 같은 DBMS의 “인덱스 스킵 스캔” 이라는 기능과 작동방식이 비슷함
• 중간마다 필요치 않은 인덱스 키값은 무시하고 다음으로 넘어가는 형태
• GROUP BY 또는 집합 함수 가운데 MAX() 또는 MN() 함수에 최적화를 하는경우 사용

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

 

• 인덱스를 어느 방향으로 읽을지는 옵티마이저가 실시간으로 만들어 내는 실행 계획에 따라 결정된다.

(1) 인덱스의 정렬

• 일반적인 상용 DBMS에서는 인덱스를 생성하는 시점에 인덱스를 구성하는 각 칼럼의 정렬을 오름차순 또는 내림차순으로 설정가능
• 하지만, MySQL은 위와같은 기능이 불가능하다. 

( 문법적으로 사용은 문제없지만, 실제로는 모든 칼럼이 오름차순 되어지게된다. )

 

ex )

CREATE INDEX ix_teamname_userscore on employees (team_name asc, user_score desc);

 

• 위와같이 선언은 가능하지만, 오름차순된다.
• 인덱스를 구성하는 칼럼 단위로 정렬방식을 혼합해서 생성하는 기능을 아직까지 지원하지않는다.

( 확인해보니 8.0 버전에서도 아직 지원하지 않는것으로 확인되어진다 )

 

• 혼합해서 만들어야 하는 경우 MySQL에서는 칼럼의 값을 역으로 변화해서 구현하는것이 유일한 방법이다.

 

ex )

CREATE TABLE ranking (
 team_name varchar(20),
 user_name varchar(20),
 user_score INT,
 ...
 INDEX ix_teamname_userscore(team_name, user_score)
);

 

• 위 테이블에서 team_name 칼럼은 오름차순, user_score는 내림차순(높은점수)을 하고싶은 경우?

SELECT team_name, user,name
from ranking
order by team_name asc, user_score desc

 

• user_score의 값을 그대로 음수로 만들어서 저장하는 것이다.

( 그리고 order by  조건을 모두 오름차순으로 사용하면된다. )

SELECT team_name, user_name
from ranking order by team_name, user score
ASC나 DESC가 따로 명시되지 않으면 기본값이 "ASC"

   

  인덱스 스캔 방향

 

• 인덱스는 항상 오름차순으로 정렬되어있지만,
  • 인덱스를 최솟값부터 읽으면 : 오름차순
  • 최대값부터 거꾸로 읽으면 : 내림차순 으로 값을 가져올수있다.

 

ex) 

SELECT * FROM employees WHERE first_name >= 'Anneke'
ORDER BY first_name ASC LIMIT 4;

SELECT * FROM employees ORDER BY first_name DESC LIMIT 5;

• 위의 두가지의 예제를 볼때,
  • 첫번째 예제는 first_name 칼럼에 정의된 인덱스를 통해 “Anneke”라는 레코드를 찾은 후, 오름차순으로 해당 인덱스를 읽으면서 4개의 레코드만 가져오면 아무런 비용이 들지않는다.
  • 반대의경우 두번째 예제는 first_name 칼럼에 정의된 인덱스를 역순으로 읽으면서 처음 다섯개의 레코드만 가져오면 되는것이다.

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

결론 

 -  B-Tree란 2진트리의 확장이라고 생각하면된다. ( MySQL은 B-+Tree 사용 )

 

 -  인덱스는 insert, update, delete 작업시 따르는 추가 비용이 크지만, 그 작업을 감수할만큼 검색에 유용하다.

 

 -  인덱스를 제대로 이해하지 못하고 남용하게 된다면, 인덱스를 사용안하는것보다 효율이 낮아질수있으므로, 인덱스에 대한 정확한 이해를 바탕으로 사용해야한다.