B-Tree
B-Tree는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가실 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
B-Tree는 노드 접근 시간이 노드에서의 연산 시간에 비해 훨씬 길 경우 다른 구현 방식에 비해 이점을 가진다. 이는 대부분의 노드가 HDD와 같은 보조 기억장치에 있을 때 일반적으로 일어난다.
B-Tree의 조건
M차 B-Tree에 대하여 (M = 트리의 차수(degree), 노드의 자식 개수 중 최대인 것)
- 모든 리프 노드는 같은 깊이를 가진다.
- 루트 노드의 자식 노드 수는 2 이상이다.
- 특정한 데이터의 왼쪽 서브 트리는 해당 데이터보다 작으며 오른쪽 서브 트리는 해당 데이터보다 크다.
- 노드는 최대 M-1개부터 \ceil[\big]{frac{M}{2}} - 1개의 키를 가질 수 있다.
- 루트 노드와 리프 노드를 제외한 노드는 최소한 \ceil[\big]{frac{M}{2}} 개의 자식을 가진다.
2-3-4 트리: 모든 내부 노드가 2, 3 또는 4개의 자식 노드를 갖는 트리
B-Tree의 검색
검색하려는 키를 k라고 하자.
- 루트 노드에서 시작하여 노드의 첫번째 키를 k와 비교한다. 만약 k가 노드의 첫번째 키와 같다면 그 노드와 인덱스를 반환한다.
- 만약 k가 노드의 첫번째 키보다 작다면 왼쪽 자식에서 재귀적으로 k와 비교한다.
- 만약 현재 노드에 하나 이상의 키가 있고 k가 노드의 첫번째 키보다 크다면 k를 현재 노드의 다음 키와 비교한다.
- 2-3을 리프 노드에 도달할 때까지 반복한다.
B-Tree의 삽입
- 트리가 비어있다면 루트 노드를 할당하고 키를 삽입한다. 이후 노드에 넣을 수 있는 키의 갯수를 갱신한다.
- 키를 삽입할 리프 노드를 검색한다. 중간 노드에 삽입하지 않는다.
- 노드가 가득 찬 경우 리프 노드를 중앙값 (차수가 짝수일 경우 왼쪽 그룹의 최대값) 에서 분할한다.
- 중앙값은 부모 노드로 보내고 왼쪽 키들은 왼쪽 자식 노드, 오른쪽 키들은 오른쪽 자식 노드로 만든다.
- 중앙값이 추가된 부모 노드가 가득 찼을 경우 4를 반복한다.
B-Tree의 삭제
Case 1. 삭제할 키가 리프에 있는 경우
if 현재 노드에 키가 최소 키수보다 크다면:
그냥 삭제한다.
elif 왼쪽 형제 노드의 키가 최소 키수보다 크다면:
1. 왼쪽 형제를 방문하고, 왼쪽 형제 노드에서 가장 큰 키를 저장한다.(tmp)
2. 현재 키를 삭제한다.
3. 부모 노드를 현재 위치로 내리고, tmp를 부모 노드로 이동시킨다.
elif 오른쪽 형제 노드의 키가 최소 키수보다 크다면:
1. 오른쪽 형제를 방문하고, 오른쪽 형제 노드에서 가장 작은 키를 저장한다.(tmp)
2. 현재 키를 삭제한다.
3. 부모 노드를 현재 위치로 내리고, tmp를 부모 노드로 이동시킨다.
elif 부모의 키가 최소 키수보다 크다면 :
부모키를 내려서 왼쪽 형제 노드랑 병합한다.
(부모키란 현재 `index-1`번째 키를 의미한다.
단, 0번 index일 땐, 0번째 부모키로 처리한다.)
else (부모 노드의 키가 최소만큼이라면):
키를 삭제하고, 부모 노드를 아래로 내리고, case3의 2번 과정으로 이동한다.
Case 2. 삭제할 키가 내부 노드에 있고, 노드나 자식에 키가 최소 키수보다 많을 경우
if 자식이 리프인 경우:
if 그 자식의 키가 최소 키수보다 크다면:
키를 삭제한 후, 그 자식에서 가장 큰 값으로 삭제된 부분을 대체한다.
elif 내 키수가 최소 키수보다 크다면:
현재 키를 삭제한 후, 내 키의 자식 노드들을 병합한다. (왼쪽으로)
else (나와 자식 모두 최소 키수인 경우):
case 3으로 이동한다.
else (자식이 리프가 아닌 경우):
왼쪽 자손의 inorder predecessor(리프)와 현재 키의 자리를 바꾼다.
현재 키를 삭제한 후, case 1으로 이동한다.
Case 3. 삭제할 키가 내부 노드에 있고, 노드에 키가 최소만큼, 노드의 자식의 키도 모두 최소인 경우
이 경우에는 삭제할 키가 있는 노드도 최소, 내 자식들도 최소이므로, 키를 삭제하면 트리의 높이가 줄어든다.
1. 양쪽 자식을 병합하여, tmp변수에 저장한다.
2. 현재 키를 삭제한다.
3. 나의 부모 키를 왼쪽 형제 노드에 붙인다.
4. 이 형제 노드의 마지막에 tmp를 붙인다.
if 형제 노드가 최대 키수를 넘어갔다면:
삽입 연산의 4-a를 수행한 후, 종료한다.
else:
if 부모 노드가 최소 키수보다 작다면:
부모 노드에 대하여 2번 과정부터 반복한다.
else: 종료한다.
예시
References
Introduction to Algorithms