(아낌없이 주는 B-나무)

0. 배경

바야흐로 지난 달.

회사에서 데이터베이스 관련해서 사수님과 이야기를 나눈 적이 있었고
사수님께서 B-Tree 관련해서 영상 하나를 추천해주셨다.

총 3부에 걸쳐 1시간 반에 가까운 길이의 영상이었는데,
정말 세세하게 B-Tree의 데이터 삽입, 삭제가 어떻게 일어나는지 설명해주었다.

(일전에 T사의 면접에서 B-Tree에 대해 질문을 받은 적이 있었는데,
그전에 이 영상을 보았다면 그때 그렇게 당당하게 모른다고 하진 않았겠지...)

그래서 오늘은 그 영상을 보고 기록을 남기기 위해 글을 작성하려 한다.

(참고로, 해당 영상은 여기에서 볼 수 있다)

 

 

1. B-Tree란?

B-Tree는 정렬된 형태를 유지하는 self-balancing 트리로써
O(log n) 복잡도로 조회, 삽입, 삭제 연산을 지원하는 트리 자료구조다.

 

self-balancing 트리?

self-balancing이란, 트리 내 삽입 및 삭제 등의 연산이 이어짐에 따라
트리의 균형이 한쪽으로 쏠리지 않도록 하는 것을 의미한다.

예를 들어, 위와 같이 {1, 2, 3}으로 이뤄진 트리가 있다고 가정했을 때,
좌측이 아닌 우측의 형태가 밸런스 잡힌 상태인 것이다.

그러면 왜 밸런스 잡힌 상태가 필요한 것일까?
좌측의 형태에서 1과 3을 조회하기 위한 depth는 각각 1, 3으로 서로 다르지만
우측의 형태에선 1과 3을 조회하기 위한 depth가 모두 2로 동일하다.

이처럼 leaf 노드의 depth를 최소화하여
worst case를 O(n)이 아닌 O(log n)으로 유지하기 위해 필요하다.

 

 

(self-balancing tree)

 

 

2. B-Tree의 특징

B-Tree는 BST(Binary Search Tree)의 일반화된 버전으로서,
3개 이상의 자녀 노드를 허용한다는 점이 가장 중요한 특징이다.

그리고 위 그림과 같이 3개 자녀 노드를 가진다고 가정했을 때,
부모 노드 안에 2개의 키가 오름차순으로 정렬되어 있다.

 

B-Tree의 제약 조건

자녀 노드의 수 n에 따라 B-Tree가 가지는 제약 조건이 결정된다.

• 부모 노드의 최대 키 수: n - 1
• 자녀 노드의 최소 수: 올림(n / 2)
  • root & leaf 노드 제외
• 각 노드의 최소 키 수: 올림(n / 2) - 1
  • root 노드 제외
• internal 노드의 키 수: 자식 노드의 수 - 1
  • internal 노드는 root & leaf 노드가 아닌 모든 노드

 

B-Tree는 왜 DB 인덱스에 사용될까?

백엔드 엔지니어가 B-Tree를 학습하게 되는 가장 큰 이유는 DB 인덱스에 사용되기 때문일 것이다.
그렇다면 왜 BST가 아닌, B-Tree를 인덱스에 사용하는지 따져보자.

먼저, 몇 가지 가정이 필요하다.

• 하드 디스크에 대한 접근이 메모리에 대한 접근에 비해 압도적으로 큰 비용을 가진다.
• DB는 하드 디스크에 데이터를 저장하기 때문에 DB에 대한 접근이 적을수록 비용이 낮아진다.
• block 단위로 DB에 접근하기 때문에, 1개의 block 안에 찾고자 하는 데이터가 모여 있을수록 비용이 낮아진다.

 

위 그림은 {1, 2, 3, 4, 5}를 각각 B-Tree와 AVL Tree(BST)로 구성한 예다.

이때 1개 노드당 block이 할당되며 block 당 DB에 접근한다고 가정했을 때,
5를 탐색하기 위해 각각 B-Tree는 2번, AVL Tree는 3번 DB에 접근해야 한다.

B-Tree는 AVL Tree에 비해,
노드당 포함할 수 있는 키의 수가 많을 뿐더러 자식 노드의 수도 더 많다.

따라서 AVL Tree는 B-Tree보다 항상 같거나 높은 worst case 값을 가지기 때문에
B-Tree가 DB 인덱스에 더 적합하다고 할 수 있다.

 

101차 B-Tree

그렇다면 도대체 B-Tree는 임의의 depth 값에 얼마나 많은 데이터를 가질 수 있는 것일까?
depth가 3인 101차 B-Tree를 통해 이를 가늠해보자.

위와 같이 트리의 모든 노드가 완벽하게 들어차 있는 best case에서,

• depth가 1인 root 노드에서 100개
• depth가 2인 internal 노드에서 100 x 101개
• depth가 3인 internal 노드에서 100 x 101 x 101개

총합 1,030,300개의 노드를 저장할 수 있다.

예를 들어 100만명의 유저를 보유하고 있는 서비스의 사용자 정보를 인덱싱한다고 가정할 때,
그 모든 데이터 사이에서 3번의 접근만으로 조회가 가능하다는 뜻이다.

 

그러면 이제는 반대로 트리의 모든 노드가 최소한으로 들어차 있는 worst case에선,

(참고로, 101차 B-Tree에서
노드당 최소 키 수는 50개, 최소 자식 노드 수는 51개다)

• depth가 1인 root 노드에서 50개
• depth가 2인 internal 노드에서 50 x 51개
• depth가 3인 internal 노드에서 50 x 51 x 51개

총합 132,650개의 노드를 저장할 수 있다.

best case에 비해서 적어보일지라도
같은 depth의 AVL Tree가 최대 7개 노드를 저장할 수 있다는 점을 감안하면 엄청난 차이를 보인다.

 

B+Tree?

데이터베이스 인덱스는 실제로 B-Tree가 아닌, B+Tree 자료구조로 이뤄져 있다는 말을 들어봤을 것이다.

B+Tree는 기본적으로 B-Tree와 동일하나,
모든 노드에는 다음 노드에 대한 key만 가진다는 점이 다르다.

그리고 추가로 leaf 노드와 연결되어 있는 추가적인 level이 존재하여,
그곳에 실제 데이터 value를 저장한다.

따라서 위 그림과 같이 키 중복이 발생하기도 한다.
(출처)

대신 그렇기 때문에 모든 노드가 value 저장 공간만큼 더 많은 key를 저장할 수 있다는 장점을 가진다.
게다가 그림과 같이 마지막 level이 linked list로 연결되어 있기 때문에 범위 검색에 최적화되어 있다.

 

 

3. B-Tree의 삽입, 삭제 연산

이제는 B-Tree 자료구조가 정확히 어떻게 삽입, 삭제 연산 알고리즘을 이용하는지 알아볼 차례다.
솔직히 이 글을 읽기보다는 이 영상을 통해 학습하는 것을 추천한다.

데이터 삽입

가정

• 데이터 추가는 leaf 노드에서 이뤄진다.
• 노드 수가 기준(n-1)을 넘으면 가운데 노드를 부모 노드로 승진하고, 좌우를 갈라 자식 노드로 삼는다.

예시

3차 B-Tree를 기준으로 예를 들어보자.

 

0) 초기화

여기 1, 15의 키를 가지는 root 노트로부터 출발한다.

 

1) 2 추가

위 그림과 같이 2를 오름차순대로 leaf 노드에 먼저 넣는다.

그러면 노드가 가지는 최대 키 수 2를 넘기 때문에 가운데 노드인 2를 승진시키고,
나머지 1과 15는 각각 서로 다른 자식 노드로 찢어지는 형태로 완성된다.

 

2) 5 추가

그러면 5는 2보다 크기 때문에 우측 leaf 노드에 삽입되어 {5, 15}의 키를 이루게 된다.

 

3) 30 추가

그러면 30는 2보다 크기 때문에 우측 leaf 노드에 삽입되어 {5, 15, 30}의 키를 이루게 된다.

그리고 최대 키 수 2를 넘기 때문에 가운데 노드인 15를 승진시키고,
나머지 5와 30은 각각 서로 다른 자식 노드로 찢어지는 형태로 완성된다.

여기서 특이한 점은, 2를 추가했을 때와 다르게 15는 기존의 부모 노드에 편입되기 때문에
총 3개의 자식 노드를 이루게 된다는 점이다.

 

4) 90 추가

그러면 90은 2, 15보다 모두 크기 때문에 가장 우측 leaf 노드에 추가된다.
해당 노드는 {30, 90}으로 정렬되고, 최대 크기가 넘지 않기 때문에 이대로 유지된다.

 

5) 20 추가

그러면 20은 2, 15보다 모두 크기 때문에 가장 우측 leaf 노드에 추가된다.
해당 노드는 {20, 30, 90}으로 정렬되고, 최대 키 수를 넘기 때문에 가운데 30이 부모 노드로 승진한다.

그런데 부모 노드도 {2, 15, 30}으로 최대 크기를 넘는다.
따라서 가운데 15가 새로운 부모 노드로 승진하며 2와 15는 서로 다른 자식 노드로 찢어진다.

마지막으로, 맨처음 {20, 30, 90}에서 30이 승진할 때도 20과 90은 서로 찢어져야 하므로
가장 우측의 상태와 같이 완성된다.

 

결과

결론적으로 depth가 2인 트리로 시작해서 depth가 1 추가되어 총 3의 depth를 가지게 되었다.
그 과정에서 지켜보면 B-Tree는 모든 leaf 노드가 동일한 depth를 가진다는 것을 알 수 있다.
그래서 B-Tree를 self-balancing 트리라고 할 수 있는 것이기도 하다.

 

(이제는 삭제를 알아볼 시간)

 

데이터 삭제

가정

• 삭제도 leaf 노드에서 발생한다.
  • internal 노드가 삭제 타겟이 되더라도, leaf 노드와 스왑 이후 처리된다.

• 삭제 후 노드의 최소 키 수보다 적을 경우 재조정한다.
  • 최소 키 수는 올림(n / 2) - 1
  • 재조정은 다음 단계를 따른다.
    • 키 수가 넉넉한 형제 노드로부터 지원을 받아본다.
    • 형제 노드의 키 수가 부족한 경우, 부모 노드로부터 무조건 지원을 받아 형제와 합친다.
    • 부모 노드의 키 수가 부족해진 경우, 거기서부터 재조정 단계를 반복한다.

예시

이번에도 3차 B-Tree를 가지고 예시를 들어보자.
참고로 3차 B-Tree의 최소 키 수는 1이다.

 

0) 초기화

 

1) 6 삭제

6은 15보다 작기 때문에 좌측 자식 노드로 이동한다.
6은 3보다 크지만 7보다 작기 때문에 중간 leaf 노드로 이동하여 삭제한다.
(이 단계는 이하 생략하도록 하자)

삭제 이후 최소 키 수 1을 만족하므로 유지된다.

 

2) 5 삭제

5를 찾아 삭제하면 해당 노드의 키 수가 0으로 1보다 작아 부족해진다.
결국 재조정 단계를 거쳐야 하는데, 먼저 동생 {1, 2} 노드로부터 2를 빌려본다.

이 때, 2를 그대로 가져오는 경우 부모 노드 {3, 7}에 따라 2가 3보다 커야 하는 아이러니한 상황이 발생하므로
그림과 같이 2는 부모 노드로 올라가고, 3은 자식 노드로 내려오는 단계를 거쳐서 완성된다.

 

3) 3 삭제

3을 찾아 삭제하면 해당 노드의 키 수가 0으로 1보다 작아 부족해진다.
결국 재조정 단계를 거쳐야 하는데, 동생도 먹고살기 팍팍하니까 형으로부터 8을 빌리자.

다만, 전과 같이 8을 부모 노드로 올리고, 7을 대신 받아 채워넣게 된다.

 

4) 7 삭제

7을 찾아 삭제하면 해당 노드의 키 수가 0으로 1보다 작아 부족해진다.
재조정 단계를 거쳐야 하는데, 동생과 형 모두 키 수가 적어서 부모로부터 빌려야 한다.

2을 빌린다고 가정하면, 이제 형제와 합쳐야 하는데 동생과 합치게 되는 경우
결국 {1, 2}의 노드를 만들고 자식 노드의 수는 2로 줄어들게 된다.

 

5) 2 삭제

2를 찾아 삭제하더라도 최소 키 수를 만족하므로 그대로 유지된다.

 

6) 1 삭제

1을 찾아 삭제하면 최소 키 수를 만족하지 못하기 때문에 재조정 단계를 거쳐야 하는데,
형제 노드의 키 수도 부족하므로 부모 노드로부터 8을 빌려와 채우게 된다.

그리고 부모 노드로부터 빌린 경우에는 형제 노드와 합쳐야 하므로
{8, 9}의 leaf 노드를 형성하게 된다.

그러면 결국 해당 부모 노드도 키 수를 만족하지 못해서 재조정 단계를 반복한다.
형제 노드의 키 수가 부족하므로 root 노드로부터 15를 빌려와 채우게 된다.

그리고 부모 노드로부터 지원받은 경우엔 형제와 합쳐야 하므로 {15, 30}의 새로운 root 노드를 형성한다.
그리고 {30}에 붙어 있던 2개 자식 노드도 가져와 알맞게 연결하면 완성된다.

 

(그래서?)

 

4. 결론

B-Tree에 대해서 명확하게 알 수 있었고, 아마도 면접 자리에서 이와 관련한 질문을 받는다면
내 머릿속 캐시의 TTL이 다하지 않는 이상 문제없이 답할 수 있지 않을까 한다.

요약하자면,

B-Tree는 3개 이상의 자식 노드를 가질 수 있는 BST다.
삽입, 삭제 연산을 통해서도 leaf 노드의 depth를 일정하게 맞춰주기 때문에 worst case가 (log n)으로 유지된다.