# B+ Tree 스터디 노트

= 2025 11 29 =
오늘 배운 것:
- B+ Tree 기본 구조 (내부 노드 vs 리프 노드)
- B+ Tree 검색 및 삽입 동작 원리
- 노드가 꽉 찼을 때 발생하는 **분할(Split)** 과 **키 승격(Promote)** 과정
- 왜 데이터베이스 인덱스(특히 InnoDB)가 B+ Tree를 사용하는지

소감문: 와... 맨날 DB 인덱스는 B+ Tree 쓴다고 키워드만 외웠는데, 직접 코드를 한 줄 한 줄 살펴보니까 진짜 보통이 아니다. gemini 아니었으면 절대 여기까지 못왔을듯.
특히 삽입할 때 노드 꽉 차서 연쇄적으로 쪼개지고, 키가 부모로 올라가고, 심지어 루트까지 쪼개져서 트리 높이가 커지는 거... `printTree()`로 찍어보면서 디버깅 안 했으면 아마 평생 이해 못 했을 것 같다. 
'인덱스'라는 게 그냥 단순한 목차가 아니라 이렇게 복잡하고 효율적인 알고리즘의 집합체였다니. 이제부터 `SELECT * ...` 날릴 때 좀 더 경건한 마음을 가져야겠다.

---

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

단순 배열에 데이터 1억 개 넣고 `for`문 돌려서 찾으면? 그건 컴퓨터에 대한 학대다. 그래서 보통 트리를 쓰는데, B+ Tree는 특히 **대용량 데이터를 디스크에 저장하고 관리**하는 데 최적화된 자료구조다. 그래서 MySQL의 InnoDB 같은 DB 엔진들이 인덱스를 구현할 때 얘를 쓴다.

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

-   **데이터는 무조건 맨 아래(리프 노드)에만 있다.**
    -   중간에 있는 노드(내부 노드)들은 데이터를 찾아가기 위한 '이정표' 역할만 한다. 길만 알려줄 뿐, 실제 데이터는 안 들고 있다.
-   **리프 노드끼리 링크트리스트로 연결돼 있다.**
    -   덕분에 `WHERE id BETWEEN 100 AND 200` 같은 **범위 검색**이 미친 듯이 빨라진다. 시작점만 찾으면 그 다음부턴 옆 노드로 쭉쭉 넘어가면서 데이터를 긁어오면 되기 때문이다.
-   **트리가 항상 균형 잡혀 있다 (Balanced).**
    -   모든 리프 노드는 루트로부터의 거리가 똑같다. 그래서 어떤 데이터를 검색하든 탐색 시간이 거의 일정하게 보장된다.
-   **내부 노드의 높은 공간 효율성 (큰 Fan-out)**
    -   내부 노드는 데이터를 저장하지 않고 오직 키와 자식 포인터만 갖는다. 덕분에 같은 디스크 공간(e.g. 4KB 블록)에 더 많은 자식 포인터를 담을 수 있어 **팬아웃(Fan-out, 한 노드가 가리키는 자식 노드의 수)이 극대화**된다. 이는 트리 전체의 높이를 더 낮게 유지하여 디스크 I/O를 줄이는 데 결정적인 역할을 한다.

    keyword: fan-out 이란? [link](https://en.wikipedia.org/wiki/Fan-out)

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

B+ Tree는 크게 두 종류의 노드로 나뉜다.

### 내부 노드 (Internal Node) vs 리프 노드 (Leaf Node)

-   **내부 노드**: `isLeaf == false`
    -   **역할**: 길잡이. 데이터를 직접 갖지 않고, 자식 노드를 가리키는 포인터만 들고 있다.
    -   **구성**: `[자식0 포인터] [키1] [자식1 포인터] [키2] [자식2 포인터] ...` 이런 식이다. 키는 N개, 자식 포인터는 N+1개를 갖는다. `key1`보다 작으면 `자식0`으로, `key1`과 `key2` 사이면 `자식1`로 내려가라는 이정표다.
-   **리프 노드**: `isLeaf == true`
    -   **역할**: 실제 데이터 보관소. 우리가 찾는 모든 `(키, 값)` 쌍이 여기에 저장된다.
    -   **구성**: `[키1, 값1], [키2, 값2], ...` 그리고 맨 끝에 옆 리프 노드를 가리키는 포인터가 하나 더 있다.

### 차수 (Order)

-   `BPlusTree(int order)` 이렇게 생성할 때 넘겨주는 `order` 값은 **한 노드가 가질 수 있는 최대 자식 포인터 수**를 의미한다.
-   최대 키 개수는 `order - 1`개다. `order`가 클수록 노드 하나에 더 많은 키를 담을 수 있으므로, 트리 전체의 높이가 낮아진다. 트리가 낮다는 건, 디스크를 덜 읽어도 된다는 뜻이므로 I/O 성능에 아주 좋다.

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

검색은 그냥 루트부터 키 비교하면서 리프까지 내려가면 되니 쉽다. 진짜는 **삽입**이다.

1.  **삽입할 리프 노드를 찾는다.** (검색과 동일)
2.  해당 리프 노드에 `(키, 값)`을 넣는다.
    -   **Case 1: 자리가 있을 때**
        -   그냥 정렬 순서에 맞게 넣고 끝. 아주 평화롭다.
    -   **Case 2: 자리가 꽉 찼을 때 → 분할(Split) 발생!**
        1.  기존 데이터와 새 데이터를 합쳐서 정렬한 뒤, 정확히 반으로 나눈다.
        2.  왼쪽 절반은 원래 노드에 남기고, 오른쪽 절반은 **새로운 리프 노드**에 넣는다.
        3.  **새로 생긴 오른쪽 노드의 첫 번째 키**를 **부모 노드로 '복사'해서 올린다(Copy-up)**. 이 키는 리프 노드에도 그대로 남아있고, 부모에는 길잡이 역할로 사본이 추가되는 것이다.
        4.  만약 부모 노드도 꽉 찼다면? **부모 노드도 똑같이 분할**한다. 이 과정은 루트까지 재귀적으로 반복될 수 있다.
        5.  만약 **루트 노드까지 분할**되면, 새로운 루트가 생기고 트리의 높이가 1 증가한다.

이 분할과 승격 과정이 B+ Tree가 스스로 균형을 맞추는 핵심 원리다.

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

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

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

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

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

컴파일할 때 "unchecked or unsafe operations" 같은 경고가 뜰 수 있는데, 보통 제네릭 타입 관련 경고라 지금은 무시해도 괜찮다.

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

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

```bash
java -cp java-datastructures BPlusTree.BPlusTreeDemo
```

이렇게 하면 `BPlusTreeDemo` 클래스의 `main` 메소드가 실행되면서, B+ Tree에 데이터를 계속 삽입할 때마다 노드가 어떻게 분할되고 트리가 어떻게 성장하는지 눈으로 직접 확인할 수 있다.

---

## 5. B-Tree vs B+ Tree 핵심 비교

| 특징 | B-Tree | B+ Tree |
| --- | --- | --- |
| **데이터 저장 위치** | 모든 노드 (내부, 리프) | **리프 노드**에만 저장 |
| **내부 노드 구성** | 키 + 데이터 포인터 + 자식 포인터 | 키 + 자식 포인터 (순수한 인덱스) |
| **키 중복** | 모든 키는 유일함 | 내부 노드의 키가 리프 노드에 중복될 수 있음 |
| **분할 방식** | 가운데 키를 부모로 **이동 (Move-up)** | 키를 부모로 **복사 (Copy-up)** |
| **성능 (특정 키 검색)** | 운 좋으면 상위 레벨에서 종료 (이론상 빠를 수 있음) | 무조건 리프 레벨까지 탐색 |
| **성능 (범위 검색)** | 비효율적 (모든 노드를 순회해야 할 수 있음) | **매우 효율적** (리프 노드 간 연결 리스트로 스캔) |
| **주요 사용처** | 파일 시스템 | **데이터베이스 인덱스** |