B-Tree (Balanced Tree) 에 대해 알아보겠습니다.

Ⅰ. B-Tree (Balanced Tree) 란?

 데이터베이스나 파일 시스템처럼 디스크에 저장된 데이터를 다룰 때, 디스크 접근(I/O)을 최소화하면서 검색·삽입·삭제를 안정적으로 빠르게 처리하는 목적으로 설계된 대용량 데이터를 빠르게 찾기 위해 만든 “균형 잡힌 다진 탐색 트리”입니다.

Ⅱ. B-Tree (Balanced Tree) 주요 특징

 ⅰ. 모든 리프(Leaf) 노드는 항상 같은 깊이(레벨)를 유지합니다.

   1)  특정 방향으로만 깊어지는 현상 방지

   2) 성능이 항상 안정적으로 유지

 ⅱ. DB 인덱스에 최적인 이유
   1) DB 인덱스는 메모리 구조가 아니라 디스크 페이지(Page) 기반 구조입니다.
   2) B-Tree는 이 특성을 정확히 겨냥해 설계되었습니다.
 ⅲ. DB 인덱스와 궁합이 좋은 이유
   1) 노드 크기를 디스크 페이지 크기에 맞게 설계 가능
   2) 한 번의 I/O로 많은 키를 읽음
   3) 다진 트리 구조 + 균형 유지
   4) 트리 높이가 낮음 → 디스크 접근 횟수 감소
   5) 키가 항상 정렬 상태 
   6) 범위 검색(BETWEEN, ≥, ≤) 가능

Ⅲ. B-Tree (Balanced Tree) 기본 구조 (노드 구성)

 ⅰ. B-Tree의 노드는 다음 두 요소로 구성됩니다.
   1) Key : 정렬된 검색 키
   2) Pointer(Ptr) : 자식 노드 또는 데이터 위치
 ⅱ. 노드 구조 예시
   [ Ptr0 | Key1 | Ptr1 | Key2 | Ptr2 | Key3 | Ptr3 ]
                 (정렬된 키)

Ⅳ. B-Tree (Balanced Tree) 차수(Order, m) 개념

 ⅰ. 차수 m = 한 노드가 가질 수 있는 최대 자식 수
 ⅱ. 키 개수는 최소 ~ 최대 범위를 가짐
 ⅲ. 루트 노드는 예외 규칙 허용 가능
 ⅳ. 노드는 절반 이상 채워진 상태 유지
 ⅴ. 트리 높이가 불필요하게 커지지 않음

Ⅴ. B-Tree(Balanced Tree) 핵심 속성

 ⅰ. 모든 리프 노드는 같은 레벨
 ⅱ. 노드는 최소 절반 이상 채워짐
 ⅲ. 키는 항상 정렬 상태
 ⅳ. 검색/삽입/삭제 시간복잡도
      → O(log n)

Ⅵ. B-Tree(Balanced Tree) 검색(Search) 흐름

 ⅰ. 예시 쿼리
   SELECT * FROM users WHERE user_id = 50;
 ⅱ. 동작 순서
  1) 루트 노드에서 키 비교
  2) 50이 속한 구간의 포인터 선택
  3) 중간 노드에서 반복
  4) 리프 노드 도달
  5) 데이터(또는 위치) 반환
 ⅲ. 구조 흐름
            [Root]
          /   |    \
     [Node] [Node] [Node]
        |
     [Leaf] → 데이터 or 데이터 위치

Ⅶ. B-Tree(Balanced Tree) 삽입(Insert) 흐름

 ⅰ. 기본 절차
   1) 삽입될 리프 노드 탐색
   2) 공간이 있으면 삽입 후 종료
   3) 공간이 없으면 노드 분할(Split) 발생
 ⅱ. 노드 분할 예시
  1) 분할 전:
    [10 | 20 | 30 | 40]
  2) 분할 후:
    [10 | 20] [30 | 40]
 3) 가운데 키(30)를 부모 노드로 승격
           [30]
          /    \
   [10|20]   [30|40]
 4) 부모도 가득 차면?
  - 연쇄 Split 발생
  - 페이지 분할 비용

Ⅷ. B-Tree(Balanced Tree) 삭제(Delete) 흐름

삭제는 후처리가 중요합니다.
 ⅰ. 절차
   1) 키 삭제
   2) 노드가 너무 비면 재조정(Rebalance)
 ⅱ. 재조정 방식
   1) Redistribution(재분배) : 형제 노드에서 키를 빌림
   2) Merge(병합) : 형제와 합치고 부모 키 조정

Ⅸ. B-Tree(Balanced Tree) vs B+Tree (Balanced Tree)

B-Tree는 개념(이론) 이름이고, B+Tree는 B-Tree 계열의 한 구현 방식입니다.
통칭(포괄 용어) 으로는 B-Tree라고 부르고, 실제 DB 구현에서는 B+Tree를 씁니다

구분	B-Tree	B+Tree
데이터 위치	여러 레벨에 분산	리프 노드에만 존재
데이터 저장	내부/리프 혼재	리프에만 저장
디스크 효율	보통	최적화
리프 연결	없음	리프 간 연결 리스트
범위 검색	가능	더 효율적
실무 사용	개념적 DB	인덱스 표준
구조	[Root: key+data]            | [Node: key+data]            | [Leaf: key+data]	[Root: key]         | [Node: key]         | [Leaf: key + data] <-> [Leaf] <-> [Leaf]