# B-Tree 스터디 노트

= 2025 11 29 =
오늘 배운 것:
- B-Tree의 기본 구조와 최소 차수 `t`의 의미
- B-Tree의 검색 및 삽입 동작 원리
- 노드가 꽉 찼을 때 중간 키를 부모로 올리는 **분할(Split)** 과정
- 왜 B-Tree가 디스크 기반 스토리지에 효율적인가

소감문: B+ Tree를 먼저 보고 B-Tree를 보니 두 자료구조의 차이점이 확 와닿는다. 


B+ Tree가 모든 데이터를 리프에만 저장하는 것과 달리, B-Tree는 내부 노드에도 데이터를 저장할 수 있다는 게 가장 큰 차이점인 것 같다.

`insert` 로직을 따라가면서 `splitChild`가 어떻게 동작하는지 보는 게 정말 어려웠다. 특히 삽입 과정에서 부모로 내려가기 전에 미리 자식 노드가 꽉 찼는지 검사하고, 꽉 찼으면 **미리 분할**해버리는 방식이 인상 깊었다. 


이렇게 해야 부모 노드로 다시 올라오는 복잡한 과정(backtracking)이 필요 없어진다는 걸 깨달았다. `BTree(3)`을 기준으로 손으로 직접 그려보면서 코드를 따라가니 얼핏 읽히는 것 같기도 하다. 책 제목은 쉽게 푸는 자료구조라는데 전혀 아닌듯; 어렵다. 

처음엔 코드가 너무 복잡해 보였지만, 단계별로 따라가며 직접 그려보니 "아, 이래서 이렇게 구현했구나" 하는 순간들이 있었다.

gemini 와 함께 코드를 쓰고 읽으면서 손으로 트리를 그려보니 복잡한 개념이 생각보다 빨리 와닿았다.

- 추가 교훈: 
    - 복잡한 알고리즘은 손으로 그려가며 이해하기
    - 삽입 순서가 구조를 바꿀 수 있음을 항상 기억
    - 삭제는 대체(replace) + 재귀로 단순화
    - 모든 복잡성은 균형 유지를 위한 것임
    - 참고로 `-` 는 minus 가 아니라 dash 를 의미한다. 헷갈리지 말자.

---

## 1. B-Tree, 너 왜 쓰는 거니?

B-Tree는 B+ Tree의 원형이 되는 자료구조로, 스스로 균형을 맞추는 트리(Self-balancing tree)다. 

B-Tree 역시 **대용량 데이터를 디스크에 저장하고 효율적으로 탐색**하기 위해 설계되었다. 

트리 구조가 항상 넓고 낮게 유지되도록 설계되어 디스크 I/O 횟수를 최소화하는 것이 핵심 목표다.

내가 이해한 B-Tree의 핵심 특징은 이렇다.

-   **데이터가 모든 노드에 저장될 수 있다.**
    -   B+ Tree와 달리, B-Tree는 내부 노드(Internal Node)와 리프 노드(Leaf Node) 모두 `(키, 데이터)` 쌍을 저장할 수 있다. (이 예제 코드에서는 key만 저장하지만, 실제로는 key에 매핑된 데이터 포인터가 함께 저장된다.)
-   **모든 리프 노드는 같은 높이에 있다 (Balanced).**
    -   이 특징 덕분에 어떤 키를 검색하든 항상 비슷한 탐색 시간을 보장한다. 최악의 경우에도 예측 가능한 성능을 제공한다.
-   **하나의 노드에 많은 자식을 가질 수 있다.**
    -   노드 하나에 많은 키와 자식 포인터를 저장함으로써 트리 전체의 높이를 낮게 유지한다. 높이가 낮다는 것은 루트에서 특정 데이터까지 도달하는 경로가 짧다는 뜻이고, 이는 곧 디스크 접근 횟수가 줄어듦을 의미한다.

## 2. B-Tree 구조 파헤치기

B-Tree의 모든 노드는 기본적으로 동일한 구조를 가지며, `leaf`라는 boolean 값으로 리프 노드인지 내부 노드인지를 구분한다.

### 최소 차수 `t` (Minimum Degree)

B-Tree를 이해하는 가장 중요한 개념은 바로 최소 차수 `t`이다. `t`는 B-Tree의 구조를 결정하는 규칙의 기준이 된다. (단, 루트 노드는 예외)

-   **키의 개수**: 노드 하나는 최소 `t-1`개, 최대 `2t-1`개의 키를 가질 수 있다.
-   **자식 노드의 수**: 내부 노드는 최소 `t`개, 최대 `2t`개의 자식 포인터를 가질 수 있다.

`t`가 클수록 노드 하나에 더 많은 데이터를 담을 수 있어 트리의 높이가 낮아지고, 디스크 I/O 성능이 향상된다.

## 3. 핵심 동작 원리: 삽입(Insert)과 분할(Split)

검색은 루트부터 키를 비교하며 올바른 자식 노드로 내려가는 과정을 반복하면 되므로 비교적 간단하다. B-Tree의 진정한 핵심은 **삽입**과 **분할** 과정에 있다.

1.  **삽입할 위치를 찾아 내려간다.**
2.  단, 그냥 내려가는 게 아니라 **내려가는 경로에 꽉 찬 노드(`2t-1`개의 키를 가진 노드)가 있는지 확인**한다.
3.  만약 꽉 찬 노드를 만나면, 그 노드로 내려가기 전에 **미리 분할(Split)을 수행**한다.
    -   이 "미리 분할하는" 전략 덕분에, 삽입이 끝난 후 다시 트리 위로 올라가면서 구조를 조정할 필요가 없어진다.
4.  적절한 리프 노드에 도달하면, 키를 정렬 순서에 맞게 삽입한다.

### 분할 (Split) 과정

꽉 찬 노드 `y` (키 `2t-1`개)를 분할하는 과정은 다음과 같다.

1.  가운데 위치한 `t-1`번째 키를 기준으로 노드를 나눈다.
2.  이 가운데 키는 부모 노드 `x`로 '이동'(Move-up)**하며, 분할된 자식 노드에는 더 이상 존재하지 않는다. 즉, 자신을 희생하여 두 노드를 나누는 기준점이 되는 셈이다.
3.  가운데 키의 왼쪽 `t-1`개의 키들은 기존 노드 `y`에 그대로 남는다.
4.  가운데 키의 오른쪽 `t-1`개의 키들은 새로운 노드 `z`를 만들어 저장한다.
5.  새로 만들어진 노드 `z`는 부모 노드 `x`의 새로운 자식이 된다 (원래 노드 `y` 바로 옆에 위치).

만약 루트 노드가 꽉 차서 분할되는 경우, 새로운 루트가 생성되고 트리의 높이가 1 증가한다. 이것이 B-Tree가 스스로 성장하며 균형을 맞춰나가는 방식이다.

## 4. Java 코드로 컴파일하고 실행하기

이 프로젝트의 B-Tree 코드를 돌려보려면 컴파일과 실행, 두 단계가 필요하다.

### 1. B-Tree 파일 컴파일

`javac`는 `.java` 소스 코드를 JVM이 이해하는 `.class` 바이트코드로 바꾸는 컴파일러다. 프로젝트 루트 폴더(`csapp-code`)에서 아래 명령어를 실행하면 `BTree` 패키지 안의 모든 자바 파일이 컴파일된다.

```bash
javac java-datastructures/BTree/*.java
```

### 2. 데모 프로그램 실행

컴파일이 끝났으면 `java` 명령어로 `BTreeDemo`를 실행해볼 수 있다. 이때 `-cp`(classpath) 옵션으로 클래스 파일들이 어디서부터 시작하는지 알려줘야 한다. `java-datastructures`가 우리 패키지들의 루트 폴더 역할을 하므로, 다음과 같이 실행한다.

```bash
java -cp java-datastructures BTree.BTreeDemo
```

이렇게 하면 `BTreeDemo` 클래스의 `main` 메소드가 실행되면서, B-Tree에 데이터를 삽입하고 순회, 검색하는 결과를 눈으로 확인할 수 있다.

---

= 2025 11 29 (추가 학습) =

## 5. 삽입 순서에 따라 트리 구조가 달라진다!

B-Tree를 공부하면서 가장 신기했던 점은 **같은 데이터를 삽입하더라도 순서에 따라 트리의 최종 구조가 완전히 달라질 수 있다**는 사실이다.

### 왜 삽입 순서가 중요한가?

B-Tree는 삽입 과정에서 노드가 꽉 차면 **그 순간 분할(Split)이 발생**한다. 어떤 키가 먼저 들어오느냐에 따라:
- 언제 노드가 꽉 차는지
- 어떤 키가 중간값으로 선택되어 부모로 올라가는지
- 트리의 높이가 언제 증가하는지

가 모두 달라진다.

### 예시: [1, 2, 3, 4, 5, 6, 7] 삽입하기 (t=2)

**케이스 1: 순서대로 삽입 (1→2→3→4→5→6→7)**
```
초기: [1, 2]
3 삽입 시 꽉 참 → 2가 올라가며 분할
      [2]
     /   \
  [1]     [3]
...
최종적으로 2, 4, 6 등이 내부 노드 키가 됨
```

**케이스 2: 역순 삽입 (7→6→5→4→3→2→1)**
```
초기: [7, 6]
5 삽입 시 꽉 참 → 6이 올라가며 분할
      [6]
     /   \
  [5]     [7]
...
최종적으로 6, 4, 2 등이 내부 노드 키가 됨
```

**케이스 3: 무작위 순서 (3→1→5→7→2→6→4)**
```
완전히 다른 구조가 생성됨
```

이처럼 **삽입 순서가 트리의 구조를 결정**한다. 하지만 놀라운 점은, **어떤 순서로 삽입하든 B-Tree의 균형 속성은 항상 유지**된다는 것이다! 모든 리프 노드는 같은 레벨에 있고, 검색 성능도 보장된다.

### 쉽게푸는 자료구조 챕터 10 - 10번 문제

`BTreeInsertionAnalysis.java`를 통해 18과 16을 삽입하는 과정을 단계별로 분석해보았다.

**핵심 포인트:**
1. **Pre-emptive Split (선제적 분할)**
   - 루트가 꽉 차 있으면 내려가기 **전에** 먼저 분할
   - 자식 노드가 꽉 차 있으면 들어가기 **전에** 먼저 분할
   - 이 전략 덕분에 backtracking이 필요 없음

2. **중간 키의 역할**
   - 분할 시 중간 키(median key)는 부모로 올라감
   - 중간 키는 두 자식을 나누는 **경계선 역할**
   - 왼쪽 자식 < 중간 키 < 오른쪽 자식

3. **트리가 자라는 방식**
   - 루트가 분할될 때만 트리 높이가 증가
   - 항상 위로(upward) 자라남 (리프는 항상 같은 레벨)

## 6. 삭제(Remove) - 삽입보다 더 복잡하다

B-Tree에서 키를 삭제하는 것은 삽입보다 훨씬 복잡하다. 왜냐하면:
- 삽입은 항상 리프 노드에서 일어나지만
- 삭제는 **내부 노드**에서도 일어날 수 있기 때문이다.

### 삭제의 세 가지 케이스

**케이스 1: 리프 노드에서 삭제**
```
[1, 2, 3]에서 2 삭제 → [1, 3]
```
간단하다! 그냥 제거하면 된다. (단, 최소 키 개수 유지해야 함)

**케이스 2: 내부 노드에서 삭제 (충분한 키가 있는 경우)**
```
       [19, 22]  (t=3 기준)
      /    |    \
  [16,18] [20,21] [24,25,26]

22를 삭제하려면?
- 왼쪽 자식 [20,21]: 2개 < t(3) → 부족함 ✗
- 오른쪽 자식 [24,25,26]: 3개 ≥ t(3) → 충분함 ✓
1. Successor(24)를 찾음
2. 22를 24로 대체: [19, 24]
3. 리프 [24,25,26]에서 24를 재귀적으로 삭제: [25,26]
```

**케이스 3: 내부 노드에서 삭제 (키가 부족한 경우)**
- 양쪽 자식이 모두 최소 키 개수(t-1)만 가지고 있다면
- **병합(Merge)** 수행: 키 + 왼쪽 자식 + 오른쪽 자식 합치기
- 또는 형제 노드에서 **빌려오기(Borrow)**: Rotation 수행

### Predecessor vs Successor

내부 노드에서 키를 삭제할 때 이해해야 할 중요한 개념:

**Predecessor (선행자)**
- 삭제할 키보다 **작은 키들 중 가장 큰 키**
- 찾는 방법: 왼쪽 자식에서 시작해 계속 오른쪽으로 내려가 마지막 키
- BST의 In-order Predecessor와 같은 개념

**Successor (후행자)**
- 삭제할 키보다 **큰 키들 중 가장 작은 키**
- 찾는 방법: 오른쪽 자식에서 시작해 계속 왼쪽으로 내려가 첫 번째 키
- BST의 In-order Successor와 같은 개념

이 둘은 항상 리프 노드에 있기 때문에, 내부 노드 삭제를 리프 노드 삭제 문제로 변환할 수 있다!

### 쉽게푸는 자료구조 챕터 10: 12 번 문제 (t=3)

`BTreeRemove22Demo.java`를 통해 22를 삭제하는 과정을 상세히 분석하면서 깨달은 점:

1. **내부 노드 삭제의 핵심 아이디어**
   - 직접 삭제하지 않고 **대체(Replace) + 재귀 삭제**
   - Predecessor나 Successor로 대체하면 문제가 리프로 이동
   - 리프에서는 단순 삭제 가능
   - **중요**: 왼쪽/오른쪽 자식 중 키가 충분한(≥ t개) 쪽을 선택!

2. **언더플로우(Underflow) 방지**
   - 각 노드는 최소 t-1개의 키를 유지해야 함 (t=3이면 최소 2개)
   - 부족하면 형제에게서 빌려오기(borrow)
   - 형제도 부족하면 병합(merge)
   - 이 과정이 삭제를 복잡하게 만드는 주범!

3. **삭제 후에도 균형 유지**
   - 병합이 연쇄적으로 발생할 수 있음
   - 최악의 경우 루트까지 영향
   - 루트가 비면 트리 높이 감소
   - **실제 실행 시**: 자동 재균형화로 인해 트리 구조가 크게 변할 수 있음!

### 삽입 vs 삭제 비교

| 특징 | 삽입 (Insert) | 삭제 (Remove) |
|------|--------------|---------------|
| 시작점 | 항상 리프 노드 | 리프 또는 내부 노드 |
| 주요 연산 | Split (분할) | Merge/Borrow (병합/차용) |
| 트리 성장 | 루트 분할 시 높이 증가 | 루트 비면 높이 감소 |
| 복잡도 | 비교적 단순 | 더 복잡 (여러 케이스) |
| 전략 | Pre-emptive split | Fix on the way up |

## 7. 실습 파일 가이드

프로젝트 내 각 파일의 역할:

**기본 구현**
- `BTree.java`: B-Tree 클래스 (insert, remove, search, printTree)
- `BTreeNode.java`: 노드 클래스 (삽입/삭제 로직 포함)

**데모 및 분석**
- `BTreeDemo.java`: 기본 삽입/검색 데모
- `BTreeManualSetupDemo.java`: 수동으로 트리 구조 생성 후 삽입 테스트
- `BTreeInsertionAnalysis.java`: 삽입 과정 단계별 상세 분석 (18, 16 삽입): 10.10, 10.11 문제
- `BTreeRemove22Demo.java`: 삭제 과정 단계별 상세 분석 (22 삭제): 10.12 문제

**학습 팁:**
1. 먼저 `BTreeInsertionAnalysis.java` 실행해서 삽입 과정 이해
2. 다음 `BTreeRemove22Demo.java` 실행해서 삭제 과정 이해
3. 코드를 읽으면서 손으로 트리 그려보기
4. 다른 키 값으로 실험해보기