B-트리(B-Tree)
B-트리는 이진 탐색 트리(BST)의 일반화한 트리 형태를 의미하며 다른 자가 균형(Self-Balancing) 이진 탐색 트리와 같이 스스로 균형을 유지하는 트리이다.
이러한 Self-Balancing을 통해서 데이터를 조회하는데 더 좋은 성능을 가질 수 있게 된다.
하지만 B-트리가 Self-Balancing을 한다고 다른 Self-Balancing BST와 같은 것은 아닌데 B-트리의 의미처럼 이진 탐색 트리를 일반화한 것이기 때문이다.
이진 탐색 트리는 자식 노드를 최대 2개까지만 가질 수 있다는 특징이 있다. 하지만 그 보다 더 많은 자식 노드를 가지고 싶다면 어떻게 해야 될까?
많은 자식 노드를 가지기 위해서는 자녀 노드가 가질 수 있는 값의 범위를 지정해줘야 한다.
위의 그림과 같이 부모 노드에 값을 저장하면 해당 값의 범위만큼 자식 노드를 가질 수 있게 된다.
간단하게 예제를 그려보면 만약 부모 노드에 50과 80을 저장했다고 가정해 보자.
그러면 왼쪽 자식 노드에는 50보다 작은 값, 중간에 위치한 자식 노드에는 50과 80 사이의 값, 오른쪽 자식 노드에는 80보다 큰 값들이 위치하게 된다.
이를 통해서 알 수 있는 정보는 부모 노드가 하나 이상의 값을 가지고 있고, 값들은 항상 정렬된다는 것이다.
정렬을 하는 이유는 정렬을 해야지 자녀 노드들의 값의 범위를 결정할 수 있기 때문이다.
이렇게 이진트리가 최대 2개의 자식 노드를 가질 수 있다는 규칙을 깨고 더 많은 자식 노드를 가질 수 있게 일반화한 것을 B-트리라고 한다.
이렇게 B-트리를 알아보면 자식 노드를 2개 이상 유동적으로 늘릴 수 있기 때문에 가장 중요해지는 것이 바로 최대 몇 개의 자녀 노드를 가질 것인가이다.
B-트리에서는 해당 정보가 가장 중요한 파라미터가 되는데 최대 자식 노드의 수가 정해지면 다른 정보들이 자동으로 정해지기 때문이다.
최대 자녀 노드의 수가 M이라고 한다면 B-트리를 M차 B-트리라 부른다. 그러면 해당 M 값을 가지고 어떤 정보들을 얻을 수 있을까
- M: 각 노드의 최대 자녀 노드의 수
- M - 1: 각 노드의 최대 키 수
- ceil(M / 2): 각 노드의 최소 자녀 노드의 수로 반올림을 해서 정한다.(루트 노드나 리프 노드는 제외)
- ceil(M / 2 - 1): 각 노드의 최소 키수(루트 노드는 제외)
어떤 파라미터를 기준 파라미터로 잡을지는 다를 수 있다.
B-트리의 데이터 삽입
B-트리에서 데이터 삽입은 3가지만 기억하자.
- 데이터 추가는 항상 리프 노드부터 시작한다.
- 노드가 가질 수 있는 키 값이 넘어가면 가운데 키를 기준으로 좌우 키들은 분할한다.
- 가운데 키를 부모 노드의 키로 승진한다.
위의 3가지 포인트를 기억하며 3차 B-트리를 예시로 어떻게 동작하는지 알아보자.
먼저 3차 B-트리를 기준으로 앞서 설명했던 파라미터들을 구해보자.
먼저 각 노드가 가질 수 있는 최대 자식 노드의 개수은 M은 3이 된다. 이를 통해서 구할 수 있는 정보는 아래와 같다.
- M - 1: 각 노드가 가질 수 있는 최대 키의 개수로 현재 M은 3이기 때문에 최대 2개의 키를 가질 수 있다.
- ceil(M / 2): 각 노드가 가질 수 있는 최소 자식 노드의 수로 현재 M은 3이기 때문에 각 노드는 최소 2개의 자식 노드를 가지고 있어야 한다.
- ceil(M / 2) - 1: 각 노드가 가질 수 있는 최소 키의 개수로 현재 M은 3이기 때문에 각 노드는 최소 1개 이상의 키를 가지고 있어야 한다.
이제 파라미터를 구했으니 데이터를 하나씩 삽입해 보며 동작 과정을 살펴보자.
참고로 키와 값은 동일한 것이 아니다. 실제로는 값이 따로 존재하지만 편의상 값과 키가 동일하다고 가정하고 진행해 봤다.
먼저 1이라는 데이터를 삽입하고 난 뒤에 15 데이터를 넣으면 위와 같이 키와 포인터가 노드에 저장된다.
그다음 2라는 데이터를 삽입하게 되면 아래의 그림과 같이 동작하게 된다.
노드가 가질 수 있는 최대 키의 값은 2이기 때문에 2라는 새로운 값이 들어왔을 때 키의 개수가 3이 돼버린다.
따라서 1과 15를 각각 분리하고 중앙값이었던 2를 새로운 부모 노드로 승진시킨다.
2라는 키 값을 저장하고 있는 노드가 최상위 루트 노드가 되었기 때문에 다음 데이터 삽입 때부터는 루트부터 비교하게 된다.
순서대로 15와 30을 저장한다고 했을 때 먼저 15는 루트인 2와 비교를 하게 되고 15가 크기 때문에 오른쪽 자식 노드의 키로 저장된다.
다음으로 30을 삽입했을 때 15와 마찬가지로 2보다 크기 때문에 오른쪽 자식 노드의 키로 저장된다.
여기까지 봤을 때 오른쪽 자식 노드가 가지고 있는 키의 개수가 3이 돼버리면서 다시 5와 30으로 분할시키고 15를 부모의 키로 승진시킨다.
다음으로 20과 90을 순차적으로 삽입해 보면 이때도 키의 개수가 3이기 때문에 20과 90으로 분할하고 30을 부모의 키로 승진시킨다.
승진을 시키고 난 뒤에 부모 노드를 보면 키의 개수가 3개가 되면서 다시 분할하는 과정이 필요해졌다.
따라서 가운데 키 값인 15를 기준으로 2와 30을 분할하고 15를 부모의 키로 승진시킨다.
여기까지 B-트리의 데이터 삽입을 살펴보면서 알 수 있는 점들을 정리해 보자.
- 모든 리프 노드들이 모두 같은 레벨에 있다는 것을 알 수 있다. 따라서 이를 통해 알 수 있는 사실은 B-트리가 균형을 유지하고 있다는 점이다.
- internal 노드(내부 노드)의 키 수가 x개라면 자녀 노드의 수는 언제나 x + 1개라는 것을 알 수 있다.
- 노드가 최소 하나의 키는 가지기 때문에 몇 차 B-트리 인지와 상관없이 internal 노드는 최소 두 개의 자녀를 가진다.
- M이 정해지면 루트 노드를 제외하고 internal 노드는 최소 M / 2개의 자녀 노드를 가질 수 있다.
B-트리의 데이터 삭제
B-트리에서 데이터 삭제 작업 또한 항상 리프 노드부터 시작한다.
B-트리에서 데이터를 삭제하는 작업에서는 각 노드가 가져야 할 최소 키의 개수 정보가 매우 중요해진다.
해당 정보를 가지고 데이터 삭제 후 최소 키 수보다 적어졌다면 B-트리를 재조정하게 된다.
위의 예제 그림은 3차 B-트리로 각 노드마다 가지고 있을 수 있는 최소 키의 개수는 1개이다.
3가지 케이스를 가지고 어떻게 삭제 작업이 동작하는지 알아보자.
- Case 1. 키 수가 여유 있는 형제의 지원을 받는다.
만약 예제 그림에서 5를 삭제한다고 가정해 보자.
5를 삭제하게 되면 위의 그림과 같이 노드가 가지고 있는 키의 개수는 0이 된다. 하지만 각 노드는 최소 1개 이상의 키를 가져야 하기 때문에 B-트리를 다시 재조정해야 하는데 이때 형제 노드 중에서 키를 지원받게 된다.
위의 그림과 같이 다시 B-트리가 재조정된 것을 알 수 있다. 하지만 여기서 주의할 점은 형제 노드에서 키를 지원받을 때는 곧바로 받는 것이 아니라 부모 노드의 키를 받고 형제 노드의 키가 부모 노드의 키를 채우는 식으로 동작하게 된다는 점이다.
- Case 2. 형제 노드에 여유가 없다면 부모의 지원을 받고 형제와 합친다.
앞서 마지막으로 봤던 예제 그림에서 3을 삭제하고 난 뒤의 그림이다.
만약 7을 삭제하게 되면 어떻게 될까? 양 옆에 위치한 형제 노드에서는 키를 1개씩 가지고 있기 때문에 지원을 받을 수 없는 상황이다. 이때는 부모에서 키를 지원받고 형제 노드와 합치게 된다.
그림과 같이 부모가 가지고 있던 2를 자식 노드로 지원을 해주고 기존의 7을 가지고 있던 노드와 형제 노드를 합친다.
- Case 3. 부모의 지원을 받고 난 뒤 부모에 문제가 생기면 다시 재조정을 한다.
이번에는 부모 노드에서 키가 부족할 때를 살펴보자.
마지막 예제 그림에서 키 1과 2를 순서대로 삭제했다고 가정해 보자.
삭제가 완료되면 왼쪽 자식 노드가 가지고 있는 키의 개수는 0이 되기 때문에 앞서 살펴봤던 2번 케이스를 통해서 부모에게 지원을 받아야 한다.
부모에게 키를 지원받고 보니 문제가 생기는데 이번에는 부모가 가지고 있는 키가 없다.
이때는 2번 케이스와 똑같이 동작하게 되는데 루트 노드에서 키를 지원받고 같은 형제 노드와 합치는 과정을 수행하게 된다.
그림과 같이 키 15와 30이 합쳐지고 루트 노드는 비워진다.
루트 노드도 최소한 키를 1개 이상 가져야 이상할 게 없을 것 같은데 다시 위로 올라가서 확인해 보면 각 노드가 가져야 할 최소 키의 개수 규칙은 루트 노드에 적용되지 않는다.
따라서 비어진 루트 노드는 삭제되고 직전에 합쳐진 노드가 새로운 루트 노드가 된다.
- ※ Internal 노드를 삭제할 경우
이때까지 알아봤던 삭제 방법은 루트 노드부터 비교하면서 리프 노드까지 찾아본 뒤 리프 노드부터 삭제하는 방법이었다.
하지만 삭제할 값이 internal 노드 즉, 리프 노드가 아닌 내부 노드에서 바로 삭제하려면 어떻게 해야 될까?
internal 노드에 있는 데이터를 삭제하려면 리프 노드에 있는 데이터와 위치를 바꾼 후 삭제하게 되는데 이때 나오는 개념이 선임자와 후임자 개념이다.
- 선임자(predecessor): 나보다 작은 데이터들 중 가장 큰 데이터
- 후임자(successor): 나보다 큰 데이터들 중 가장 작은 데이터
만약 위와 같이 예제 그림에서 15를 삭제한다고 가정해 보자.
15를 삭제하기 위해서는 선임자와 후임자를 알아야 하는데 그림에서 표현해 보면 선임자는 9, 후임자는 20이 된다.
이 중에서 선임자를 활용한다고 하면 15와 9의 위치를 바꿔준 뒤 15를 삭제하면 된다.
굳이 리프 노드와 바꿔야 할 이유가 있을까 생각해 보면 모든 노드가 최대 개수만큼 키를 가지고 있다고 생각해 봤을 때 리프 노드가 아닌 자식 노드와 위치를 변경하는 것은 매우 비효율적이라 생각한다.
위의 그림만 봐도 만약 15를 왼쪽 자식 노드인 7과 변경한다면 15가 삭제되고 나서 노드가 가지고 있는 키는 3밖에 없기 때문에 리프 노드까지 영향을 끼치게 된다.
하지만 internal 노드와 리프 노드 간의 변경은 따로 자식 노드에 영향을 미치지 않기 때문에 보다 효율적이다.
B-트리는 뭐가 좋을까
B-트리는 모든 케이스에 O(logN)의 시간복잡도를 가져서 매우 좋은 성능을 보여준다. 여기서 한 가지 의문이 드는 것이 있는데 다른 자가 균형 이진 탐색 트리도 같은 O(logN) 시간복잡도를 가진다는 점이다.
| 종류 | B-Tree | AVL-Tree | ||||
| 구분 | Best | Avg | Worst | Best | Avg | Worst |
| 조회 | O(logN) | O(logN) | ||||
| 삽입 | ||||||
| 삭제 | ||||||
B-트리와 Self-Balacing BST의 종류인 AVL 트리와 비교해 보면 모두 동일한 O(logN)이다.
그렇다면 둘의 사용 용도가 어떻게 다른 것일까?
DB의 인덱스가 B-트리 기반으로 동작한다는 것은 개발을 공부해 본 사람이라면 대부분 알 것이다.
그럼 왜 인덱스가 B-트리 기반으로 동작할까? 같은 시간 복잡도라면 AVL 트리도 있고, 레드-블랙 트리도 있는데 왜 굳이 B-트리를 사용하는 것일까?
DB가 저장되는 곳은 보조 기억장치(디스크)이다.
이러한 보조 기억장치는 물리적인 장치이기 때문에 데이터를 처리하는 속도가 다른 메모리에 비해서 상당히 느리다.
또한 데이터를 보조 기억장치에서 찾아서 메인 메모리에 올리면 찾은 데이터 하나만 올리는 것이 아닌 데이터 묶음 즉, 블록 단위로 메인 메모리에 올리게 된다.
보조 기억장치는 데이터를 조회하는데 속도가 느리고, 원하는 데이터를 찾는다고 해도 블록 단위로 메모리에 올리기 때문에 공간 낭비가 발생할 수 있다.
이러한 문제를 해결하기 위해서는 보조 기억장치에 접근하는 횟수를 줄이고, 메인 메모리에 올라가는 블록에 연관된 데이터를 모아서 저장하면 효율적으로 읽고 쓸 수 있다.
B-트리를 사용한다면 다른 트리와 다르게 여러 데이터를 하나의 노드에 저장할 수 있고 이를 통해서 트리의 깊이가 낮아지기 때문에 보다 적은 횟수로 데이터를 찾을 수 있게 된다.
또한, B-트리는 다른 트리와 다르게 범위라는 개념을 가지기 때문에 데이터를 조회할 때 탐색 범위를 빠르게 좁힐 수 있다.
이러한 B-트리의 장점으로 대부분의 관계형 데이터베이스에서 인덱스에 B-트리 구조를 사용한다고 한다.
대표적으로 MySQL에서 인덱스 부분 공식 문서를 살펴보면 아래와 같이 설명한다.
대부분의 MySQL 인덱스(PRIMARY KEY, UNIQUE, INDEX 및 FULLTEXT)는 B-트리에 저장됩니다.
B-트리는 뭐가 안 좋을까
B-트리의 삽입과 삭제 동작 과정을 보면 트리의 균형을 유지하기 위해 상당히 복잡한 연산을 수행한다는 것을 알 수 있다. 삽입할 때는 키의 개수에 따라 노드를 분할하고 키를 승진시켜야 하고, 삭제할 때는 부모로 키를 지원받고 형제 노드와 합치는 등 과정이 너무 복잡하다.
또한, 하나의 노드에 여러 개의 데이터를 저장할 수 있는 점은 좋지만 반대로 여러 개의 키와 포인터를 저장해야 하기 때문에 메모리 사용량이 상대적으로 높다.
따라서 적은 양의 데이터라면 굳이 B-트리를 사용하지 않는 것이 더 좋을 것 같다.
B+ 트리
앞서 B-트리를 설명할 때 인덱스가 B-트리 기반으로 생성된다고 했는데 실제로는 B-트리 뿐만 아니라 같은 B-트리 계열을 사용하여 인덱스를 생성하게 된다.
B+ 트리는 B-트리 의 변형으로 모든 실제 데이터는 리프 노드에만 저장되고 internal 노드는 인덱싱 용도로만 사용되는 트리 구조이다.
범위 검색에 최적화되어 있다.
B+ 트리는 뭐가 좋을까
B+ 트리는 범위 내의 데이터를 빠르게 순회할 수 있다.
internal 노드는 인덱싱 역할만 하기 때문에 노드당 저장되는 키의 수가 많아져 트리의 높이를 낮출 수 있다. 이를 통해서 디스크 접근 횟수를 더욱 줄일 수 있다.
모든 데이터는 리프 노드에만 저장되기 때문에 데이터 접근하기 더욱 편리하다.
하지만 internal 노드가 인덱스만 저장하게 되면서 공간 활용 측면에서는 약간의 낭비가 있을 수 있다.
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] - Set (0) | 2024.10.25 |
|---|---|
| 자료구조 - 해시(Hash) (0) | 2024.06.20 |
| 자료구조 - 힙 (0) | 2024.06.17 |
| 자료구조 - 레드 블랙 트리 (0) | 2024.06.17 |
| 자료구조 - AVL 트리 (0) | 2023.12.10 |
