[개발 일기] 2025.01.15 - B-Tree

개요

 

어젠 이진 탐색 트리에 대한 일기를 썼다.

 

 

오늘은 이진 탐색 트리의 단점을 보완한 자료구조인 B-Tree에 대해 정리해 보자.

 

 

 

B-Tree

 

B-Tree는 데이터베이스 및 파일 시스템과 같은 대규모 데이터 구조에서 데이터를 효율적으로 관리하기 위해 설계된 트리형태의 자료구조이다.

 

 

B-Tree의 탄생 이유는 위에서 언급했었던 것처럼 이진 탐색 트리의 단점을 생각하면 된다.

 

 

이진 탐색 트리의 단점은 어제 일기에서 작성한 것을 조금 언급하자면 균형 잡힌 데이터가 삽입된다면 아래의 이미지처럼 트리가 한쪽으로 치우친 선형 구조(일종의 연결 리스트)로 변형된다.

 

하지만 이진트리의 경우 데이터의 삽입, 삭제 시 트리 구조를 재조정하여 항상 균형 잡힌 상태를 유지한다.

 

 

그 방법은 아래에서 더 자세히 설명하겠다.

 

 

또한 이진 탐색 트리는 각 노드는 2개의 자식 노드를 가질 수 있지만, B-Tree는 2개 이상의 자식 노드를 가질 수 있을뿐더러, 노드 내의 데

이터가 1개 이상일 수 있다.

 

 

이렇게 각 노드별로 저장할 수 있는 값의 개수가 증가하게 되면 자연스럽게 트리의 높이도 낮아지게 된다.

→ 자연스럽게 탐색에 더 유리해지는 것!

 

 

이러한 B-Tree의 트리를 보면 데이터베이스와 같은 대규모 데이터를 다루는 환경에 적합하다는 생각이 든다.

 

 

 

B-Tree 규약

 

B-Tree는 하나의 노드에 여러 값을 저장할 수 있다.

 

 

노드 내 저장할 수 있는 값의 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree라고 한다.

 

 

이렇게 여러 값을 하나의 노드에 저장할 수 있지만, 그에 따른 규약이 있다.

• 각 노드는 최소⌈M/2⌉개자식 노드를 가짐
• 각 노드는 ⌈M/2⌉−1개부터 M-1개의 키를 가짐
• 루트 노드는 최소 2개의 자식을 가짐
• 부모 노드의 키가 A개라면 자식 노드는 A+1개를 가짐
• 모든 리프 노드는 동일한 깊이

 

 

(참고) ⌈숫자⌉

⌈숫자⌉ 기호는 숫자보다 크거나 같은 가장 작은 정수를 의미한다.

 

 

 

탐색 연산

 

 

탐색 연산은 기본적으로 이분 탐색 트리와 비슷하다. 하지만 위에서 언급했다시피 B-Tree는 하나의 노드에 여러 개의 값을 가지고 있을 수 있다.

 

 

그렇기 때문에 단순히 찾고자 하는 값보다 작으면 왼쪽 자식, 크면 오른쪽 자식과 같이 탐색을 하면 안 된다.

 

 

그렇기 때문에 B-Tree에선 Key와 Pointer를 사용한다.

 

 

위의 트리 이미지에선 숫자는 Key고, 빨간색 사각형은 Pointer에 해당한다.

 

 

아래는 내가 찾고자 하는 값이 25인 경우이다.

 

(1) : 찾고자 하는 값이 10보다 작은 경우

(2) : 찾고자 하는 값이 10보다 크고, 20보다 작은 경우

(3) : 찾고자 하는 값이 20보다 큰 경우

 

우리가 찾는 값은 25이기 때문에 (3) 포인터가 사용된다.

 

이러한 흐름으로 각 노드의 Key를 비교하고, 그에 맞는 Pointer를 사용하며 데이터를 찾는 것이다.

 

 

 

삽입 연산

 

위의 트리는 3차 B-Tree이다. (M=3)

 

 

B-Tree에서 삽입 연산은 두 가지 경우로 나뉜다.

1. 분할이 발생하지 않는 경우
2. 분할이 발생하는 경우

 

분할이 발생하지 않는 경우

 

아래는 9를 삽입하는 상황이다. 그냥 삽입하면 된다.

 

분할이 발생하는 경우

 

위의 3차 B-Tree의 규약을 정리해 보자.

• 각 노드는 최소 ⌈M/2⌉개자식 노드를 가짐
  • 3차 B-Tree에서 각 노드는 최소 ⌈4/2⌉ = 2개의 자식 노드를 가진다.
• 각 노드는 ⌈M/2⌉−1개부터 M-1개의 키를 가짐
  • 3차 B-Tree에서 각 노드는 1개 or 2개의 키를 가질 수 있다.
• 루트 노드는 최소 2개의 자식을 가짐

 

아래는 13을 추가하는 경우이다.

 

보다시피 11과 12가 있는 노드에 13을 추가해야 하지만, 이미 가지고 있는 Key가 2개이기 때문에, 13을 넣을 수 없다.

 

 

이런 경우에 분할이 발생한다.

 

 

일단 13을 11, 12가 있는 노드에 삽입한다.

 

그리고 그 노드의 중간 값 Key을 부모 노드에 삽입한다.

 

 

그러면 아래와 같은 형태의 트리가 된다.

 

하지만 12, 14, 17도 가지고 있는 Key가 3개이므로, 분할을 진행한다.

 

 

분할 방법은 이전과 동일하게 12, 14, 17의 중간 값 Key인 14를 부모 노드에 삽입한다.

 

하지만 또다시 루트 노드가 10, 14, 20 3개의 Key를 가지게 되었다.

 

 

여기서도 동일하게 분할을 진행한다. 분할을 진행하면 루트 노드는 14가 된다.

 

 

 

삭제 연산

 

삭제 연산은 크게 두 가지 경우로 나뉜다.

• 삭제할 Key가 리프노드에 있는 경우
  • 삭제하는 Key가 있는 노드의 key 개수가 최소 key 개수보다 클 경우
  • 삭제하는 Key의 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수 이상인 경우
  • 삭제하는 Key의 왼쪽, 오른쪽 형제 노드의 key가 최소 key 개수이고, 부모노드의 key가 최소개수 이상인 경우
• 삭제할 Key가 내부에 있는 경우

 

 

삭제할 Key가 리프노드에 있는 경우 - 삭제하는 Key가 있는 노드의 key 개수가 최소 key 개수보다 클 경우

 

그냥 삭제하면 된다.

 

 

아래는 12를 삭제하는 경우이다.

 

 

삭제 후, 따로 정렬할 필요 없다.

 

 

삭제할 Key가 리프노드에 있는 경우 - 삭제하는 Key의 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수 이상인 경우

 

아래는 15를 삭제하는 경우이다.

 

15를 삭제한 뒤, 해당 노드의 위치를 부모 노드의 Key로 교체해 준다. 참고로 15의 부모 Key는 14이다.

 

 

그리고 왼쪽 형제 노드에 있는 Key 중에서 가장 큰 Key를 부모 Key 위치로 옮긴다.

 

 

삭제할 Key가 리프노드에 있는 경우 - 삭제하는 Key의 왼쪽, 오른쪽 형제 노드의 key가 최소 key 개수이고, 부모노드의 key가 최소개수 이상

 

아래는 18을 삭제하는 경우이다.

 

 

18을 삭제한 후, 부모 key를 왼쪽 형제 노드와 합친다.

 

그러면 아래와 같은 트리 형태가 된다.

 

 

 

느낀 점

 

확실히 이진 탐색 트리보다 더 난이도가 어렵다.

 

 

많은 데이터를 저장하고 효율적으로 관리하기 위해선, 지속적인 정렬이 필수적이라서 그런 것 같다.