TIL 008 B트리

B트리를 공부하기 위해 다음 링크의 자료를 번역하고 정리하였다. 이미지와 코드가 함께 나와 있음으로 다음 링크에서 참조하면서 공부하면 좋을 것 같다.
https://www.programiz.com/dsa/b-tree

c로 구현한 b트리 링크이다.
github 링크

👉 B트리란

B트리는 self-balancing search tree 노드 당 한 개 이상의 키를 가짐으로서 여러 개의 자식을 둘 수 있는 자료구조이다.

👉 왜 B트리인가?

B트리가 필요한 이유는 하드디스크를 빠르게 사용하기 위함이다. 기존의 자료구조는 여러 개의 키(key)를 가지게 되면 트리의 높이(height)를 가지게 되고, 자료를 읽어드리는데 많은 시간을 필요로 하게 된다. B트리는 여러 개의 키를 한 노드에 사용함으로서 높이를 줄이고 빠르게 데이터에 접근할 수 있게 한다.
또한, 메인 메모리와 Secondary 메모리의 수행속도가 다름으로, main 메모리 입장에서는 시간 복잡도가 더 줄어든다.

👉 B트리 특성

모든 노드 x에는 key가 오름차순으로 담겨있다.
각 노드에는 x.leaf가 boolean이 x의 leaf 여부를 담는다.
n차원의 B트리는 n-1개의 key를 갖는다
루르를 제외한 모든 노드는 최대 n개, 최소 n/2개의 자식을 갖는다.
모든 가지(leaf)는 같은 깊이(depth)를 갖는다.
루트는 최소 1개의 key와 2개의 자식을 갖는다.

👉 B트리 기능

1. 탐색

기본적으로 이진 탐색과 같다.

• 루트부터 시작해, 첫 번째 키 값과 비교해 내려간다. 만약 키 값이 같을 경우 index와 노드를 리턴한다.
• 만약 k.leaf = True 라면 Null 값을 반환한다.
• 만약 k < 첫 번째 키 값이라면, 이 키의 왼쪽 자식들을 탐색해나간다.
• 만약 k > 첫 번째 키 값이라면, 이 노드의 다음 키들과 비교한다. 만약 k < 다음 키 값이라면, 이 키의 왼쪽 자식들을 탐색해나간다. 마지막 키 값보다 크다면 이 노드의 오른쪽 자식들을 탐색해나간다.
• 값을 찾거나, leaf에 닿을 때까지 위를 반복한다.

BtreeSearch(x,k)
i=1
while i<= n[x] and k >= keyi[x]: # n[x] means number of keys in x node
	do i = i + 1
if k= keyi[x]:
	return (x, i)
if leaf[x]:
	return Null
else
	return BtreeSearch(ci[x], k)

2. 삽입

B트리의 삽입은 두 가지 과정을 거친다.
1) 삽입할 위치까지의 탐색한 뒤 삽입
2) 필요한 경우의 노드 분할

• 만약 트리가 비어있다면, 루트를 할당하고 키를 삽입한다.
• 노드의 키 갯수를 갱신한다.
• 삽입될 노드를 탐색한다.
• 만약 노드가 가득 차 있다면, 다음 스텝들을 실행한다.
• • 일단 오름차순에 따라 삽입을 한다.
• • 이제, 이제 노드 수가 limit을 넘겼기 때문에 중간(median)을 기준을 분할시킨다.
• • 중간 키를 부모의 키로 보낸다. 왼쪽 키들은 왼쪽 자식으로 오른쪽 키들은 오른쪽 자식으로 나눈다.
• • (부모로 보낸 키에 의해 부모도 limit을 넘김다면 같은 스텝이 실행된다.)
• 만약 노드가 가직 차지 않았다면, 오름차순에 따라 삽입한다.

3. 삭제

B트리의 삭제는 세 가지 과정을 거친다.
1) 삭제할 키를 탐색
2) 키 삭제
3) B트리 조건을 만족시킨다. 이때 노드가 최소의 키 갯수를 가지지 못하는 underflow가 발생할 수 있다.

Case#1: leaf에서 삭제 될 때

• 삭제 후에도 키가 최소 갯수 이상으로 남을 때 -> OK.
• 삭제 후에 키가 최소 갯수 아래 일 때 -> 다음 스텝 실행
• • 왼쪽 형제(sibling) 노드가 키를 나눠주어도 최소 갯수 이상일 때 -> 왼쪽 형제 노드에 가장 오른쪽 키를 부모 노드로 보내고, 원래 있던 부모 키로 내 부족한 키를 채운다.
• • 왼쪽 형제가 줄 수 없고, 오른쪽 형제 노드가 키를 나눠줄 수 있을 때 -> 오른쪽 형제 노드에 가장 왼쪽 키를 부모 노드로 보내고 원래 있던 부모 키로 내 부족한 키를 채운다.
• • 둘 다 키를 나눠 줄 수 없을 때-> 왼쪽 부모 키를 왼쪽 자녀 키 값과 합쳐 새로운 노드를 만든다.

Case#2: 트리 내부에서 삭제 될 때
inorder predecessor = 내 노드의 왼쪽 자식 노드 중 가장 큰 키
inorder successor = 내 노드의 오른쪽 자식 노드 중 가장 작은 키

• 만약 왼쪽 자식이 더 자식이 많고 inorder predecessor로 삭제된 키가 대체되어도 자식 노드가 최소 갯수를 가질 때 -> OK.
• 만약 오른쪽 자식이 더 자식이 많고 inorder successor로 삭제된 키가 대체되어도 자식 노드가 최소 갯수를 가질 때 -> OK.
• 둘 다 줄 수 없을 때 -> 왼쪽 자식과 오른쪽 자식을 합친다.
• • 자식들을 합친후 부모 노드가 최소한의 갯수를 가지지 못할때 case#1 을 실행해 채워준다.

Case#3: 트리의 높이(height)가 축소 될 때

• 만약 case#2 처럼 트리 내부에서 삭제가 일어났지만 자식들이 키를 올려 줄 수 없어서, case#1으로 들어갔지만 형제 노드들도 키를 나눠 줄 수 없을 때는, 어디서도 키를 가져 올 수 없어서 높이의 축소가 일어난다.
• 이 때는, 부모 노드와 형제 노드를 합쳐주고, 자식들을 오름차순으로 넣어준다.