이진 트리에서 자녀 노드를 더 가지고 싶다면?
모든 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 가지고, 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 가지는 트리이며 자녀 노드는 최대 2개까지 가질 수 있는 트리이다.
이때 자녀 노드를 2개 이상 가지고 싶으면 어떻게 해야할까?
이진 트리의 구성 방식을 살펴보면 루트 노드의 왼쪽 노드는 ?<50 인 값이, 오른쪽 노드는 ?<50인 값이 저장된다. 여기서 자식 노드를 더 늘려보자.
이렇게 표현할 수 있을 것이다. 왼쪽 노드는 ?<k1, 가운데 노드는 k1<?<k2, 오른쪽 노드는 ?>k2가 될 것이다.
이때 3개의 자녀 노드를 저장하기 위해 k1과 k2 두 개의 값이 필요한 것을 볼 수 있다.
따라서 루트 노드에는 하나의 값이 아닌 k1, k2 두개의 키 값이 필요하다. 루트 노드에 한 개 이상의 값을 저장함으로써 자녀 노드의 수를 늘릴 수 있는 것이다. 이런 형태로 동작하는 트리를 B 트리라고 한다. 이 개념을 기억하고 B트리의 특징을 살펴보자.
B 트리
우선 B트리의 파라미터를 살펴보자.
- M: 각 노드의 최대 자녀 수. 최대 M개의 자녀를 가질 수 있는 B트리를 M차 B트리라고 한다.
- M-1: 각 노드의 최대 key 수.
- ⌈M/2⌉: 각 노드의 최소 자녀 수. (루트, 리프 노드 제외)
- ⌈M/2⌉-1: 각 노드의 최소 key수 (루트 노드 제외)
이 파라미터들을 기억하고 아래 특징을 살펴보자.
- internal노드의 key수가 x개라면 자녀 노드의 수는 항상 x+1개 이다.
- 노드가 최소 하나의 key를 가지기 때문에 몇 차 b tree인지 상관 없이 internal노드는 최소 두개의 자식 노드를 가진다.
- M이 정해지면 root 노드를 제외한 internal노드는 최소 ⌈M/2⌉개의 자녀노드를 가질 수 있게 된다.
- key는 오름차순으로 정렬되어 저장되어야 한다.
- 모든 리프 노드는 같은 레벨에 있다. (삽입 과정을 알아보면서 이해해보자)
- B트리는 balanced tree이다.
위 파라미터를 잘 이해했다면 어렵지 않게 이해할 수 있을 것이다.
B 트리의 데이터 삽입
삽입을 알아보기에 앞서 B 트리에서 데이터 삽입이 일어나면 아래의 두 가지 방식으로 동작한다는 것을 알아야한다.
- 데이터 추가는 항상 리프 노드에서 일어난다.
- 노드가 넘치면 가운데 key를 기준으로 좌우 키는 분할하고 가운데 key는 승진한다.
자 이제 3차 B 트리에 데이터 삽입을 하는 경우를 알아보도록 하자. 3차 B 트리이기 때문에 자녀 노드의 수는 최대 3개, key 는 최대 2개까지 가질 수 있다.
1. 1 추가
1을 추가한 후 모습이다. key는 최대 2개까지 이므로 노드에 키를 저장하는 공간이 두 개임을 확인할 수 있다.
2. 15추가
삽입은 항상 리프 노드에서 일어난다고 했다. 위 노드는 루트 노드인 동시에 리프 노드이므로 빈 공간에 추가한다.
3. 2 추가
2를 추가해보자. key는 오름차순으로 정렬해줘야하기 때문에 가운데에 우선 삽입하였다. 최대 키 수는 2개 까지인데 노드가 넘쳤다. 앞서 보았던 규칙에 따르기 위해 가운데 노드를 기준으로 분할을하고 가운데 key는 승진을 시켜보자.
그러면 이런 모습이 될 것이다. key옆에 작은 막대기 처럼 보이는 공간은 자녀 노드를 가리키기위한 포인터 역할을 한다고 보면 된다.
4. 3 추가
5는 루트 노드인 2보다 큰 값이므로 오른쪽 자식 노드에 저장되어야한다. 그런데 key가 정렬 되어야하므로 위 처럼 5, 15 순으로 저장이 될 것이다.
5. 30 추가
30은 루트 노드인 2보다 크므로 오른쪽 노드에 정렬된 형태로 저장된다. 노드가 넘쳤으므로 가운데 노드인 15를 승진시키고 5와 30은 자녀 노드로 양쪽으로 분할하면 아래와 같은 형태가 완성된다.
6. 90 추가
90은 2와 15 모두와 크므로 30이 저장된 노드의 빈공간에 추가된다.
7. 20 추가
여기서 20을 추가하면 어떻게 될까? 20은 2와 15보다 커서 오른쪽 자녀인 30과 90이 저장된 노드에 저장되어야한다. 
이렇게 되면 노드가 넘치게 되니 규칙에 의해 분할과 승진을 시켜줘야한다. 우선 90을 따로 분할해주고 30을 루트노드로 승진 시킨다.
승진시키고 봤더니 루트노드가 넘치게 되었다. 그래서 이 루트 노드에 대해서도 분할과 승진 과정을 수행한다.
새로운 노드를 만들어 30을 분할하고, 15를 루트 노드로 만들기 위해 새로운 노드에 15를 저장하여 자식 노드를 가리키는 포인터를 연결해준다. 이제는 15가 루트노드가 되었다.
B 트리의 데이터 삭제
B 트리에서 데이터 삭제는 아래 두 규칙에 따라 수행된다.
- 삭제는 항상 리프 노드에서 발생한다.
- 삭제 후 최소 key 수보다 적어진다면 재조정한다.
재조정하는 방식은 다음과 같다.
- key수가 여유있는 형제의 지원을 받는다.
- 1번이 불가하다면 부모의 지원을 받고 형제와 합친다. (합칠때는 왼쪽 방향으로 합친다)
- 2번 후 부모에 문제가 생겼다면 거기서 다시 재조정한다.
이것을 기억하고 아래와 같은 3차 B 트리에서 삭제 과정을 예제로 알아보자. 이 트리에서의 최소 key수는 1 개이다.
1. 6 삭제
우선 삭제할 노드를 조회해야한다. 6은 15보다 작으니 왼쪽 자식으로 이동할 것이다. 6은 3보다 크고 7보다 작으니 가운데의 서브트리로 이동한다. 6은 리프 노드이기 때문에 별다른 과정없이 바로 삭제된다. 삭제 후에도 최소 key수 보다 적어지지 않았기 때문에 재조정도 하지 않는다.
2. 5 삭제
자 이상태에서 5를 삭제해보자. 아까와 같은 과정을 거쳐 5가 있는 노드를 찾은 후 5를 제거한다.
5를 삭제해주니 해당 노드의 최소 key수 보다 적어졌다. 현재 상황에서는 왼쪽, 오른쪽 노드 모두 key수가 여유가 있다. 그래서 왼쪽에 있는 노드에서 지원을 먼저 받을 것이다.
여기서 2의 값을 바로 가운데로 이전해버리면 안된다. 그러면 부모 노드의 키 값인 3보다 큰 값이 아니어서 규칙을 깨뜨리게 된다. 정렬 순서를 유지하기 위해 부모의 3을 가운데 노드로 보내고 2를 부모 노드로 보낸다.
최종적으로 이런 모습이 된다.
3. 3 삭제
3을 삭제하니 아까와 같이 최소 key수보다 적어져 재조정이 필요해졌다. 이번에는 왼쪽 노드에는 도움을 받을 수 없으니 오른쪽 노드에 요청하게 된다. 정렬순서가 유지되어야하니 부모 노드의 7을 가운데 노드로 내리고 8을 부모노드로 보낸다. 그리고 정렬에 맞게 9를 왼쪽으로 옮겨주면 다음과 같은 모습이 될 것이다. 
여기까지 살펴보면 형제로부터의 지원은 다음과 같은 절차로 이루어진다는 것을 알 수 있다.
- 왼쪽 형제에 여유가 있으면
- 왼쪽 형제의 가장 큰 key를 부모노드와 나 사이에 둔다.
- 원래 있던 부모의 key는 나의 가장 왼쪽에 둔다.
- 왼쪽 형제가 아니라 오른쪽 형제에 여유가 있으면
- 오른쪽 형제의 가장 작은 key를 부모노드와 나와 형 사이에 둔다.
- 원래있던 부모노드의 key는 나의 오른쪽에 둔다.
4. 7 삭제
이번엔 7을 삭제해보자. 7을 삭제하고 보니 재조정이 필요한데 이번에는 형제 노드에게 지원을 받을 수 없게 되었다.
이번에는 부모의 지원을 받고 형제와 합쳐야한다.
우선 부모의 왼쪽 key를 왼쪽 노드(동생)으로 보낸다. 원래는 가운데있는 나의 노드의 값도 합쳐야하지만 이 순서에는 합칠 필요가 없기 때문에 빈 노드는 제거한다. 부모 노드에 남은 8도 정렬을 해줘야하기 때문에 왼쪽으로 옮기고 포인터도 왼쪽으로 보내면 아래와 같은 모습이 된다.
이렇게 형제와 합쳐지면서 노드 하나가 사라지게 된다.
5. 2삭제 후 1삭제
아까 트리 모습에서 2를 삭제하면 이런 모습이 된다. 2 삭제 과정은 재조정이 필요없기에 생략한다.
이번엔 1을 삭제해보자. 1을 삭제하려고 봤더니, 형제한테 지원을 받을 수 가 없는 상황이 되었다. 우선 부모에게 지원을 받기 위해 나의 노드(1이 있던 노드)에 부모의 값을 넣는다.
오른쪽 형제와 합치기 위해 9를 나의 노드에 합치면 아래와 같은 모습이 된다.
합치고 나니 부모 노드에 문제가 생겼다. 이때는 부모노드에서부터 다시 재조정을 해야한다. 부모 노드에 해당하는 노드의 형제에게 도움을 받을 수 있는지 확인한다. 30이 있는 형제는 최소 key수만큼만 key를 가지기 때문에 도움을 받을 수 없다.
부모 노드인 15를 아래 노드로 보낸다.
형제 노드인 30도 왼쪽으로 합쳐준다.
포인터도 옮겨주고 난 후 빈 형제 노드는 삭제한다.
자 이번엔 부모 노드에 문제가 생겼다. 이 문제를 해결하는 방법은 간단하다. 부모 노드를 삭제해주면 된다.
그럼 최종적으로 이러한 모습이 완성된다.
여기까지 살펴보면 재조정 3번 과정(부모 노드에게 지원받은 후 부모 노드를 재조정)은 아래와 같은 절차로 이루어지는 것을 알 수 있다.
- 부모노드가 root가 아니라면
- 그 위치에서 다시 1번부터 재조정을 시작한다.
- 부모가 root이고 비어있다면
- 부모노드를 삭제한다.
- 직전에 합쳐진 노드가 root노드가 된다.
여기 까지 리프노드에서의 삭제 과정을 알아봤다. 그럼 리프노드가 아닌 internal 노드에서 삭제가 일어나면 어떻게 될까?
internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다. 삭제 후 문제가 생겼다면 아까와 같이 재조정을 해주면 된다.
여기서 15를 삭제해보자. 15노드는 리프 노드가 아니므로 리프노드 중 하나와 위치를 바꿔야한다. 여기서 어떤 리프노드와 바꿔줘야할까?
삭제할 데이터의 선임자(predesessor)나 후임자(successor)와 자리를 바꿔주면 된다. 선임자는 나보다 작은 데이터들 중 가장 큰 데이터를 의미하며 후임자는 나보다 큰 데이터 중 가장 작은 데이터를 의미한다. 이렇게 선임자 또는 후임자를 삭제하면 B트리의 정렬이 깨지지 않게 유지할 수 있다.
예를 들어 위 트리에서는 15의 선임자는 9이다. 9가 15랑 자리를 바꾸면 9의 왼쪽 서브 트리에는 9보다 작은 값들이, 오른쪽 서브트리에는 9보다 큰 값들이 있게 될 것이다.
B트리가 왜 DB의 인덱스로 사용될까
그렇다면 데이터베이스 인덱스에서는 왜 비슷한 이진트리를 사용하지 않고 B-tree 계열(B-tree, B+tree)을 사용할까. 그 이유는 디스크 I/O 특성과 실제 저장소의 동작 방식 때문이다.
디스크 I/O의 특성은 다음과 같다.
- 디스크에서 데이터를 읽을 때는 한 번에 블록 단위(보통 4KB~16KB)로 읽는다.
- 메모리에서 1바이트 읽는 것과 1KB 읽는 것의 시간 차이는 거의 없지만, 디스크 I/O는 한 번 발생하는 것 자체가 큰 비용이 든다.
- 따라서 디스크 I/O 횟수를 최소화하는 것이 성능의 핵심이다.
이진 트리는 다음과 같은 문제점이 있다.
- 각 노드가 최대 2개의 자식만 가지므로 트리의 높이가 높아진다.
- 높이가 높다 = 디스크 I/O 횟수가 많다는 의미
- 100만 개 데이터: 이진 트리는 약 20번의 디스크 I/O 필요
즉 각 노드가 가질 수 있는 자식 수의 한계 때문에 I/O 속도가 느려진다. 하지만 B트리 계열은 한 노드에 여러개의 키를 저장할 수 있어 다음과 같은 이점이 있다.
- 한 노드에 수십~수백 개의 키를 저장할 수 있어 트리의 높이가 낮다.
- 한 블록을 읽을 때 여러 키를 함께 읽으므로 디스크 I/O가 효율적이다.
- 100만 개 데이터: B-tree는 3~4번의 디스크 I/O면 충분
그 중 B+ 트리는 아래와 같은 장점이 있어 요즘은 B트리 보다 B+트리가 인덱스에 대부분 사용된다.
- 리프 노드들이 연결 리스트로 연결되어 범위 검색(range scan)이 매우 효율적이다.
- 모든 데이터가 리프 노드에만 있어 순차 접근 성능이 좋다.
B 트리는 자가 균형 트리(self-balancing tree) 자료구조로, 디스크 기반 데이터베이스와 파일 시스템에서 널리 사용된다. 주요 특징은 1. 하나의 노드가 여러 개의 키와 자식을 가질 수 있다 (차수 m인 B 트리는 최대 m개의 자식) 2. 모든 리프 노드가 같은 레벨에 있어 균형이 보장된다. 3. 각 노드는 최소 ⌈m/2⌉개, 최대 m개의 자식을 가진다 (루트 제외) 4. 키들은 정렬된 상태로 유지된다. B 트리를 사용하는 이유는 디스크 I/O를 최소화하기 위해서이다. 이진 트리는 높이가 높아 디스크 접근 횟수가 많지만, B 트리는 한 노드에 여러 키를 저장해 높이를 낮춰 디스크 접근을 줄인다.
- B 트리의 시간 복잡도는:검색, 삽입, 삭제 모두 O(log n). 여기서 로그의 밑은 차수 m에 비례
- B 트리에서 삽입/삭제 시 어떻게 균형을 유지하는지?
- 삽입: 노드가 가득 차면 중간 키를 부모로 올리고 노드를 분할(split)
- 삭제: 노드의 키가 최소 개수보다 적어지면 형제 노드에서 빌리거나 병합(merge)- B 트리의 차수 m을 어떻게 결정하나?: 디스크 블록 크기와 키/포인터 크기를 고려, 한 노드가 하나의 디스크 블록에 들어가도록 설정
