B+Tree

추가는 (insertion)는 항상 leaft node에 함

노드의 분할 (split), 병합 (merge) 

M : 하나의 노드가 가질 수 있는 최대 데이터 갯수

 

1) B-treed의 데이터 삽입은 상향식으로 진행됨 

B-tree의 데이터 삽입 -> 항상 리프 노드 (leaf node)에서부터 시작됨.

 

2) B-Tree 데이터 삽입 과정

1) 새로운 데이터를 삽입하기 위한 리프 노드를 탐색한다

2) 리프 노드 발견시 새로운 데이터를 추가한다

3) 새로운 데이터 추가 후 필요하다면 노드의 분할(split)과 병합(merge)이 수행된다.

 

3) 노드의 분할 (split of node)

특정 리프 노드의 현재 데이터 수가, 노드가 가질 수 있는 최대 데이터 개수가 될 때, 해당 리프 노드의 데이터들 중 중간 값을 기준으로 해당 값보다 작은 값을 왼쪽 노드로, 큰 값을 오른쪽으로 분할하여 재구성하는 과정.

 

 

 

이를 다시 이해하기 쉽게 설명하자면,

 

B+Tree 구성 요소

• Root Node (루트 노드): 트리의 최상위 노드
• Internal Nodes (내부 노드): 오직 인덱스 역할, 실제 데이터는 없음
• Leaf Nodes (리프 노드): 모든 데이터를 보관하며, 리프 노드 간 연결 포인터 존재

 

 

✅ B-Tree / B+Tree 노드 분류

구분설명예시 용어

Leaf Node	데이터를 실제로 저장하는 가장 아래층 노드	리프(leaf) 노드
Non-Leaf Node	탐색 경로 역할만 하는 노드. 자식 노드들을 가리키는 포인터를 가짐	내부 노드(internal), 루트(root) 포함

 

즉, 루트도 non-leaf의 일종이지만, 특별히 트리의 최상단 노드이기 때문에 루트 노드라고 부르는 것뿐이야.

✅ 시각적으로 보면

 

[30] ← non-leaf (루트) / \ [10,20] [40,50] ← leaf

• 여기서 [30]은 non-leaf, 그 아래 [10,20], [40,50]은 leaf
• 루트와 내부 노드를 **기능적으로 하나로 묶어서 "non-leaf"**라고 부르는 거야

✅ 용어 정리

용어의미

Leaf node	리프 노드, 자식 없음, 데이터 저장
Non-leaf node	루트 + 내부 노드 포함, 자식 있음, 탐색용 인덱스 역할
Internal node	루트를 제외한 중간 계층의 노드 (non-leaf의 하위 개념)
Root node	최상단 노드, 경우에 따라 리프일 수도 있음 (초기 상태)

 

✅ 결론

✔️ 네가 수업에서 배운 “leaf / non-leaf” 구분은 맞고,

✔️ non-leaf는 루트와 내부 노드를 모두 포함하는 상위 개념이야.

원한다면 실제 삽입/삭제 시 어떤 노드가 어떻게 동작하는지도 leaf/non-leaf 관점에서 정리해줄게!

 

 

✅ 왜 non-leaf에서는 **이동(move)**이고, leaf에서는 **복사(copy)**인가?

🔹 1. Leaf 노드에서의 분할 (B+Tree 기준)

• 리프 노드는 데이터를 실제로 저장하는 곳이기 때문에
• 리프 노드를 분할할 때 중간 키는 상위 노드에 복사만 하고,
• 리프 노드에는 그대로 유지됨
• 예: [10, 20, 30, 40] → 중간값 30

→ 리프: [10, 20], [30, 40]
→ 내부 노드에는 30을 복사해서 인덱스로 사용

 

✅ 그래서 리프 간에는 copy

 

🔹 2. Non-leaf(내부 노드 포함)에서의 분할

• 중간 키는 실제 데이터가 아니라 경로 결정용 인덱스 키
• 이 키는 자식 노드에 더 이상 남아 있으면 안 됨
• 즉, 해당 키를 부모 노드로 "이동"시키고,
    자식 노드에서는 제거해야 트리 규칙이 유지됨

✅ 그래서 non-leaf 간에는 move

📌 핵심 차이 요약

구분Leaf 노드Non-leaf 노드

중간 키 처리 방식	복사(copy)	이동(move)
이유	데이터는 리프에만 있으므로 중복 가능 (B+Tree)	경로 분기용 키이므로 자식/부모 양쪽에 있으면 안 됨
B-Tree/B+Tree 공통?	B+Tree에서 더 명확	B-Tree도 일반적으로 non-leaf는 move 취급

 

✅ 결론

📌 Non-leaf 노드의 키는 복사되는 것이 아니라 "부모로 이동"됨,

📌 Leaf 노드에서는 중간값을 "복사"해서 부모 인덱스로만 활용함.