B+ Tree 구현 & 포인터 정리

B+ Tree

Search : Log(n)
Insertion : log(n)
- Disk write 프로세스가 여러번 나타날 수 있음
Delete : log(n)
Range search : log(n + k)
- 범위 안 결과 k개 수집 (linked list 순회)

!image.png

바이너리 파일 저장이 뭔 소린지

B+ Tree를 메모리(RAM)에만 만들면, 프로그램 끄는 순간 데이터 다 날아가잖아.

바이너리 파일 저장 = 트리 구조를 하드디스크에 저장하는 것.

메모리(RAM)에 있는 트리
    [4]
   /   \
 [2]   [6]
  ↓
바이너리 파일(.bin)로 직렬화해서 디스크에 저장
→ 프로그램 꺼도 데이터 유지됨

코드에서 이 부분이야:

// 노드 구조체를 바이트로 변환해서 파일에 씀
fwrite(&node, sizeof(Node), 1, file);

“DB 인덱스 디스크 저장 방식 체득”이 왜 의미 있냐

MySQL 같은 실제 DB가 B+ Tree 인덱스를 디스크에 저장하는 방식이랑 원리가 동일해.

MySQL InnoDB
  → .ibd 파일에 B+ Tree 인덱스 저장
  → 너가 구현한 것도 .bin 파일에 B+ Tree 저장
  → 구조는 같음

즉 “파일 저장 시스템을 새로 만들었다”기보다는 “DB가 인덱스를 디스크에 저장하는 원리를 직접 구현하며 체득했다” 는 거야.

면접 질문 “바이너리 파일 저장은 왜 했나요?” 대비 답변

“메모리에만 트리를 유지하면 프로그램 종료 시 데이터가 사라지기 때문에, 실제 DB 인덱스처럼 디스크에 영속적으로 저장하는 구조를 구현했습니다. 이 과정에서 MySQL이 B+ Tree 인덱스를 파일로 직렬화해 저장하는 방식과 동일한 원리를 직접 체감할 수 있었습니다.”

ㅋㅋㅋ 걱정마 차근차근 알려줄게! 코드에 나온 것들 위주로 설명할게.

1. 포인터 ()

포인터 = 메모리 주소를 저장하는 변수야.

int a = 10;        // a라는 변수에 10 저장
int* p = &a;       // p라는 포인터에 a의 주소 저장

메모리를 집으로 비유하면:

변수 a  →  101호에 사는 사람 (값: 10)
포인터 p →  101호의 주소를 적어둔 메모지

cout << a;   // 10  (값 출력)
cout << p;   // 0x7fff... (주소 출력)
cout << *p;  // 10  (주소로 찾아가서 값 출력) ← 역참조

의 두 가지 역할 헷갈리지 마:

int* p = &a;   // 선언할 때 *  →  "나는 포인터야"
cout << *p;    // 사용할 때 *  →  "이 주소에 있는 값 꺼내줘"

2. 참조 (`&`)

참조 = 변수의 별명이야.

int a = 10;
int& ref = a;   // ref는 a의 별명

ref = 20;
cout << a;   // 20  (ref를 바꿨는데 a도 바뀜)

포인터랑 차이:

// 포인터
int* p = &a;
*p = 20;      // 역참조 해서 바꿔야 함

// 참조
int& ref = a;
ref = 20;     // 그냥 바로 바꿔도 됨, 걍 a랑 같은 애임

&의 두 가지 역할도 헷갈리지 마:

int& ref = a;   // 선언할 때 &  →  "나는 참조야"
int* p = &a;    // 사용할 때 &  →  "a의 주소 알려줘"

3. `>` 연산자

포인터로 구조체/클래스 멤버에 접근할 때 써.

// 포인터 아닐 때  →  점(.) 사용
Node node;
node.size = 3;

// 포인터일 때  →  화살표(->) 사용
Node* p = &node;
p->size = 3;    // (*p).size = 3 랑 완전히 동일

코드에서 이렇게 나오잖아:

while(!cursor->is_leaf) {
    cursor = cursor->children[i];
}

cursor가 Node<T>* 포인터니까 -> 쓰는 거야.

4. 이중 포인터 (`*`)

포인터의 포인터야. 주소의 주소.

코드에서 이게 나와:

Node<T>** children;

왜 이중 포인터냐면:

children = Node 포인터들의 배열
         = Node* 들을 담은 배열
         = Node* 의 포인터
         = Node**

그림으로 보면:

children(Node**)
    │
    ├─ children[0] (Node*)  →  [리프노드1]
    ├─ children[1] (Node*)  →  [리프노드2]
    └─ children[2] (Node*)  →  [리프노드3]

5. `new` / `delete`

C++에서 동적 메모리 할당이야. Java의 new랑 비슷한데 직접 해제해줘야 함.

// 하나 할당
Node<T>* node = new Node<T>(degree);   // 힙에 노드 생성
delete node;                            // 반드시 해제!

// 배열 할당
T* arr = new T[10];    // 크기 10짜리 배열 생성
delete[] arr;          // 배열은 delete[] 써야 함!

코드에서 이렇게 나와:

// Node 생성자 안에서
T* _item = new T[degree-1];      // 키 배열 동적 할당
this->item = _item;

Node<T>** _children = new Node<T>*[degree];  // 자식 포인터 배열 동적 할당
this->children = _children;

6. `nullptr`

포인터가 아무것도 가리키지 않는 상태야.

Node<T>* p = nullptr;   // 아무것도 없음

if(p == nullptr) {
    // 포인터가 비어있을 때 처리
}

코드에서 이렇게 씀:

// 초기화할 때
for(int i=0; i<degree; i++) _children[i] = nullptr;

// 체크할 때
if(node == nullptr) return nullptr;

// 연결 끊을 때
cursor->children[cursor->size-1] = nullptr;

7. 코드에서 실제 쓰인 패턴 정리

패턴 1: 노드 포인터 이동

Node<T>* cursor = node;   // cursor = node의 주소 복사
cursor = cursor->children[i];  // cursor가 자식 노드로 이동

cursor 자체가 바뀌는 거지, 원래 node는 안 바뀜.

패턴 2: 노드 생성

auto* Newnode = new Node<T>(this->degree);
Newnode->parent = cursor->parent;

힙에 새 노드 만들고, 포인터로 접근.

패턴 3: linked list 연결

// 리프 노드끼리 연결하는 핵심 코드
cursor->children[cursor->size] = Newnode;
// cursor의 마지막 children 포인터가 Newnode를 가리킴

패턴 4: 메모리 해제

delete[] cursor->item;      // 배열이라 []
delete[] cursor->children;  // 배열이라 []
delete cursor;              // 노드 자체는 그냥 delete

한 줄 요약

기호	이름	뜻
`int* p`	포인터 선언	p는 int의 주소를 저장
`*p`	역참조	p가 가리키는 주소의 값
`&a`	주소 연산자	a의 메모리 주소
`int& r`	참조 선언	r은 어떤 변수의 별명
`p->size`	멤버 접근	(*p).size 와 동일
`Node**`	이중 포인터	포인터의 배열
`new`	동적 할당	힙에 메모리 생성
`delete`	메모리 해제	할당한 메모리 반납
`nullptr`	널 포인터	아무것도 가리키지 않음

면접에서 포인터 관련 질문 나오면 “B+ Tree 직접 구현하면서 이중 포인터로 자식 노드 배열 관리하고, linked list 포인터로 Range Search 구현했습니다” 이렇게 연결하면 딱이야!

range_search 구현 과정에서 실제로 어려웠을 만한 포인트들 뽑아줄게. 각각 다 다른 답변 안으로 만들었어.

안 A: linked list 포인터 관리 어려움

“가장 어려웠던 부분은 리프 노드 linked list 연결을 유지하는 거였습니다. 삽입할 때 리프 노드가 분열되면 새 노드를 기존 linked list 중간에 끼워 넣어야 하는데, 포인터 연결 순서를 잘못 하면 기존 연결이 끊겨버립니다. 특히 cursor->children[cursor->size]가 다음 리프를 가리키는 포인터인데, 분열 후에 이 포인터가 새 노드를 가리키도록 재연결하면서 기존 다음 노드와의 연결도 유지해야 해서 순서가 중요했습니다. 종이에 직접 포인터 연결을 그려가며 어떤 순서로 재연결해야 끊기지 않는지 추적하면서 해결했습니다.”

꼬리질문: 구체적으로 어떤 순서로 연결했어요?

“분열 후 새 노드(Newnode)를 만들면, 기존 cursor가 가리키던 다음 노드를 먼저 Newnode에 연결하고, 그 다음에 cursor가 Newnode를 가리키도록 바꿨습니다. 순서를 반대로 하면 기존 다음 노드 주소를 잃어버리게 되거든요.”

안 B: children[size] 의미 파악 어려움

“가장 헷갈렸던 부분은 children[size]가 이중 역할을 한다는 점이었습니다. 내부 노드에서 children[size]는 마지막 자식 포인터인데, 리프 노드에서는 다음 리프를 가리키는 linked list 포인터로 쓰입니다. 처음에 이 구조를 정확히 이해하지 못해서 range_search에서 cursor = cursor->children[cursor->size]로 다음 리프로 이동하는 코드가 왜 동작하는지 이해하는 데 시간이 걸렸습니다. 실제로 삽입 코드에서 이 포인터가 어떻게 세팅되는지 추적하면서 이해했습니다.”

꼬리질문: 그 포인터가 어디서 세팅돼요?

“insert 함수에서 리프 분열 시 cursor->children[cursor->size] = Newnode로 왼쪽 노드가 새 오른쪽 노드를 가리키도록 세팅합니다. 그리고 Newnode->children[Newnode->size] = cursor->children[degree-1]로 기존에 cursor가 가리키던 다음 노드를 Newnode에 이어줍니다.”

안 C: range_search의 경계 조건 처리

“구현하면서 어려웠던 부분은 범위 탐색의 경계 조건이었습니다. BPlusTreeRangeSearch로 start가 속하는 리프를 찾았을 때, 그 리프의 첫 번째 값이 start보다 작을 수 있거든요. 예를 들어 start=3인데 찾은 리프가 [2,3]이면 2는 범위 밖이라 수집하면 안 됩니다. 처음엔 그냥 리프 전체를 수집했다가 범위 밖 값이 들어가는 버그가 생겼고, (temp >= start) && (temp <= end) 조건으로 각 키마다 범위 체크를 해야 한다는 걸 깨달았습니다.”

꼬리질문: while 루프 종료 조건은 어떻게 처리했어요?

“while 루프 조건을 temp <= end로 잡았는데, 이 temp가 for 루프 안에서 계속 갱신되는 구조입니다. 리프 노드의 마지막 값이 end를 넘는 순간 다음 루프에서 조건이 false가 되어 탈출합니다. 다만 마지막 리프에서 cursor->children[size]가 nullptr이 되는 경우를 대비해 if(cursor == nullptr) break 조건도 추가했습니다.”

안 D: B Tree vs B+ Tree 차이를 구현하며 이해

“구현하면서 가장 인상 깊었던 부분은 B Tree와 B+ Tree의 차이가 range_search 한 함수에서 극명하게 드러난다는 점이었습니다. B Tree였다면 범위 내 값을 하나씩 루트부터 탐색해야 하지만, B+ Tree는 리프 노드가 linked list로 연결되어 있어서 시작점만 찾으면 cursor = cursor->children[cursor->size] 한 줄로 다음 노드로 이동하며 O(k)로 스캔할 수 있습니다. 이 구조 덕분에 실제 DB의 범위 쿼리가 왜 효율적인지 코드 레벨에서 직접 이해하게 됐습니다.”

꼬리질문: B Tree로 range search하면 왜 느려요?

“B Tree는 모든 데이터가 내부 노드와 리프 노드 양쪽에 분산되어 있고, 리프 노드 간 연결이 없습니다. 그래서 범위 내 다음 값을 찾으려면 매번 루트부터 다시 탐색해야 해서 O(k log n)이 됩니다. B+ Tree는 리프만 스캔하면 되니까 O(log n + k)로 훨씬 빠릅니다.”

어떤 안 쓸지 선택 기준

면접관이 코드를 보면서 물어볼 때 → 안 B나 안 C가 적합해. 코드 디테일을 물어보는 거거든.

면접관이 “어떤 점이 어려웠나요?” 오픈형으로 물어볼 때 → 안 A나 안 D가 자연스러워.

면접관이 “B+ Tree를 왜 썼어요?” 로 연결할 것 같을 때 → 안 D로 시작하면 지원동기랑도 연결돼.

개인적으로는 안 B + 꼬리질문 대비가 제일 탄탄해. children[size]가 이중 역할을 한다는 걸 정확히 짚는 게 코드를 진짜로 이해했다는 증거거든!