B-트리(B-tree)

0. 오프닝: B-tree를 배우는 이유

B-tree(B-Baum)는 시험에서 이름보다 그림과 조건이 먼저 나오는 자료구조입니다. 처음 배우는 학생은 보통 'BST가 넓어진 것'이라고 말하지만, 그 표현은 절반만 맞습니다. B-tree도 search tree이긴 합니다. 그러나 한 node가 key 하나만 갖는 binary search tree가 아니라, 한 node가 여러 key를 sorted array처럼 들고 있고 그 key들이 여러 child interval을 나누는 multiway search tree입니다.

왜 굳이 이렇게 복잡하게 만들까요? Lecture 04의 동기는 block access입니다. 메모리나 디스크에서 pointer 하나를 따라갈 때마다 작은 값 하나만 읽는 것이 아니라 block/page 단위로 여러 entry를 한꺼번에 읽는 상황을 생각합니다. 그러면 node 안 비교가 조금 늘어도 tree height를 줄이는 것이 이득입니다. B-tree는 branching factor를 크게 만들어 root에서 leaf까지 내려가는 횟수를 줄입니다. 시험 답안에서는 이 block-friendly motivation을 한 문장으로 말하면 정의와 Laufzeit가 왜 그런지 자연스럽게 이어집니다.

한 문장 답: B-tree는 block access에 맞춰 node 하나에 여러 sorted keys를 담아 height를 낮춘 balanced multiway search tree입니다.

1. 선수 지식과 vocabulary map

B-tree 전에 필요한 개념은 많지 않지만, 정확해야 합니다. 첫째, BST의 subtree-wide order를 알아야 합니다. 부모 바로 아래 child만 비교하는 것이 아니라 subtree 전체가 ancestor가 만든 범위를 지켜야 합니다. B-tree에서도 같은 원리가 여러 interval로 확장됩니다. 둘째, root(Wurzel), internal node, leaf(Blatt), height(Höhe), predecessor(Vorgänger), successor(Nachfolger)를 알아야 합니다. 셋째, asymptotic notation에서 \(O(t\cdot h), \Theta(\log_{t} n)\)O(t*h), Θ(logₜ n)처럼 두 parameter가 섞인 표현을 읽을 수 있어야 합니다.

German/English term은 답안에 그대로 섞어 쓰면 좋습니다. B-Baum은 B-tree, Grad t는 minimum degree t, Knoten은 node, Aufteilen은 split, Rotieren/Verschieben은 rotate/shift, Verschmelzen은 merge입니다. Deletion에서 Vorgänger/Nachfolger는 internal key를 지울 때 올라오는 predecessor/successor입니다.

• BST invariant: subtree 전체 범위 조건
• 트리 용어: 루트(Wurzel), 노드(Knoten), 잎(Blatt), 높이(Höhe)
• 갱신 용어: 분할(Aufteilen), 회전·이동(Rotieren/Verschieben), 병합(Verschmelzen)
• 실행 시간 용어: 실행 시간(Laufzeit), 높이 h, 최소 차수(Grad) t

2. Formal definition: Grad t가 정하는 용량

강의 표기에서 B-tree는 Grad t, 즉 minimum degree t로 정의됩니다. Root가 아닌 모든 node는 최소 t-1개, 최대 2t-1개의 key를 가져야 합니다. Root는 예외입니다. 비어 있지 않은 tree의 root는 1개부터 2t-1개까지 key를 가질 수 있습니다. 이 root exception은 MC에서 매우 자주 나오는 함정입니다. '모든 node는 적어도 t-1 keys를 가진다'라고만 쓰면 root가 비어 있거나 초기 상태인 경우를 잘못 처리할 수 있습니다.

Node 내부 key들은 오름차순입니다. Internal node가 m개의 keys를 가지면 children은 m+1개입니다. 예를 들어 node [9, 40, 60]은 child 네 개를 만듭니다. 첫 child는 9보다 작은 값, 둘째 child는 9와 40 사이, 셋째 child는 40과 60 사이, 넷째 child는 60보다 큰 값을 담습니다. 중요한 말은 'child subtree 전체'입니다. child root만 interval에 맞는다고 충분하지 않습니다.

3. Equal leaf height와 height bound 직관

B-tree가 balanced라고 부르는 핵심은 모든 leaves가 같은 depth에 있다는 조건입니다. Plain BST는 sorted input을 넣으면 한 줄짜리 chain이 될 수 있지만, B-tree는 leaf level을 맞추고 node 최소 용량을 유지하므로 height가 logarithmic하게 묶입니다.

Height bound의 직관은 가장 빈약한 tree를 세는 것입니다. Height h가 커지려면 node들이 최대한 적은 keys만 가져야 합니다. Root는 최소 1 key, 그 아래 non-root node들은 최소 t-1 keys를 가진다고 보면, level이 내려갈수록 children 수가 적어도 t배씩 늘어납니다. 이 counting으로 \(n \ge 2t^{h} - 1\)n ≥ 2t^h - 1이 나오고, 따라서 \(h \le \log_{t}((n+1)/2)\)h ≤ logₜ((n+1)/2)가 됩니다. 증명 세부를 외우는 것보다, '최소 occupancy를 놓고 key 수를 아래에서 세어 height 상한을 얻는다'는 proof intuition을 말할 수 있어야 합니다.

4. Search: node 안에서 interval 하나 고르기

Search(Baum, k)는 현재 node x에서 시작합니다. 먼저 node 안 sorted keys 중 k가 들어갈 위치 i를 찾습니다. key[i]가 k와 같으면 성공입니다. 같지 않고 x가 leaf라면 실패입니다. Internal node라면 child[i]로 내려갑니다. 이때 child[i]는 k가 들어갈 수 있는 정확한 interval입니다.

한 level에서 node 내부 key를 선형으로 보면 최대 2t-1개를 검사하므로 \(O(t)\)O(t)입니다. Level 수는 h입니다. 따라서 search cost는 \(O(t\cdot h)\)O(t*h)입니다. Height bound를 넣으면 \(O(t \log_{t} n)\)O(t logₜ n)입니다. 강의가 강조하는 포인트는 Big-O가 t를 상수처럼 숨길 수 있지만 실제로 node scan factor가 있으며, B-tree의 장점은 CPU 비교 수 하나하나보다 block/page access 횟수를 줄이는 데 있다는 것입니다.

Search 답안에는 반드시 node scan \(O(t)\)O(t), height h, block-access motivation을 분리해 말하세요.

5. 삽입: 내려가기 전에 분할

Insertion(Einfügen)의 목적지는 항상 leaf입니다. 하지만 full node, 즉 2t-1 keys를 가진 node에 내려가서 새 key를 넣으면 overflow가 납니다. 강의 알고리즘은 이 상황을 피하려고 top-down으로 내려가며 full child를 미리 split(Aufteilen)합니다. Split은 가운데 median key를 parent로 올리고, 왼쪽 t-1 keys와 오른쪽 t-1 keys를 두 node로 나누는 작업입니다.

Root가 full이면 먼저 새 empty root를 만들고 old root를 child로 둔 다음 split합니다. 이때만 height가 1 증가할 수 있습니다. 그 다음에는 항상 내려갈 child가 full이 아니도록 유지하므로, leaf에 도착했을 때 key를 바로 넣을 공간이 있습니다. 시험에서 'insert하고 overflow가 생기면 돌아오며 split한다'는 방식으로 설명하면 다른 B-tree variant에는 있을 수 있어도 Lecture 04의 top-down 설명과 어긋날 수 있습니다.

6. 풀이 예제 1: Sheet08 방식의 \(t=2\)t=2삽입

\(t=2\)t=2이면 node 최대 key 수는 3입니다. 시작 상태를 root [9, 40], leaves [2,4,5], [12,15,30], [55,60,69]라고 합시다. 67을 insert하려면 root에서 40보다 크므로 오른쪽 leaf [55,60,69]로 내려가야 합니다. 그런데 이 leaf는 이미 full입니다. 따라서 내려가기 전에 split합니다. Median 60을 parent로 올리고 [55]와 [69]로 나눕니다. 이제 67은 60보다 크고 69보다 작으므로 오른쪽 leaf [69]에 들어가 [67,69]가 됩니다.

다음으로 45를 넣는다고 합시다. 이 시점 root가 [9,40,60]처럼 full이면 root split이 먼저 필요합니다. Median 40이 새 root가 되고, 왼쪽 internal은 [9], 오른쪽 internal은 [60] 쪽으로 나뉩니다. 그 뒤 45는 40보다 크고 60보다 작으므로 해당 leaf에 들어갑니다. 이 예시의 핵심은 key를 넣기 전에 full child를 발견하면 즉시 split한다는 순서입니다.

• \(t=2\)t=2: \(\max \text{keys} = 3\)max keys = 3
• [55,60,69]가 가득 참 → 중앙 키 60을 부모로 올림
• 67은 split 후 [69] 쪽에 삽입
• root full이면 먼저 root split, height 증가 가능

7. Deletion: 내려가기 전에 child를 고쳐 놓기

Deletion(Löschen)은 insertion보다 어렵습니다. 초보자는 leaf에서 지운 뒤 underflow를 고치려고 하지만, 강의 알고리즘의 중심 약속은 반대입니다. 내려갈 child가 t-1 keys뿐이면, 내려가기 전에 그 child가 적어도 t keys를 갖도록 repair합니다. 이 약속을 delete descent invariant라고 생각하면 됩니다.

Repair는 두 갈래입니다. 가까운 sibling이 t개 이상 keys를 가지고 있으면 rotate/shift(Rotieren/Verschieben)합니다. Parent separator가 내려오고, sibling의 가까운 key가 parent로 올라가며 child가 하나 보강됩니다. 양쪽 sibling도 모두 t-1 keys뿐이면 merge(Verschmelzen)합니다. Parent key 하나를 내려 child와 sibling을 합칩니다. 이렇게 하면 재귀적으로 내려간 뒤 실제 삭제가 일어날 때 underflow를 피하기 쉽습니다.

8. 내부 노드 삭제: 선행자, 후속자, 병합

삭제할 key k가 internal node에 있으면 그냥 빼면 child interval이 깨집니다. 그래서 세 case로 나눕니다. 왼쪽 child가 t개 이상 keys를 가지면 predecessor(Vorgänger), 즉 왼쪽 subtree에서 가장 큰 key를 찾아 k 자리로 올리고, predecessor를 그 subtree에서 삭제합니다. 오른쪽 child가 t개 이상이면 successor(Nachfolger), 즉 오른쪽 subtree에서 가장 작은 key를 올립니다. 둘 다 t-1 keys뿐이면 k와 두 children을 merge한 뒤, 합쳐진 node 안에서 k를 재귀적으로 삭제합니다.

이 case 구분은 시험에서 말로 설명하기 좋습니다. '왼쪽 충분하면 Vorgänger, 오른쪽 충분하면 Nachfolger, 둘 다 부족하면 Verschmelzen'이라고 외우되, 왜 그런지 interval을 보존하기 위해 바로 이전/다음 key만 parent key 자리를 대체할 수 있다고 설명하세요.

9. 풀이 예제 2: 삭제 과정을 읽는 법

Sheet08 G3류 deletion 문제를 풀 때는 매 단계에서 먼저 target이 현재 node에 있는지, 아니면 어느 child로 내려가야 하는지 봅니다. 예를 들어 \(t=3\)t=3에서 삭제하려는 key가 internal node에 있고 왼쪽 child가 충분하면 predecessor를 올리는 case입니다. 문제 해설에서 13 삭제가 predecessor 12를 올리는 모양으로 나오면, 핵심은 12가 13보다 작은 값 중 가장 크고, 왼쪽 child가 충분한 key를 가지고 있어 안전하다는 점입니다.

반대로 내려갈 child가 t-1 keys뿐이면 바로 내려가지 않습니다. Sibling에서 빌릴 수 있는지 봅니다. 빌릴 수 있으면 rotate/shift로 parent separator를 교환하고, 둘 다 부족하면 merge합니다. 시험 답안에는 최종 tree만 그리지 말고, 왜 rotate인지 merge인지 용량 조건을 한 줄씩 적어야 부분점수를 지킬 수 있습니다.

• Step 1: target key가 현재 node에 있는지 확인
• Step 2: 내려갈 child.n이 t-1인지 확인
• Step 3: \(\text{sibling}.n \ge t\)sibling.n ≥ t이면 rotate/shift
• Step 4: 둘 다 부족하면 merge
• Step 5: internal key는 predecessor/successor/merge case

10. Proof intuition: 왜 operations가 height에 묶이는가

Search, insert, delete 모두 본질적으로 root-to-leaf path 하나를 따라갑니다. Search는 각 level에서 interval 하나를 고릅니다. Insert는 내려가기 전 split을 할 수 있지만 그래도 같은 level에서 local repair를 하고 child 하나로 내려갑니다. Delete도 내려가기 전 rotate/merge repair를 하지만 역시 path 하나를 따라갑니다. 따라서 operation count는 level 수 h에 node 내부 작업 비용을 곱한 형태가 됩니다.

여기서 equal leaf height와 capacity invariant가 없으면 h를 log로 묶을 수 없습니다. B-tree correctness는 단순히 search order만이 아니라 capacity와 equal-depth invariant를 계속 보존하는 데 있습니다. Split은 overflow를 해결하면서 separator interval을 보존하고, rotate/merge는 underflow를 해결하면서 interval과 leaf depth를 보존합니다. 이 관점을 가지면 insertion/deletion 그림이 암기가 아니라 invariant maintenance로 보입니다.

증명 문장: 각 갱신은 키의 정렬 순서, 자식 구간, 용량 경계와 모든 잎의 같은 깊이를 보존합니다.

11. 반례로 확인하는 객관식 함정

첫째, 'B-tree는 binary tree이다'는 false입니다. Counterexample: \(t=2 \text{node}\)t=2 node는 1,2,3 keys를 가질 수 있고 internal node with 3 keys has 4 children입니다. 둘째, 'node 안 key만 sorted면 B-tree이다'도 false입니다. Counterexample: root [10,20]의 middle child에 25가 있으면 node 안은 정렬되어 있어도 child interval을 위반합니다. 셋째, 'root도 항상 t-1 keys 이상이어야 한다'는 root exception 때문에 부정확합니다.

넷째, 'insert는 leaf에 넣은 뒤 overflow를 고친다'는 Lecture 04 알고리즘 설명으로는 false입니다. 강의는 split while searching downward를 강조합니다. 다섯째, 'delete는 leaf에서 지운 뒤 underflow를 고친다'도 강의식 설명으로는 false입니다. 내려가기 전에 \(\text{child}.n \ge t\)child.n ≥ t가 되도록 고칩니다. 여섯째, '\(\Theta(\log_{t} n)\)Θ(logₜ n)이므로 언제나 balanced binary tree보다 빠르다'는 성급합니다. Node 내부 scan \(O(t)\)O(t)와 memory/block model을 같이 봐야 합니다.

12. 구두시험 답안 틀

60초 답안: B-tree는 Grad t를 가진 balanced multiway search tree입니다. Non-root node는 t-1..2t-1 keys, root는 예외적으로 1..2t-1 keys를 가질 수 있습니다. Internal node with m keys has m+1 children이고, child subtree 전체가 separator interval을 지켜야 합니다. 모든 leaves는 같은 height에 있으므로 \(h \le \log_{t}((n+1)/2)\)h ≤ logₜ((n+1)/2)입니다. Search는 \(O(t\cdot h)\)O(t*h), insert는 full child를 내려가기 전에 split, delete는 내려갈 child를 t keys 이상으로 repair합니다.

3분 답안: 먼저 block access 동기를 말합니다. Node 하나에 여러 keys를 담아 fanout을 키우고 height를 줄입니다. 그 다음 formal definition으로 capacity, root exception, m+1 children, equal leaf height를 말합니다. Search는 node 내부 scan 후 child interval 선택입니다. Insert는 top-down split-before-descent이고 split은 median up입니다. Delete는 \(\text{child}.n \ge t \text{invariant}\)child.n ≥ t invariant를 만들고 내려가며, internal key는 predecessor, successor, merge case로 처리합니다. 마지막으로 runtime은 path length h와 node scan \(O(t)\)O(t)의 곱이라고 정리합니다.

Deep-dive 답안: operation correctness를 invariant maintenance로 설명합니다. Split은 full node를 parent separator와 두 valid nodes로 바꿔 capacity와 interval을 보존합니다. Rotate/shift는 sibling 여유를 parent separator를 통해 옮겨 child capacity를 회복합니다. Merge는 두 minimal siblings와 parent separator를 합쳐 한 valid node를 만들고 parent key 수를 줄입니다. 모든 변화는 같은 leaf level 안에서 일어나므로 equal leaf height가 보존됩니다. 그래서 search tree order, capacity bounds, balanced height가 함께 유지됩니다.

13. 힌트가 있는 능동 회상

아래 질문은 답을 보기 전에 말로 먼저 풀어야 합니다. 힌트는 막혔을 때만 보세요.

• Q1. B-tree를 BST와 node 구조 관점에서 비교하세요. Hint: key 하나 vs 여러 sorted keys와 child intervals.
• Q2. Grad t에서 non-root node의 최소/최대 key 수는? Hint: t-1과 2t-1.
• Q3. Root exception을 정확히 말하세요. Hint: empty가 아닌 tree에서 1..2t-1.
• Q4. 키가 m개인 내부 노드에는 자식이 몇 개인가요? 힌트: 구간 수는 분리자 수보다 하나 많습니다.
• Q5. Child interval rule을 subtree-wide하게 설명하세요. Hint: child root만 보는 것이 아닙니다.
• Q6. 모든 leaves가 같은 height라는 조건이 runtime과 어떻게 연결되나요? Hint:\(h \le \log_{t}((n+1)/2).\)h ≤ logₜ((n+1)/2).
• Q7. Search cost가 왜 \(O(t\cdot h)\)O(t*h)인가요? Hint: node scan times number of levels.
• \(Q8. t=2\)Q8. t=2에서 full node는 몇 keys이며 split 결과는? Hint: 3 keys, median up, 좌우 1 key.
• Q9. Insertion에서 왜 내려가기 전에 split하나요? Hint: leaf 도착 시 공간을 보장합니다.
• Q10. Delete descent invariant를 말하세요. Hint: \(\text{child}.n \ge t \text{before} \text{descending}.\)child.n ≥ t before descending.
• \(Q11. \text{Sibling}.n \ge t\)Q11. Sibling.n ≥ t이면 deletion repair는 무엇인가요? Hint: rotate/shift with parent separator.
• Q12. Both siblings have t-1이면 무엇을 하나요? Hint: merge with parent key.
• Q13. Internal key deletion에서 predecessor를 쓰는 조건은? Hint: left child has at least t keys.
• \(Q14. \Theta(\log_{t} n)\)Q14. Θ(logₜ n)만 말하면 무엇이 빠지나요? Hint: node internal \(O(t)\)O(t) factor and block I/O model.

14. Validity checklist: 그림이 B-tree인지 판정하기

시험에서 B-tree는 직접 구현보다 validity 판정으로도 자주 나옵니다. 이때는 느낌으로 균형 있어 보인다고 판단하지 말고, 항상 같은 순서로 확인하세요. 첫째, 각 node 내부 key가 sorted인지 봅니다. 둘째, key 수 capacity를 봅니다. Non-root node가 t-1보다 적거나 2t-1보다 많으면 invalid입니다. Root는 예외이므로 root만 따로 봅니다. 셋째, internal node with m keys has m+1 children인지 확인합니다. Child pointer 수가 하나라도 맞지 않으면 search tree로 내려갈 interval 자체가 깨집니다.

넷째, child interval을 subtree-wide하게 확인합니다. Root [10,20]의 middle child root가 15라서 맞아 보여도, 그 subtree 안에 25가 있으면 invalid입니다. 이 trap은 BST path validity와 같은 사고방식입니다. Parent 바로 아래만 보지 말고 ancestor가 만든 lower/upper bound를 계속 들고 내려가야 합니다. 다섯째, 모든 leaves가 같은 depth인지 봅니다. Capacity가 모두 맞고 interval도 맞아도 leaf depth가 다르면 B-tree가 아닙니다.

• Node 내부 keys sorted?
• 루트가 아닌 노드의 용량은 t-1..2t-1이고, 루트 예외를 확인했나요?
• 키가 m개인 내부 노드의 자식은 m+1개인가요?
• 모든 자식 부분 트리가 분리자 구간을 지키나요?
• 모든 잎이 같은 깊이에 있나요?

15. B-tree와 2-3-4 tree: \(t=2\)t=2를 손으로 읽기

\(t=2\)t=2는 B-tree를 처음 손으로 그릴 때 가장 좋은 special case입니다. Non-root node는 최소 1 key, 최대 3 keys를 가집니다. 그래서 node 종류를 2-node, 3-node, 4-node처럼 부를 수 있습니다. 1 key를 가진 internal node는 children 2개, 2 keys는 children 3개, 3 keys는 children 4개입니다. 이 때문에 \(t=2 B-\text{tree}\)t=2 B-tree를 2-3-4 tree라고 연결해 생각할 수 있습니다.

이 연결은 insertion trace를 읽을 때 특히 유용합니다. 4-node, 즉 3 keys를 가진 node는 full입니다. 내려가려는 child가 4-node이면 먼저 split하고 median을 parent로 올립니다. 그러면 4-node가 두 개의 2-node와 parent separator로 바뀝니다. 시험에서 \(t=2\)t=2그림이 나오면 'max 3 keys'와 'full child split before descent'를 자동으로 체크하세요. 반대로 \(t=3\)t=3이면 max 5 keys이므로 \(t=2\)t=2습관을 그대로 적용하면 틀립니다.

16. B-tree, BST, red-black tree를 비교하는 답안

B-tree를 다른 balanced tree와 비교하라는 질문이 나오면, 단순히 'B-tree도 logarithmic'이라고 끝내지 마세요. Plain BST는 height가 input order에 따라 \(\Theta(n)\)Θ(n)까지 망가질 수 있습니다. Red-black tree(Rot-Schwarz-Baum)는 binary search tree에 color invariant를 붙여 height를 \(O(\log n)\)O(log n)으로 유지합니다. B-tree는 binary shape를 고치는 대신 node 하나를 multi-key block으로 크게 만들어 fanout을 키웁니다.

따라서 comparison axis는 세 가지입니다. 첫째, branching입니다. BST/RB tree는 binary branching이고 B-tree는 up to 2t children입니다. 둘째, memory model입니다. RB tree는 pointer-based main memory 구조로 설명하기 쉽고, B-tree는 disk/page/block index에 잘 맞습니다. 셋째, operation repair입니다. RB tree는 rotations and recoloring이 중심이고, B-tree는 split, rotate/shift, merge가 중심입니다. 이 비교는 'B-tree가 항상 더 빠르다'는 MC 문장을 반박할 때도 필요합니다.

• 일반 BST: \(O(h)\)O(h)이며 h는 \(\Theta(n)\)Θ(n)까지 커질 수 있음
• 레드-블랙 트리: 이진 균형 트리, 회전과 재색칠 사용
• B-트리: 다방향 균형 트리, 분할·병합·이동 사용
• B-트리의 동기: 블록·페이지 접근 횟수 감소

17. 풀이 예제 3: 검색 경로와 허용 구간

Root가 [20, 50]이고 children이 C0, C1, C2라고 합시다. C0에는 \(\text{key} < 20, C1\)key < 20, C1에는 \(20 < \text{key} < 50, C2\)20 < key < 50, C2에는 \(\text{key} > 50\)key > 50이 있어야 합니다. C1의 root가 [30, 40]이라면 그 children은 다시 (20,30), (30,40), (40,50) 범위로 나뉩니다. 여기서 45를 찾으면 root [20,50]에서 middle child C1로 내려가고, [30,40]에서 오른쪽 child로 내려갑니다. 이때 45는 단순히 40보다 크다는 조건만 만족하면 되는 것이 아니라, ancestor bound 때문에 50보다 작아야 합니다.

이 예시가 중요한 이유는 invalid path trap 때문입니다. 어떤 subtree 안에 55가 들어 있으면 local parent [30,40] 기준으로는 오른쪽이라 맞아 보일 수 있지만, root [20,50]의 middle interval을 위반합니다. 따라서 B-tree search path와 validity check는 항상 accumulated bounds로 생각해야 합니다.

경로 유효성 문장: 한 층 내려갈 때마다 허용 구간이 좁아지며, 아래의 키는 모든 조상 분리자가 만든 조건을 만족해야 합니다.

18. 풀이 예제 4: 삭제 복구를 말로 추적하기

Deletion trace를 그릴 때는 '지운다'보다 '내려갈 수 있게 만든다'가 먼저입니다. 예를 들어 \(t=3\)t=3이고 내려갈 child가 [8,9]처럼 2 keys만 가진다면, 이는 t-1 keys 상태입니다. 이 child로 바로 내려가서 하나를 지우면 underflow가 날 수 있습니다. 먼저 왼쪽 또는 오른쪽 sibling을 봅니다. Sibling이 3 keys 이상이면 rotate/shift가 가능합니다. Parent separator를 child 쪽으로 내리고 sibling의 가까운 key를 parent로 올려 child key 수를 3으로 만듭니다.

만약 양쪽 sibling도 모두 2 keys뿐이면 빌릴 곳이 없습니다. 이때는 parent separator 하나와 child, sibling을 merge합니다. \(t=3\)t=3에서 2 keys + separator 1개 + \(2 \text{keys} = 5 \text{keys}\)2 keys = 5 keys가 되어 \(\max 2t-1=5\)max 2t-1=5를 넘지 않습니다. 그래서 merge가 valid합니다. 이 산술을 말할 수 있으면 왜 merge가 overflow를 만들지 않는지 설명할 수 있습니다.

19. 답안 템플릿: 서술형에서 빠뜨리면 안 되는 문장

서술형 답안은 다음 순서로 쓰면 안정적입니다. 먼저 정의: 'B-tree of degree t is a balanced multiway search tree.' 그 다음 capacity: \(\text{non}-\text{루트} t-1..2t-1 \text{keys}, \text{루트} \text{exception}, \text{internal} m \text{keys} \rightarrow m+1 \text{children}.\)non-root t-1..2t-1 keys, root exception, internal m keys → m+1 children.그 다음 order: keys sorted inside node and all child subtrees respect separator intervals. 그 다음 balance: all leaves have same height. 여기까지가 validity definition입니다.

Operation 문제라면 search, insert, delete 중 무엇을 묻는지에 따라 invariant를 붙입니다. Search는 interval descent입니다. Insert는 split full child before descent입니다. Delete는 ensure child has at least t keys before descent입니다. Runtime 문제라면 \(h \le \log_{t}((n+1)/2), \text{node} \text{scan} O(t), \text{total} O(t\cdot h)\)h ≤ logₜ((n+1)/2), node scan O(t), total O(t*h)를 말합니다.

• 정의 → 용량 → 순서 → 같은 깊이의 잎
• 검색 → 구간을 따라 하강
• 삽입 → 내려가기 전에 분할
• 삭제 → 내려가기 전에 복구
• 실행 시간 → \(O(t\cdot h), h \le \log_{t}((n+1)/2)\)O(t*h), h ≤ logₜ((n+1)/2)

20. 후속 AI 학습 프롬프트

Vorlesung/04AdvancedDataStructures.pdf, Übung/AuD26_Sheet08.pdf, Übung/AuD26_Sheet08-Sol.pdf를 첨부하세요. 한국어로 설명하고 독일어·영어 핵심 용어는 괄호에 함께 표시하세요. 먼저 최소 차수(Grad) t인 B-트리를 정의해 보라고 물으세요. 이어서 용량, 루트 예외, 자식 구간, 같은 잎 높이, 높이 상한, 검색 실행 시간, \(t=2\)t=2삽입 분할, 내려가기 전 삭제 복구, 선행자·후속자 경우와 객관식 반례를 한 번에 한 문항씩 시험하세요. 정답·부분 정답·오답으로 엄격하게 채점하고, 틀렸을 때는 전체 교정을 보여 주기 전에 힌트 하나를 먼저 주세요.

21. Common misconception clinic: 왜 틀렸는지까지 말하기

오답을 고칠 때는 'false'만 말하면 약합니다. 왜 false인지 B-tree invariant와 연결해야 합니다. 'B-tree는 binary tree이다'라는 말은 branching invariant를 틀린 것입니다. B-tree node는 여러 separator를 갖고, internal node with m keys has m+1 children입니다. 따라서 binary라는 말은 \(t=2\)t=2에서도 맞지 않습니다. \(t=2\)t=2는 2-3-4 tree라서 최대 4 children까지 가능합니다.

'모든 node가 t-1 keys 이상이다'라는 말은 root exception을 빼먹은 것입니다. B-tree definition은 root와 non-root를 다르게 취급합니다. 'node 안 key가 sorted면 된다'라는 말은 order invariant를 너무 약하게 만든 것입니다. B-tree order는 node-local sorting plus subtree interval입니다. 'leaf depth가 달라도 capacity가 맞으면 된다'라는 말은 balance invariant를 빼먹은 것입니다. Equal leaf height가 없으면 height bound를 보장할 수 없습니다.

'delete는 지운 뒤 고친다'라는 말은 강의 알고리즘의 방향을 뒤집은 것입니다. Lecture 04 스타일에서는 내려가기 전에 \(\text{child}.n \ge t\)child.n ≥ t를 확보합니다. 'split은 아무 key나 올리면 된다'라는 말은 separator와 capacity 양쪽을 깨뜨립니다. Median을 올려야 왼쪽과 오른쪽이 각각 t-1 keys를 갖고 interval도 자연스럽게 나뉩니다.

• 이진 트리라는 주장 → 다방향 분기 성질을 위반
• 루트도 같은 최소 용량이라는 주장 → 루트 예외를 무시
• 노드 안 정렬만 보면 된다는 주장 → 부분 트리 구간을 무시
• 잎 깊이가 달라도 된다는 주장 → 균형 불변식을 무시
• 용량 부족 뒤에 삭제를 복구한다는 주장 → 강의 알고리즘의 순서를 뒤집음
• 아무 키나 올려 분할한다는 주장 → 중앙 분리자 논리를 위반

22. Mini proof: split이 B-tree 조건을 보존하는 이유

Full child y가 2t-1 keys를 가지고 있다고 합시다. Keys는 sorted되어 있습니다. Median key를 기준으로 왼쪽에는 t-1 keys, 오른쪽에는 t-1 keys가 남습니다. Median은 parent로 올라가 separator가 됩니다. Capacity부터 보면 왼쪽과 오른쪽 node는 non-root minimum인 t-1을 정확히 만족하고 maximum도 넘지 않습니다. Parent는 key 하나가 늘어나지만, insertion 알고리즘은 parent가 full인 상태로 내려가지 않도록 위에서 이미 처리했기 때문에 parent overflow도 피합니다.

Order를 보면 median보다 작은 keys는 왼쪽 node에, median보다 큰 keys는 오른쪽 node에 있습니다. Child pointers가 있다면 median 기준으로 함께 나뉘므로 각 subtree interval도 유지됩니다. Leaf height를 보면 split은 같은 level의 node 하나를 같은 level의 두 node로 바꾸는 작업입니다. 따라서 leaves가 갑자기 다른 depth로 내려가지 않습니다. Root split만 새 root를 만들어 height를 1 늘리지만, 모든 leaves가 동시에 한 level 아래가 되는 관점이라 equal leaf height는 유지됩니다.

이 proof intuition을 oral exam에서 말하면 좋습니다. Split은 단순한 배열 분할이 아니라 capacity, order, equal height를 동시에 보존하는 local repair입니다.

23. Mini proof: rotate/shift와 merge가 deletion을 안전하게 만드는 이유

Deletion repair의 목적은 내려갈 child가 너무 작지 않게 만드는 것입니다. Child c가 t-1 keys라면 하나를 삭제했을 때 minimum 아래로 떨어질 수 있습니다. Sibling s가 t keys 이상이면 s에는 여유 key가 하나 있습니다. Rotate/shift는 parent separator를 c로 내리고, sibling의 가장 가까운 key를 parent로 올립니다. 이렇게 하면 c는 key 하나를 얻어 t keys가 되고, sibling은 하나를 잃어도 최소 t-1 keys 이상입니다. Parent key 수는 변하지 않습니다. Interval도 유지됩니다. 왜냐하면 sibling에서 올라오는 key는 parent separator와 child interval 사이에 있는 가장 가까운 boundary key이기 때문입니다.

Sibling도 t-1 keys뿐이면 빌릴 여유가 없습니다. 이때 merge는 child t-1 keys, parent separator 1 key, sibling t-1 keys를 합칩니다. 총 key 수는 2t-1이므로 maximum에 정확히 맞습니다. Parent는 key 하나를 잃지만, root가 아닌 parent underflow는 상위 recursion에서 같은 방식으로 처리됩니다. Root가 empty가 되면 height가 줄 수 있는데, 이 경우에도 모든 leaves가 같은 depth라는 성질은 보존됩니다.

따라서 deletion repair는 임시방편이 아니라 수학적으로 capacity bound를 맞추는 local transformation입니다. 이 관점을 가지면 Sheet08 deletion trace에서 왜 어떤 단계는 rotate이고 어떤 단계는 merge인지 조건으로 설명할 수 있습니다.

24. Practice set: 짧은 응용 문제

문제 A: \(t=3\)t=3인 B-tree에서 non-root node가 가질 수 있는 key 수 범위는 무엇인가요? 답은 2..5 keys입니다. Root는 별도입니다. 문제 B: internal node [10, 30, 70]은 children을 몇 개 가져야 하나요? 답은 4 children입니다. 각 child interval은 (-inf,10), (10,30), (30,70), (70,+inf)입니다. 문제 C: root [20,50]의 middle child subtree 안에 60이 있으면 왜 invalid인가요? 60은 local node 기준으로 맞아 보일 수 있어도 ancestor interval (20,50)을 위반합니다.

문제 D: \(t=2 \text{node} [5,9,12]\)t=2 node [5,9,12]를 split하면 무엇이 parent로 올라가나요? Median 9입니다. Left는 [5], right는 [12]입니다. 문제 E: delete 중 내려갈 child가 t-1 keys이고 오른쪽 sibling이 t keys 이상이면 무엇을 먼저 하나요? Rotate/shift로 child를 보강합니다. 문제 F: 양쪽 sibling도 t-1 keys이면 무엇을 하나요? Parent separator와 merge합니다. 이때 resulting node의 key 수는 2t-1이라 valid합니다.

이 practice는 계산보다 조건 언어를 훈련하기 위한 것입니다. 답을 쓸 때마다 'capacity', 'interval', 'same leaf height', 'before descent' 중 어떤 조건을 쓰는지 표시해 보세요.

• \(t=3\)t=3일 때 루트가 아닌 노드의 용량: 키 2..5개
• \([10,30,70] \to \)[10,30,70] →자식 4개
• [20,50]의 가운데 부분 트리에는 60이 들어갈 수 없음
• \(t=2\)t=2에서 [5,9,12] 분할 → 9를 부모로 올림
• 형제에 여분 키가 있음 → 회전·이동
• 양쪽 형제가 모두 최소 용량 → 병합

25. 마지막 정리: 시험 직전 90초 압축

B-tree는 block-friendly balanced multiway search tree입니다. 한 node가 여러 sorted keys를 갖고, 그 key들이 m+1 child intervals를 만듭니다. Grad t에서 non-root node는 t-1..2t-1 keys, root는 예외적으로 1..2t-1 keys입니다. 모든 leaves는 같은 height에 있습니다. 이 세 가지, capacity, interval, equal leaves가 definition의 핵심입니다.

Search는 node 안에서 k의 위치를 찾고 child interval 하나로 내려갑니다. Cost는 \(O(t\cdot h)\)O(t*h), height bound는 \(h \le \log_{t}((n+1)/2)\)h ≤ logₜ((n+1)/2)이므로 \(O(t \log_{t} n)\)O(t logₜ n)입니다. Insertion은 leaf에 넣지만, full child를 만나면 내려가기 전에 split합니다. Split은 median up, 좌우 t-1 keys입니다. Root split은 height를 증가시킬 수 있습니다. Deletion은 내려갈 child가 t keys 이상이 되도록 먼저 repair합니다. Sibling이 충분하면 rotate/shift, 둘 다 부족하면 merge입니다. Internal key deletion은 \(\text{left} \text{child} \text{sufficient} \rightarrow \text{predecessor}, \text{right} \text{child} \text{sufficient} \rightarrow \text{successor}, \text{both} \text{minimal} \rightarrow \text{merge}\)left child sufficient → predecessor, right child sufficient → successor, both minimal → merge입니다.

MC에서 가장 위험한 문장은 'binary', 'root도 항상', 'm keys m children', 'node-local sorted이면 충분', 'leaves depth 달라도 됨', 'insert 후 split', 'delete 후 underflow repair', 'log라서 항상 더 빠름'입니다. 각 문장을 반례 하나와 함께 반박할 수 있으면 B-tree 첫 강의 목표는 달성한 것입니다.

26. 출처에 근거한 설명과 자료 한계

이 장의 course-specific 내용은 local source map에 맞춰 제한했습니다. Lecture 04 pages 114-120은 \(B-\text{Baum} \text{definition}, \text{node} \text{representation}, \text{height} \text{bound}, \text{block}-\text{storage} \text{motivation}, \text{search}, t=2\)B-Baum definition, node representation, height bound, block-storage motivation, search, t=2의 2-3-4 tree 연결, B+-tree note를 제공합니다. Pages 123-126은 insertion, splitting, root split, downward split idea를 다룹니다. Pages 127-135는 deletion, leaf deletion, rotate/shift, merge, internal deletion, one-pass delete invariant를 다룹니다. Page 136은 \(\text{search}/\text{insert}/\text{delete} \text{worst}-\text{case} \Theta(\log_{t} n)\)search/insert/delete worst-case Θ(logₜ n)와 hidden t factor를 경고합니다.

Exercise grounding은 Sheet08입니다. Sheet08 G2는 \(t=2 \text{insertion} \text{trace}\)t=2 insertion trace를, G3는 \(t=3 \text{deletion} \text{trace}\)t=3 deletion trace와 validity checks를 제공합니다. Source gap은 시각 자료입니다. 현재 text extraction만으로는 일부 tree 그림의 exact shape를 완전히 검증하기 어렵기 때문에, 실제 시험형 그림 trace는 PDF page image를 같이 보고 최종 node 배치를 확인하는 것이 가장 안전합니다.