soowanlog
B-tree 본문
- B-tree란?
B-tree란 Balanced-tree를 의미하며 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종입니다.
이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다.
- B-tree의 특징
B-tree는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가질 수 있습니다.
최대 M개의 자식을 가질 수 있는 B-tree를 M차 B-tree라고 합니다.
- 탐색 시 루트노드에서부터 하향식으로 탐색합니다.
- 노드 안 데이터는 오름차순으로 정렬됩니다.
- 노드는 최대 M개의 자식 노드를 가질 수 있습니다.
3차 B-tree라면 최대 3개의 자식 노드를 가질 수 있습니다.
- 루트 노드와 리프 노드를 제외한 각 노드는 최소 [M/2]개의 자식 노드를 가집니다.
3차 B-tree라면 각 노드는 최소 2개의 자식 노드를 가집니다.
- 노드에는 최대 M-1개의 key를 가질 수 있습니다.
3차 B-tree라면 최대 2개의 key를 가질 수 있습니다.
- 루드 노드를 제외한 각 노드는 최소 [M/2]-1개의 key를 가집니다.
3차 B-tree라면 각 노드는 최소 1개의 key를 가집니다.
※ 루트 노드
트리 구조에서 가장 위에 있는 노드.※ 리프 노드
트리 구조에서 자식 노드가 없는 노드.※ 가우스 기호
[x]로 표기하고 주어진 실수 x보다 크거나 같은 최소 정수를 나타내는 기호.
- B-tree의 데이터 삽입
데이터 삽입은 항상 리프 노드에 합니다.
데이터를 삽입하는 과정에서 노드가 가질 수 있는 최대 key의 개수인 M-1개를 넘게 된다면 가운데 key를 기준으로 좌우 key들을 분할하고 가운데 key는 승진합니다.
- 분할이 일어나지 않는 경우
- 분할이 일어나는 경우
- B-tree의 데이터 삭제
데이터 삭제 시에도 B-tree의 특징에 맞춰서 재조정이 일어납니다.
- 형제 노드의 지원을 받는 과정은 다음과 같습니다.
1. 동생(왼쪽 형제)이 여유가 있는 경우
동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 두고 원래 부모 노드에 있던 key는 나의 가장 왼쪽에 둡니다.
2. 형(오른쪽 형제)이 여유가 있는 경우
형의 가장 작은 key를 부모 노드의 나와 형 사이에 두고 원래 부모 노드에 있던 key는 나의 가장 오른쪽에 둡니다.
- 부모 노드의 지원을 받는 과정은 다음과 같습니다.
1. 동생이 있으는 경우
동생과 나 사이의 key를 부모 노드로부터 받고 그 key와 나의 key를 차례로 동생에게 합친 뒤 나의 노드를 삭제합니다.
2. 동생이 없는 경우
형과 나 사이의 key를 부모 노드로부터 받고 그 key와 형의 key를 차례로 나에게 합친 뒤 형의 노드를 삭제합니다.
참 고 자 료
- B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정 | chanyoung1998.log
- B-tree란? / B-tree의 연산 / B*tree, B+tree / B+tree 구현 | 공영재
'자료구조' 카테고리의 다른 글
| Linked List (0) | 2024.03.26 |
|---|---|
| Array (0) | 2024.03.25 |
