B-Tree

균형 잡힌 다진 트리, 데이터를 빠르게 찾기 위한 정렬된 트리 구조

인덱스는 데이터 베이스에서 검색 속도를 높이기 위한 자료 구조

-- 인덱스 없을 때
SELECT * FROM users WHERE name = '홍길동';
-- 100만 건 전부 확인 (O(n))

-- 인덱스 있을 때 (B-Tree)
CREATE INDEX idx_name ON users(name);
-- 로그 시간에 검색 (O(log n))

장단점

장점:

  • 검색 속도 대폭 향상(WHERE, JOIN)
  • 정렬(ORDER BY) 성능 개선

단점:

  • 쓰기 성능 저하(INSERT, UPDATE, DELETE)
  • 추가 저장 공간 필요
  • 인덱스 관리 오버헤드

일반 배열(순차 탐색)

// 배열: [1, 2, 3, 4, 5]
// 4를 찾기

int[] arr = {1, 2, 3, 4, 5};

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == 4) {  // 찾았다!
        return i;
    }
}

// 비교 횟수:
1 == 4? No
2 == 4? No
3 == 4? No
4 == 4? Yes! ← 4번 비교

→ 최악의 경우 n번 비교 = O(n)


**B-Tree(이진 탐색 방식)**

배열: [1, 2, 3, 4, 5] B-Tree 구조: [3] /
[1,2] [4,5]

4 찾기:

  1. 루트(3)과 비교: 4 > 3 → 오른쪽으로
  2. [4,5]에서 비교: 4 == 4 → 찾음!

비교 횟수: 2번 (log₂5 ≈ 2.3) → O(log n)

CREATE INDEX idx_age ON users(age);

데이터: 18, 22, 25, 28, 30, 35, 40, 45, 50

B-Tree 구성: [30] ← 전체 중간값 /
[22, 25] [40, 45] ← 각 구간의 중간값들 / | \ / |
[18] [22][28][35][40][50]


---

## **왜 중간값인가?**

중간값 선택 → 좌우 균형 균형 → 모든 경로 길이 비슷 → 검색 시간 일정 (O(log n) 보장)


---

## **노드 차수(Order)의 역할:**

B-Tree 차수 = 4 (최대 4개 키)

[10, 20, 30, 40] ← 꽉 참 ↓ 중간값 분리 (20 또는 30) [30] /
[10,20] [40] ```

데이터가 커질수록 두 방법은 차이가 난다.

일반 배열: O(n) ← n = 100만 B-Tree: O(log n) ← log₂(1000000) ≈ 20

일반 배열 (순차 탐색):

  • 운 좋으면: 1번 (첫 번째가 답)
  • 평균: 50만 번
  • 운 나쁘면: 100만 번 → O(n) = O(1,000,000)

B-Tree (인덱스):

  • 항상: 약 20번 → O(log n) = O(20)

B-Tree 활용 대표 알고리즘

이진 탐색 (필수) ⭐⭐⭐ Lower/Upper Bound (중요) ⭐⭐ 매개변수 탐색 (고급) ⭐⭐ BST (선택) ⭐

핵심 정리:

  1. 정렬 순서대로 데이터 삽입
  2. 노드가 꽉 차면 중간값을 부모로 올림
  3. 재귀적으로 반복하며 트리 확장
  4. 항상 균형 유지 (중간값 덕분)

결론: “중간값 기준 분할 + 정렬 유지 + 균형 보장”이 B-Tree의 핵심입니다! 🌳