B-Tree 구조
매우 중요한 자료 구조 중 하나, 데이터베이스와 파일 시스템에서 자주 사용된다.
균형 이진 탐색 트리(Binary Search Tree)의 일반화된 형태로, 노드가 다수의 자식을 가질 수 있어 데이터의 삽입, 삭제, 검색이 효율적으로 이루어집니다.
이진 탐색 트리(BST)
노드의 개수가 최대 2개까지 가질 수 있다.
모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다.
B-Tree의 파라미터
- M : 각 노드의 최대 자녀 노드 수(가장 중요한 파라미터)
- 최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부른다.
- M-1 : 각 노드의 최대 Key 수
- ⌈M/2⌉ : 각 노드의 최소 자녀 노드수
- ⌈ ⌉ -> 올림 기호
- 만약 M이 3이라면 3/2 = 1.5인데 올림을 해야 해서 최소 자녀 노드수는 2가 된다.
- root node, leaf node는 제외
- ⌈M/2⌉ -1 : 각 노드의 최소 key 수
- root node 제외
B-Tree 특징
internal 노드의 key수가 x 개라면 자녀 노드의 수는 언제나 x+1 개다.
위의 그림은 x가 2개인데 자녀 노드가 2개이기 때문에 x+1의 규칙을 벗어납니다. b-tree에서 이런 구조는 있을 수 없습니다
또한, 아래의 그림처럼 x=1인 상황에서 자녀 노드가 3이면 x+1 규칙에 어긋나기 때문에 이런 구조도 있을 수 없습니다.
Tip)
노드가 최소 하나의 key는 가지기 때문에 몇 차 B-Tree 인지와 상관없이 internal 노드는 최소 두 개의 자녀는 가진다.
B-Tree 데이터 삽입
- 데이터 추가는 항상 leaf 노드에서 발생한다.
- 노드가 넘치면 가운데(median) key를 기준으로 좌우 key들은 분활하고 가운데 key는 올라간다.
예를 들어, 3차 B-Tree가 있다고 할 때 데이터를 삽입하면?
1 추가
M : 각 노드의 최대 자녀 노드수
M-1: 각 노드의 최대 key 수
3차 B-Tree를 사용하기 때문에 각 노드의 최대 key 수가 3-1 = 2로 2칸을 가지게 된다.
15 추가
추가는 항상 leaf 노드에서 발생한다.
가장 처음에는 root 노드이기도 하지만 leaf 노드이기도 하기 때문에 처음 1을 추가했던 노드에 추가된다.
2 추가
노드는 항상 오름차순 정렬이된 상태로 저장을 하게 됩니다.
최대 key의 수는 2인데 데이터가 3개가 되었기 때문에 노드에 저장할 수 없습니다. 그래서 분할이 발생합니다. 가운데 있던 2는 위로 올라가고 좌우에 있던 1과 15가 양쪽으로 분할이 되어 2의 자식 노드가 됩니다.
5 추가
5를 추가하면 2보다 크기 때문에 15가 있는 노드에 가게 될 것입니다. 노드는 항상 오름차순 정렬이 된 상태이기 때문에 15의 앞에 위치하게 될 것입니다.
30 추가
2보다 크기 때문에 5, 15가 있는 노드로 갑니다. 5, 15, 30이 되기 때문에 분할을 합니다. 5는 그대로 있고 15는 root노드로 올라가 2, 15가 됩니다. 그리고 30은 따로 노드를 만들어서 저장이 됩니다.
90 추가
2와 먼저 비교해서 2보다 크기 때문에 15와 비교를 해줍니다. 여전히 15보다 크기 때문에 30이 있는 노드로 갑니다. 빈 공간이 있고 30보다 크기 때문에 30 뒤에 저장이 됩니다.
20 추가
맨 처음 root노드의 2, 15와 비교하는데 20이 더 크기 때문에 30이 있는 곳에 갑니다. 정렬된 상태로 20, 30, 90의 데이터를 가집니다. 하지만, 노드가 최대 2개까지 밖에 key를 가질 수 없기 때문에 분할을 합니다. 가운데 있던 30은 올라갑니다.
그럼 root 노드가 최대 key인 2개를 넘어가기 때문에 분할이 되어 2, 30인 자녀노드가 되고 root노드가 생성되고 15를 root 노드에 올려줍니다.
7 추가
root에 있는 15와 비교합니다. 이어서 2와 비교를 하고 5가 있는 노드에 자리가 비어 있으므로 5가 있는 노드에 저장됩니다.
9 추가
15와 비교합니다. 이어서 2와 비교합니다 5가 있는 곳에 가는데 이미 자리가 없습니다. 5, 7, 9 이렇게 데이터가 있기 때문에 분할이 발생합니다. 7을 2가 있는 노드로 올리고 7을 5와 9를 가리키도록 합니다.
8 추가
root인 15와 비교 다음 2와 비교합니다. 8이 더 크기 때문에 7과 비교를 합니다. 여전히 8이 더 크기 때문에 9가 있는 노드로 갑니다. 자리가 있기 때문에 8이 오름차순 정렬되어 저장됩니다.
10 추가
15와 비교합니다. 15가 더 크기 때문에 2와 비교합니다. 다음 7과 비교하고 10이 더 크기 때문에 8,9 가 있는 노드로 갑니다. 8, 9, 10이 되기 때문에 분할을 하고 9를 2, 7이 있는 노드로 올립니다.
그럼 2, 7, 9가 되기 때문에 또 분할을 합니다. 그럼 가운데 7을 15가 있는 노드로 올립니다.
50 추가
7보다 크기 때문에 15와 비교 30과 비교 90보다 작기 때문에 90 앞에 위치합니다.
70 추가
7과 먼저 비교하고 70이 더 크기 때문에 15와 비교합니다. 30보다 크기 때문에 50, 70, 90이 됩니다. 분할을 합니다. 30이 있는 노드로 70을 올립니다. 70은 50, 90을 바라봅니다.
60 추가
7보다 크기 때문에 15와 비교를 하고 30과 비교를 합니다. 30보다 크기 때문에 70과 비교합니다. 70보다 작기 때문에 50이 있는 노드로 가서 데이터가 저장됩니다.
40 추가
7, 15와 비교, 30보다 크고 70보다 작기 때문에 40, 50 ,60이 됩니다. 노드가 넘치기 때문에 분할을 합니다. 60이 저장될 노드가 만들어지고 50은 올라갑니다. 그럼 30, 50, 70이기 때문에 또 분할됩니다. 70이 저장될 노드가 생성이 되고 50은 올라가게 됩니다. 여기서 7, 15, 50이 되기 때문에 root노드가 생성이 됩니다. 15는 root노드에 올라가고 50은 분할된 root노드의 오른쪽 노드가 됩니다.
모든 leaf 노드들은 같은 레벨에 있다. -> balanced tree
검색 avg/worst case O(log N)
