[MySQL] B-Tree 알고리즘

Real MySQL 8.0 - 8.3.2에서 인덱스 키 추가 및 삭제 과정에 대한 설명이 쭉 나와 있는데, 시각화된 자료가 없어서 동작 과정이 와닿지 않았다.
그러던 중 B-Tree Visualization이라는 좋은 사이트를 알게 되어서 직접 조작하여 눈으로 확인해보고자 한다.

B-Tree란?

자식 노드의 개수가 2개 이상인 트리

 

• 하나의 노드가 최대 `M`개의 자식을 가질 수 있는 B-Tree를 `M차 B-Tree`라고 부른다.
• 각 노드는 최대 `M - 1`개의 key를 가질 수 있다.
• 노드의 데이터 수가 `N`개라면, 자식 노드의 개수는 `N + 1`개이다.
• 노드의 데이터는 항상 정렬된 상태여야 한다.
  • 노드의 자식 노드들은 노드 데이터를 기준으로 더 작은 값을 왼쪽 서브 트리에, 더 큰 값들은 오른쪽 서브 트리에 위치해야 한다.

B-Tree Visualization 사용법

 

B-Tree 데이터 삽입 과정

1. 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 탐색한다.
2. 저장될 위치가 결정되면 데이터를 추가한다.
3. 리프 노드가 꽉 차면 노드의 분할과 병합을 수행한다.
   • 특정 리프 노드의 데이터 수가 M이 되면, 해당 리프 노드 데이터의 중간값을 기준으로 작은 값을 왼쪽 노드로 큰 값을 오른쪽 노드로 분할하여 트리를 재구성한다. (분할)
   • 분할이 일어나는 노드가 루트 노드가 아닐 경우, 반드시 부모 노드를 가지게 되는데 분할의 과정을 거치면서 재구성된 해당 서브 트리의 루트 노드는 자신의 부모 노드와 합쳐지게 된다. (병합)

B-Tree 인덱스

인덱스 키 추가

1. 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색한다.
2. 저장될 위치가 결정되면,
   1. MyISAM의 경우, 실제 데이터 레코드의 위치 정보(주소)를 저장한다.
   2. InnoDB의 경우, 데이터 파일의 PK 값을 저장한다.
3. 리프 노드가 꽉 차서 더는 저장할 수 없을 때, 분할 및 병합의 과정이 일어난다.

이렇게 삽입 후 분할 및 병합 과정이 수행되기 때문에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다.

인덱스 키 삭제

• 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크를 한다.
• 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다.

왜 인덱스를 바로 삭제하지 않고 삭제 마킹을 하는 걸까?
1. 데이터를 삭제하면 B-Tree는 정렬된 상태를 유지해야 하기 때문에 재정렬 작업이 발생할 수도 있다.
2. 클러스터링 인덱스의 경우, 실제 데이터와 연결되어 있기 때문에 삭제 시 데이터에 영향을 주기 때문인 것 같다.

인덱스 키 변경

B-Tree의 키 변경 작업은

1. 먼저 키 값을 삭제한 후
2. 다시 새로운 키 값을 추가하는 형태로 처리된다.

정리

• 장점) B-Tree 인덱스는 키의 순서대로 정렬되어 있기 때문에 범위 쿼리나 정렬된 결과를 얻을 때 유용하다.
• 단점) 삽입 시 분할 및 병합 과정이 수행되기 때문에 상대적으로 쓰기 작업에 비용이 많이 든다.

Ref

Real MySQL 8.0 책

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

https://mangkyu.tistory.com/286

https://www.programiz.com/dsa/insertion-into-a-b-tree