Btree

인덱스 - btree 왼쪽 작은거 오른쪽 큰거

삽입,삭제 → 수정

위치찾아서 추가

삭제 → 정렬

언제 리벨런싱되는지..

Mysql은 기본적으로

MySQL(InnoDB)은 기본적으로 B+Tree 인덱스를 사용하며,

삽입·수정·삭제 시 트리 구조의 균형과 정렬 상태를 유지합니다.

삽입 시노드에 여유 공간이 있으면 정렬된 상태로 추가되지만,

노드가 가득 찬 경우 split(분할)이 발생하고 재 정렬이 이루어질 수 있습니다.

삭제 시 키가 사라지면 노드 간 병합(merge)이나 키 차용(borrow)

과정이 발생해, 구조적 재 정렬과 균형 유지가 수행 됩니다

언제?

• 노드가 가득 찼을 때 새로운 데이터를 삽입하면 오버플로우(Overflow)가 발생.
• 트리의 높이를 최소로 유지하기 위해 노드를 두 개로 나눔.

과정:

1. 중간 키를 선택해 상위 노드로 올림.
2. 중간 키 기준으로 노드를 두 개로 분할.
3. 상위 노드에 새로운 자식 연결.
4. 필요시 상위 노드도 분할 가능 → 재귀적 분할 발생.

🔄 2. 병합(Merge) — 삭제 시 발생

언제?

• 키 삭제 후 노드에 최소 키 개수 미달(Underflow) 발생.
• 형제 노드도 최소 키만 보유 중이라 차용 불가.
• 두 노드를 병합해 균형 유지.

과정:

1. 형제 노드와 현재 노드를 병합.
2. 상위 노드의 중간 키를 병합된 노드로 내림.
3. 병합으로 인해 상위 노드에 키 부족 발생 시 재귀적 병합 가능.

🔁 3. 차용(Borrow) — 삭제 시 발생

언제?

• 키 삭제 후 최소 키 개수 미달 발생.
• 형제 노드에 여유 키가 있을 때 발생.
• 형제 노드에서 하나의 키를 빌림으로써 리밸런싱 수행.

과정:

1. 형제 노드에서 가장 가까운 키를 빌림.
2. 상위 노드에서 중간 키를 내려받고, 형제 키가 상위 노드로 이동.
3. 노드 간 균형 유지.

🧨 1. 병합(Merge) — 형제 노드도 최소 상태일 때 발생

Underflow 발생 원인:

• 노드에서 키가 삭제됐는데 남은 키 개수가 최소 개수 미만.
• 형제 노드도 최소 키 개수만 보유하고 있어, 차용이 불가능한 상태.
• 이 상황에서 병합으로 해결.

예시: (3차 B-Tree — 최소 키 개수 1)

      [20]
     /    \\
 [10]     [25]   <- 두 노드 모두 최소 1개 키만 있음

• 25 삭제 → 오른쪽 노드가 Underflow 발생
• 왼쪽 형제 노드도 1개 키만 보유 → 키를 빌릴 수 없음
• 병합 수행 → 두 노드와 상위 키가 하나로 합쳐짐

[10, 20]

---

🔁 2. 차용(Borrow) — 형제 노드에 여유 키가 있을 때 발생

Underflow 발생 원인:

• 노드에서 키가 삭제돼 남은 키가 최소 개수 미만.
• 형제 노드에 여유 키가 존재 → 차용 가능.
• 형제 노드에서 하나의 키를 빌려서 Underflow 해결.

예시:

      [20]
     /    \\
 [10]     [25, 30]   <- 오른쪽 형제 노드에 2개 키(여유 있음)

• 25 삭제 → 오른쪽 노드에서 Underflow 발생
• 형제 노드에 여유 키(30) 존재 → 차용 수행
• 상위 키(20)와 형제 키가 이동해 구조적 균형 유지

      [25]
     /    \\
 [10]     [30]

---

🚩 한눈에 차이 정리:

구분 발생 원인 형제 노드 상태 해결 방법 트리 높이 변화

병합	삭제로 Underflow 발생	형제 노드도 최소 키만 보유	두 노드 병합	높이 감소 가능
차용	삭제로 Underflow 발생	형제 노드에 여유 키 있음	형제에게 키 차용	높이 유지

---

✅ 핵심 포인트:

• 병합: 형제도 키가 부족해서 합쳐야만 해결 가능.
• 차용: 형제에 여유가 있어 빌려서 해결 가능.

이 차이만 확실히 기억하면 B-Tree의 균형 유지 메커니즘을 정확히 이해한 거야.

혹시 더 궁금한 부분이 있으면 언제든 편하게 물어봐! 🌱✨

맞아! 🎯 차수(m)에 의해

최소/최대 키 개수와 자식 노드 개수가 결정된다는 게 핵심이야.

즉,차수가 커지면 최소/최대 개수도 커지고, 그에 따라 트리의 균형을 맞추는 방식이 달라지지