자료구조 12강 - m원 탐색 트리와 B 트리
이진 탐색 트리를 여러 갈래로 확장한 m원 탐색 트리의 노드 구조와 탐색 원리를 익힌다. B 트리의 균형 조건과 삽입·삭제 과정, 노드 채움률을 높인 B* 트리, 순차 접근에 유리한 B+ 트리의 특징을 비교한다.
01. m원 탐색 트리의 등장 배경
이진 탐색 트리를 여러 갈래로 확장하기
이진 탐색 트리는 한 노드가 왼쪽과 오른쪽이라는 두 방향을 사용한다. 키가 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 내려가므로 검색·삽입·삭제에 편리하다. 그러나 노드 수가 많아지거나 한쪽으로 치우치면 트리 높이가 커져 탐색 경로가 길어질 수 있다.
m원 탐색 트리(m-way search tree)는 한 노드가 최대 m개의 가지를 가질 수 있도록 이진 탐색 트리를 확장한 구조이다. 한 노드에 여러 키를 정렬해 저장하고 키 사이의 범위마다 자식 포인터를 둔다. 같은 수의 키를 저장해도 한 레벨에서 더 많은 하위 범위를 나눌 수 있어 이진 트리보다 낮은 높이를 만들 수 있다.
| 구분 | 이진 탐색 트리 | m원 탐색 트리 |
|---|---|---|
| 최대 자식 수 | 2개 | m개 |
| 노드당 키 수 | 보통 1개 | 최대 m-1개 |
| 분기 기준 | 현재 키보다 작음·큼 | 여러 정렬 키가 만드는 m개 범위 |
| 목표 | 간단한 이진 탐색 | 분기 수를 늘려 트리 높이를 낮춤 |
핵심: BS 트리는 2원 탐색 트리이며, m원 탐색 트리는 노드마다 2개 이상 m개 이하의 자식 방향을 사용할 수 있는 확장형 탐색 트리이다.
02. m원 탐색 트리의 노드 구조와 탐색
키와 포인터가 번갈아 놓이는 노드
키가 n개 들어 있는 노드는 일반적으로 P0, k0, P1, k1, …, kn-1, Pn의 구조를 갖는다. 키들은 k0 < k1 < … < kn-1의 오름차순으로 저장되며, 키 n개는 n+1개의 검색 범위를 만든다.
| 포인터 | 가리키는 서브트리의 키 범위 |
|---|---|
| P0 | k0보다 작은 키 |
| Pi | ki-1보다 크고 ki보다 작은 키 |
| Pn | 마지막 키 kn-1보다 큰 키 |
탐색은 현재 노드 안의 정렬된 키들을 비교해 일치하는 키를 찾는다. 일치하면 해당 키에 연결된 레코드 주소를 반환한다. 일치하지 않으면 찾는 값이 속할 구간을 결정하고 그 구간의 포인터로 내려간다. 포인터가 NULL이면 탐색에 실패한다.
차수가 커지면 노드 내부에서 비교할 키는 늘지만 한 번 내려갈 때 더 많은 범위를 구분하므로 전체 높이가 낮아진다. 예를 들어 키가 255개일 때 4원 트리는 한 레벨마다 최대 네 갈래로 분기하여 최대 경로 길이를 크게 줄일 수 있다.
m원 탐색 트리는 자식 수의 상한만 정하고 서브트리의 균형을 특별히 강제하지 않는다. 실제 인덱스에서는 같은 차수라도 높이가 낮고 모든 잎이 같은 레벨에 있도록 제한한 B 트리를 널리 사용한다.
03. B 트리의 정의와 조건
균형을 유지하는 m원 탐색 트리
B 트리는 m원 탐색 트리에 최소 채움 조건과 동일한 잎 레벨 조건을 추가한 균형 다원 탐색 트리이다. 각 노드가 여러 키와 자식을 가져 높이를 줄이며, 디스크 접근 횟수를 줄여야 하는 인덱스 구조에 일반적으로 사용된다.
| 차수 m인 B 트리 조건 | 내용 |
|---|---|
| 최대 자식 수 | 각 노드는 최대 m개의 서브트리를 가짐 |
| 일반 내부 노드 최소 자식 수 | 루트와 잎을 제외하면 최소 ⌈m/2⌉개의 서브트리를 가짐 |
| 루트 최소 자식 수 | 트리가 잎 하나가 아니라면 최소 2개 |
| 키 수 | 자식 포인터가 k개이면 키는 k-1개 |
| 잎 레벨 | 모든 잎 노드는 같은 레벨에 위치 |
예를 들어 차수 3인 B 트리의 내부 노드는 최대 3개의 자식과 2개의 키를 갖는다. 루트와 잎이 아닌 내부 노드는 최소 ⌈3/2⌉ = 2개의 자식을 가져야 한다. 모든 잎의 레벨이 같으므로 어떤 키를 탐색하더라도 루트에서 잎까지의 경로 길이가 균일하다.
B 트리 판별: 키가 정렬되어 범위를 나누는가, 노드가 최소·최대 자식 수를 지키는가, 모든 잎이 같은 레벨인가를 함께 확인한다.
04. B 트리의 삽입
빈자리 삽입과 가득 찬 노드 분할
삽입할 위치를 찾기 위해 루트부터 키 범위를 비교하며 잎 방향으로 내려간다. 도착한 노드에 빈자리가 있으면 키를 정렬 순서에 맞춰 넣으면 끝난다. 노드가 이미 가득 찼다면 새 키를 포함한 키들을 정렬한 뒤 노드를 둘로 분리하고 중간 키를 부모 노드로 올린다.
부모에 중간 키를 올렸을 때 부모에도 빈자리가 없으면 부모 역시 분할하고 중간 키를 한 단계 더 위로 올린다. 이 과정이 루트까지 전달되어 루트가 분할되면 새로운 루트가 만들어지고 트리 높이가 1 증가한다. 즉 B 트리는 삽입 때 잎에서 루트 방향으로 분할이 전파될 수 있다.
| 상황 | 삽입 처리 |
|---|---|
| 대상 노드에 빈자리 있음 | 키를 오름차순 위치에 직접 삽입 |
| 대상 노드가 가득 참 | 키와 포인터를 두 노드로 나누고 중간 키를 부모에 삽입 |
| 부모도 가득 참 | 부모 분할을 반복하여 위쪽으로 전파 |
| 루트가 분할됨 | 중간 키로 새 루트를 만들고 높이를 1 증가 |
분할할 때 중간 키는 자식 노드에 남는 것이 아니라 부모의 구분 키로 올라간다. 나머지 작은 키와 큰 키가 각각 왼쪽·오른쪽 노드에 배치된다.
05. B 트리의 삭제와 재배열
잎 삭제와 내부 키 대체
잎 노드에서 키를 삭제한 뒤에도 최소 키 수를 만족하면 재구성이 필요 없다. 내부 노드의 키를 삭제하려면 왼쪽 서브트리의 가장 큰 키 또는 오른쪽 서브트리의 가장 작은 키처럼 적절한 기준 키로 대체한 다음, 그 기준 키가 있던 잎에서 실제 삭제를 수행한다.
키 부족을 해결하는 재분배와 결합
삭제 결과 노드의 키 수가 최소 기준보다 작아지면 형제 노드를 살핀다. 여유 키가 있는 형제가 있으면 부모의 구분 키와 형제의 경계 키를 이동해 재분배한다. 양쪽 형제도 최소 키만 갖고 있어 빌릴 수 없다면 부모의 구분 키를 내려 보내 형제와 결합한다.
| 삭제 후 상태 | 처리 |
|---|---|
| 최소 키 수 이상 | 키만 제거하고 종료 |
| 키 부족, 형제에 여유 있음 | 부모 구분 키를 거쳐 형제와 키를 재분배 |
| 키 부족, 형제도 최소 상태 | 부모 구분 키와 형제 노드를 합쳐 결합 |
| 결합으로 부모도 부족 | 같은 재배열을 위쪽으로 반복 |
루트가 마지막 키를 잃고 자식 하나만 남게 되면 그 자식을 새 루트로 삼아 트리 높이를 1 줄일 수 있다. 이처럼 B 트리는 삽입에서는 분할, 삭제에서는 재분배와 결합으로 모든 잎의 레벨과 최소 채움 조건을 유지한다.
06. B* 트리
노드 채움률을 높인 B 트리
B* 트리는 B 트리보다 노드를 더 촘촘히 사용하도록 최소 채움 조건을 강화한 구조이다. 일반 B 트리가 노드를 대략 절반 이상 채우는 데 비해 B* 트리는 노드의 약 2/3 이상이 차도록 유지하는 것을 목표로 한다. 같은 수의 키를 저장할 때 노드 수와 분할 횟수를 줄이고 트리 높이를 낮출 수 있다.
B* 트리에서는 노드가 가득 찼다고 곧바로 둘로 분할하지 않는다. 먼저 인접 형제에 공간이 있으면 키와 포인터를 재배치해 여유 공간을 활용한다. 형제도 가득 찼다면 두 노드의 키에 부모의 구분 키를 더해 세 노드로 재분배한다. 이를 2-to-3 분할이라고 볼 수 있다.
| 구분 | B 트리 | B* 트리 |
|---|---|---|
| 최소 채움 목표 | 대략 1/2 이상 | 대략 2/3 이상 |
| 노드가 가득 찬 경우 | 두 노드로 분할하고 중간 키 승격 | 형제와 먼저 재분배, 불가능하면 두 노드를 세 노드로 분할 |
| 효과 | 균형 다원 탐색 | 더 높은 공간 이용률과 적은 노드 분할 |
07. B+ 트리
인덱스와 실제 레코드 위치를 잎에 모으기
B+ 트리는 내부 노드를 탐색 경로를 안내하는 인덱스로 사용하고, 모든 검색 키와 실제 데이터의 주소를 잎 노드에 저장한다. 내부 노드의 키는 경로를 나누기 위한 구분 키이며, 검색은 반드시 잎 노드에 도달해야 완료된다.
잎 노드들은 키 순서대로 연결되는 포인터를 가진다. 한 잎의 마지막 포인터가 다음 키를 가진 잎을 가리키므로, 첫 위치를 찾은 뒤에는 키를 매번 내부 노드와 비교하지 않고 다음 잎으로 이동하면서 범위 검색과 순차 처리를 수행할 수 있다. 이런 이유로 B+ 트리는 인덱스된 순차 파일에 적합하다.
| 항목 | B 트리 | B+ 트리 |
|---|---|---|
| 실제 레코드 주소 | 내부·잎 노드의 키에서 가질 수 있음 | 잎 노드에 모아 저장 |
| 탐색 종료 | 내부 노드에서 일치하면 종료 가능 | 반드시 잎 노드까지 도달 |
| 잎 연결 | 필수 아님 | 키 순서대로 다음 잎을 가리키는 포인터 존재 |
| 강점 | 다원 균형 탐색 | 범위 검색과 순차 처리 |
B+ 트리에서 키를 삽입해 잎이 분할되면 키 순서에 따라 두 잎으로 나누고 경계 키를 부모 인덱스에 반영한다. 잎의 키를 삭제하더라도 내부 노드에 남은 같은 키가 실제 데이터를 직접 나타내는 것이 아니라 탐색용 기준값이라면 반드시 함께 삭제할 필요는 없다.
B+ 트리 암기: 모든 실제 데이터 주소는 잎에, 내부 노드는 인덱스로, 탐색은 잎에서 종료, 잎끼리는 순서대로 연결.
08. 핵심 개념 정리
m원 탐색 트리는 한 노드에 최대 m-1개 키와 m개 자식 포인터를 두어 검색 범위를 여러 구간으로 나눈다. 분기 수가 커지면 같은 키 수에서 트리 높이를 낮출 수 있지만 그 자체로 균형을 보장하지는 않는다.
B 트리는 최소 채움 조건과 모든 잎의 동일 레벨을 보장한다. 삽입 시 가득 찬 노드를 분할해 중간 키를 부모로 올리고, 삭제 후 키가 부족하면 형제 재분배 또는 결합으로 조건을 회복한다.
B* 트리는 형제 재분배와 2-to-3 분할로 약 2/3 이상의 채움률을 지향한다. B+ 트리는 실제 데이터 주소를 잎에 모으고 잎을 순서대로 연결하여 직접 탐색뿐 아니라 범위·순차 처리도 효율적으로 수행한다.
최종 암기: m원 = 최대 m개 자식 · B = 최소 절반 채움과 같은 잎 레벨 · 삽입 = 분할과 중간 키 승격 · 삭제 = 재분배 또는 결합 · B* = 약 2/3 채움 · B+ = 데이터는 잎, 잎은 순차 연결.
예상문제 20개
1. m원 탐색 트리에서 한 노드가 가질 수 있는 최대 자식 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
m원 탐색 트리는 각 노드가 최대 m개의 가지를 가질 수 있도록 정의한다.
2. 최대 m개의 자식 포인터를 가진 m원 탐색 트리 노드의 최대 키 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
n개의 정렬 키가 n+1개의 범위를 만들므로 m개 자식에는 최대 m-1개 키가 대응한다.
3. 노드의 첫 키가 k0일 때 P0가 가리키는 서브트리의 키 범위는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
P0는 첫 번째 키보다 작은 값들이 모인 가장 왼쪽 서브트리를 가리킨다.
4. m원 탐색 트리가 이진 탐색 트리보다 낮은 높이를 만들 수 있는 주된 이유는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
분기 수가 2보다 커지면 한 레벨에서 더 많은 하위 구간을 구분할 수 있다.
5. m원 탐색 트리와 달리 B 트리가 추가로 보장하는 대표적 성질은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
B 트리는 최소 채움 조건과 함께 모든 잎의 레벨을 동일하게 유지한다.
6. 차수 m인 B 트리에서 루트와 잎을 제외한 내부 노드의 최소 자식 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
일반 내부 노드는 최대 m개, 최소 m의 절반을 올림한 수의 자식을 가져야 한다.
7. B 트리에서 자식 포인터가 k개인 내부 노드의 키 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
k-1개의 키가 경계를 만들어 k개의 자식 범위를 구분한다.
8. B 트리 삽입 위치의 노드에 빈자리가 있을 때의 처리는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
빈자리가 있으면 키를 노드 내부의 오름차순 위치에 넣는 것으로 삽입이 끝난다.
9. B 트리 삽입 중 가득 찬 노드를 분할할 때 부모로 올라가는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
중간 키가 부모의 새 구분 키가 되고 작은 키와 큰 키는 두 자식 노드로 나뉜다.
10. B 트리 삽입 과정에서 루트가 분할되면?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
승격된 중간 키가 새 루트를 이루고 기존 루트의 두 부분이 자식이 된다.
11. B 트리의 내부 노드에서 키를 삭제할 때 일반적으로 대체할 수 있는 키는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
중위 선행자나 후속자 역할의 경계 키로 대체하면 탐색 순서를 유지할 수 있다.
12. B 트리 삭제 후 키가 부족하지만 형제 노드에 여유 키가 있을 때의 처리 방법은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
형제의 경계 키와 부모의 구분 키를 이동해 두 노드가 최소 키 수를 만족하도록 조정한다.
13. B 트리 삭제 후 형제 노드도 최소 키만 가져 빌릴 수 없을 때는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
재분배가 불가능하면 부족 노드, 부모 구분 키, 형제를 하나의 노드로 합친다.
14. B* 트리가 일반 B 트리보다 높이려는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
B* 트리는 노드가 약 2/3 이상 채워지도록 해 공간 이용률을 높인다.
15. B* 트리에서 가득 찬 노드에 삽입할 때 우선 시도하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
B* 트리는 즉시 분할하기 전에 형제의 여유 공간을 활용하여 높은 채움률을 유지한다.
16. B* 트리에서 대상 노드와 형제가 모두 가득 찼을 때 사용하는 대표적 분할은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
두 가득 찬 형제와 부모의 구분 키를 재배치하여 세 노드로 나누면 약 2/3 채움을 유지할 수 있다.
17. B+ 트리에서 실제 데이터의 주소가 저장되는 곳은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
B+ 트리는 모든 검색 키와 실제 레코드 주소를 잎에 모아 둔다.
18. B+ 트리의 탐색이 종료되는 위치는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
내부 키는 경로 안내용이므로 실제 레코드 주소가 있는 잎까지 내려가야 탐색이 끝난다.
19. B+ 트리가 범위 검색과 순차 처리에 유리한 이유는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
첫 잎을 찾은 뒤 다음 잎 포인터를 따라가며 연속 키를 차례로 처리할 수 있다.
20. B 트리, B* 트리, B+ 트리에 공통으로 적용되는 설명은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
세 구조는 m원 탐색과 균형 유지 원리를 공유하면서 채움률과 데이터 배치 방식이 다르다.
댓글
댓글 쓰기