🌳 B-Tree란?
- 데이터를 정렬된 상태로 저장하고, 검색, 삽입, 삭제를 효율적으로 수행할 수 있는 균형 트리 구조이다.
- 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장된다.
- 부모 노드의 key들을 오름차순으로 정렬
- 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.
➡ 탐색 속도(log n)를 유지하면서
➡ 디스크 접근 횟수를 최소화하도록 설계된 트리
➡ B tree는 BST를 일반화한 tree
M : 각 노드의 최대 자녀 노드 수
M-1 : 각 노드의 최대 key 수
⌈M/2⌉ : 각 노드의 최소 자녀 노드 수(root node, leaf node 제외)
⌈M/2⌉-1 : 각 노드의 최소 key 수 (root node 제외)
🌳 B-Tree 삽입
- 추가는 항상 leaf 노드에 한다.
- 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.
- 모든 leaf 노드들은 같은 레벨에 있다.
🌳 B-Tree 삭제
- 삭제도 항상 leaf 노드에서 발생
- 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
- key 수가 여유있는 형제의 지원을 받는다.
- 1. 동생(왼쪽 형제)이 여유가 있으면
➡ 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다.
➡ 원래 그 자리에 있던 key는 나의 가 왼쪽에 둔다. - 2. 그게 아니라 형(오른쪽 형제)이 여유가 있으면
➡ 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다.
➡ 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.
- 1. 동생(왼쪽 형제)이 여유가 있으면
- 그게 불가능하면 부모의 지원을 받고 형제와 합친다.(왼쪽)
- 위를 실행 후 부모에 문제가 있다면 거기서 다시 재조정한다.
- 1. 부모가 root 노드가 아니라면
➡ 그 위치에서부터 다시 1번부터 재조정을 시작한다. - 2. 부모가 root 노드고 비어있다면
➡ 부모 노드를 삭제한다.
➡ 직전에 합쳐진 노드가 root노드가 된다.
- 1. 부모가 root 노드가 아니라면
- key 수가 여유있는 형제의 지원을 받는다.
- internal 노드 데이터 삭제
- leaf 노드에서 삭제하고 필요하면 재조정
- internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
➡ 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.
'IT > 데이터 구조' 카테고리의 다른 글
| 트리 비교 (0) | 2025.11.06 |
|---|---|
| Red-Black 트리 (0) | 2025.11.03 |
| AVL 트리 (0) | 2025.10.31 |
| 이진 탐색 트리(BST) (0) | 2025.10.31 |
| 이진(binary)트리 (0) | 2025.10.31 |