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)에 의해

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

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

반응형

댓글

Designed by JB FACTORY