B+Tree 데이터베이스 인덱스 정리 – B-Tree와 B+Tree 차이, 선택 이유까지 한 번에

[일반 트리 구조]

          [루트: 50]
         /          \
     [30]            [70]
    /    \          /    \
  [20]  [40]     [60]   [80]
                             ← 리프 노드(자식 없음)

[순서대로 10, 20, 30, 40, 50 삽입 시]

[10]
   \
  [20]
     \
    [30]
       \
      [40]
         \
        [50]

→ 트리가 한쪽으로 기울어져(편향)
→ 탐색 시간이 O(log N) → O(N)으로 악화
→ 사실상 선형 탐색(링크드 리스트)과 동일한 성능

[BST와 디스크 I/O의 문제]

백만 개의 데이터(2^20)에서 BST 탐색 시:
  → 최대 20번의 노드 탐색 필요
  → 각 노드가 디스크의 서로 다른 위치에 저장
  → 최대 20번의 랜덤 디스크 I/O 발생

디스크 랜덤 I/O 1회 ≈ 10ms
20번 × 10ms = 200ms → 0.2초

→ 실시간 조회가 필요한 데이터베이스에서는 치명적

✅ 모든 리프 노드는 같은 깊이(레벨)에 위치 → 균형 보장
✅ 루트를 제외한 모든 노드는 최소 ⌈M/2⌉개의 자식을 가짐
✅ 하나의 노드는 최대 M-1개의 키를 가짐
✅ 각 노드의 키는 오름차순 정렬됨
✅ 내부 노드의 키들은 자식 노드의 범위를 구분하는 경계값 역할

[3차 B-Tree – 노드당 최대 2개의 키, 최대 3개의 자식]

              [30 | 70]
             /    |    \
        [10|20] [40|60] [80|90]

→ 30보다 작으면 왼쪽 자식 탐색
→ 30~70 사이면 가운데 자식 탐색
→ 70보다 크면 오른쪽 자식 탐색

모든 리프 노드가 같은 깊이 → 균형 트리 유지

[BST vs B-Tree 디스크 I/O 비교]

데이터 100만 개 기준:

BST (이진 탐색):
  트리 높이 ≈ log₂(1,000,000) ≈ 20
  → 최대 20번 디스크 I/O

B-Tree (차수 1000 – 페이지당 1000개의 키):
  트리 높이 ≈ log₁₀₀₀(1,000,000) ≈ 2
  → 최대 2~3번 디스크 I/O

→ 디스크 접근 횟수를 20번 → 2~3번으로 대폭 감소
→ 이것이 B-Tree가 데이터베이스에 적합한 핵심 이유

[B-Tree 구조 – 내부 노드에도 데이터 존재]

         [30,data | 70,data]          ← 내부 노드에도 data 저장
        /           |          \
[10,d|20,d]   [40,d|60,d]   [80,d|90,d]   ← 리프 노드에도 data 저장

(d = data 또는 데이터 포인터)


[B+Tree 구조 – 리프 노드에만 데이터 존재]

            [30 | 70]                 ← 내부 노드: 키(인덱스)만 저장
           /    |    \
[10,d|20,d|30,d] → [40,d|60,d|70,d] → [80,d|90,d]
                                      ← 리프 노드: 실제 data 저장
                                      ← 리프 노드끼리 연결 리스트로 연결 (→)

[B-Tree에서 40 탐색]

루트 [30,data | 70,data]
  └─ 30 < 40 < 70 → 가운데 자식으로
      [40,data | 60,data]
        └─ 40 발견! data 즉시 반환
           → 2번 접근으로 완료 ✅

[B+Tree에서 40 탐색]

루트 [30 | 70]
  └─ 30 < 40 < 70 → 가운데 자식으로
      리프 [40,data | 60,data | 70,data]
        └─ 40 발견! data 반환
           → 2번 접근으로 완료 ✅

→ 단일 값 탐색 성능은 유사

-- 실무에서 매우 흔한 범위 검색 쿼리들
SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31';
SELECT * FROM products WHERE price >= 10000 AND price <= 50000;
SELECT * FROM users WHERE age >= 20 AND age <= 30;
SELECT * FROM logs WHERE created_at > '2024-06-01' ORDER BY created_at;

[B-Tree에서 40~80 범위 검색]

루트 [30 | 70]
  ↓ 40 탐색 → 리프까지 이동 → 40 발견
  ↓ 다음 값 50 탐색 → 루트부터 다시 탐색 시작!
  ↓ 60 탐색 → 루트부터 다시!
  ↓ 70 탐색 → 루트부터 다시!
  ↓ 80 탐색 → 루트부터 다시!
→ 범위 내 값 N개 → N번 트리 순회 = 매우 비효율적

[B+Tree에서 40~80 범위 검색]

루트 [30 | 70]
  ↓ 40 탐색 → 리프 노드 도달
  ↓ 리프 연결 리스트를 따라 오른쪽으로 선형 탐색
  [40,d] → [50,d] → [60,d] → [70,d] → [80,d] → 81 도달 → 종료
→ 트리 탐색 1번 + 리프 선형 탐색
→ 디스크 I/O 최소화, 속도 압도적으로 빠름 ✅

[페이지 크기 16KB 기준 비교]

B-Tree 내부 노드 (키 + 데이터 포인터 저장):
  키 1개 크기 ≈ 8byte (정수)
  데이터 포인터 ≈ 8byte
  → 노드당 키 수 ≈ 16,384 / 16 ≈ 1,024개

B+Tree 내부 노드 (키만 저장):
  키 1개 크기 ≈ 8byte
  자식 포인터 ≈ 8byte (키 하나당)
  → 노드당 키 수 ≈ 16,384 / 8 ≈ 2,048개

→ B+Tree 내부 노드에 약 2배 많은 키 저장 가능
→ 팬아웃(하나의 노드에서 뻗어나가는 자식 수) 2배 증가
→ 같은 데이터 수에서 트리 높이가 낮아짐
→ 탐색에 필요한 디스크 I/O 감소

SELECT * FROM users ORDER BY age;        -- 정렬 출력
SELECT * FROM orders GROUP BY user_id;   -- 그룹화
SELECT * FROM products;                  -- 전체 스캔(풀 스캔)

[B+Tree 순차 접근 흐름]

리프 레벨만 순서대로 스캔:

[10|20|30] → [40|50|60] → [70|80|90] → [100|110] → ...

→ 루트·내부 노드 전혀 접근하지 않음
→ 디스크 순차 읽기 → 최대 I/O 성능 활용
→ ORDER BY 처리 시 별도 정렬 없이 인덱스 스캔으로 대체 가능

[B-Tree 탐색 시간 분포]

루트에서 발견:  O(1)  → 매우 빠름 (드문 경우)
중간 노드:     O(k)  → 깊이에 따라 다름
리프 노드:    O(log N) → 가장 느림

→ 탐색 시간이 데이터 위치에 따라 불규칙

[B+Tree 탐색 시간 분포]

항상 리프까지 내려감: O(log N) → 항상 일정

→ 모든 데이터에 대해 균등한 탐색 시간 보장
→ 데이터베이스 쿼리 성능 예측 가능 → 안정적인 서비스 운영에 유리

[MySQL InnoDB 버퍼 풀 + B+Tree 캐시 효과]

메모리 (버퍼 풀):
  └─ 루트 노드 (항상 캐시)
  └─ 2레벨 내부 노드 (자주 캐시)
  └─ 자주 접근하는 리프 노드 (LRU 캐시)

디스크 I/O:
  └─ 캐시 미스 발생 시 리프 노드만 읽기

→ 99% 이상의 탐색이 1~2번 디스크 I/O로 완료 가능

[InnoDB 클러스터드 인덱스 B+Tree 구조]

내부 노드:  [PK=100 | PK=500]
           /         |         \
리프 노드:
[PK=1, name='김철수', age=25, email='kim@...']
[PK=50, name='이영희', age=30, email='lee@...']
→
[PK=100, name='박민준', age=22, email='park@...']
[PK=200, name='최수진', age=35, email='choi@...']
→
[PK=500, name='정다운', age=28, email='jung@...']

→ 기본 키 순서대로 데이터가 물리적으로 정렬되어 저장
→ 기본 키로 조회 시 리프 노드에서 바로 모든 컬럼 데이터 획득

[세컨더리 인덱스 조회 과정 – name 컬럼에 인덱스 생성 시]

① name='박민준' 검색
    ↓
② name 세컨더리 인덱스 B+Tree 탐색
    리프 노드 발견: name='박민준', PK=100
    ↓
③ PK=100으로 클러스터드 인덱스(기본 키 인덱스) 재탐색
    클러스터드 인덱스 리프에서 전체 row 데이터 반환

→ 이 과정을 "인덱스를 통한 PK 조회 후 테이블 접근" 또는 북마크 룩업(Bookmark Lookup)이라 함
→ 커버링 인덱스(Covering Index) 사용 시 ③ 단계 생략 가능 (성능 최적화)

-- 인덱스 사용 여부 확인
EXPLAIN SELECT * FROM orders
WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31';

-- 결과 예시
-- type: range     → 범위 스캔 (B+Tree 리프 연결 리스트 활용)
-- key: idx_order_date → 사용한 인덱스
-- rows: 3542      → 스캔 예상 행 수
-- Extra: Using index condition → 인덱스 컨디션 푸시다운 적용

-- 비교: 인덱스 없을 때
-- type: ALL       → 풀 테이블 스캔 (B+Tree 사용 안 함)
-- rows: 1000000   → 전체 행 스캔

-- ✅ B+Tree 인덱스가 효과적으로 사용되는 패턴
SELECT * FROM users WHERE age = 25;              -- 동등 조건
SELECT * FROM users WHERE age >= 20;             -- 범위 조건 (한쪽 개방)
SELECT * FROM users WHERE age BETWEEN 20 AND 30; -- 범위 조건 (양쪽 폐쇄)
SELECT * FROM users WHERE name LIKE '김%';       -- 전방 일치 LIKE
SELECT * FROM users ORDER BY age LIMIT 10;       -- 정렬 + LIMIT

-- ❌ B+Tree 인덱스가 사용되지 않는 패턴 (주의!)
SELECT * FROM users WHERE YEAR(created_at) = 2024; -- 컬럼에 함수 적용
SELECT * FROM users WHERE age + 1 = 26;            -- 컬럼 연산
SELECT * FROM users WHERE name LIKE '%김';          -- 후방 일치 LIKE (전체 스캔)
SELECT * FROM users WHERE age != 25;               -- 부정 조건 (경우에 따라 다름)

높은 카디널리티 (인덱스 효과적):
  user_id, email, phone_number, order_id → 거의 모든 값이 유니크

낮은 카디널리티 (인덱스 비효과적):
  gender (남/여), status (활성/비활성), is_deleted (Y/N)
  → 절반씩 나뉘므로 인덱스로 걸러지는 데이터가 적음
  → 풀 스캔이 오히려 빠를 수도 있음

-- 복합 인덱스: (last_name, first_name, age)
CREATE INDEX idx_name_age ON users(last_name, first_name, age);

-- ✅ 인덱스 활용 가능
WHERE last_name = '김'
WHERE last_name = '김' AND first_name = '철수'
WHERE last_name = '김' AND first_name = '철수' AND age = 25

-- ❌ 인덱스 활용 불가 (선두 컬럼 없음)
WHERE first_name = '철수'          -- last_name 없이 first_name만
WHERE age = 25                      -- last_name 없이 age만
WHERE first_name = '철수' AND age = 25  -- last_name 없이 중간부터

-- user_id, name, email로 구성된 복합 인덱스 존재 시
CREATE INDEX idx_cover ON users(user_id, name, email);

-- ✅ 커버링 인덱스 적용 – 인덱스만으로 모든 컬럼 반환
SELECT user_id, name, email FROM users WHERE user_id = 100;
-- EXPLAIN Extra: "Using index" → 테이블 접근 없음

-- ❌ 커버링 인덱스 미적용 – phone_number가 인덱스에 없음
SELECT user_id, name, email, phone_number FROM users WHERE user_id = 100;
-- EXPLAIN Extra: 없음 → 테이블 추가 접근 발생

Q: B-Tree와 B+Tree의 가장 큰 차이는?
A: 데이터 저장 위치와 리프 노드 연결 여부.
   B-Tree는 모든 노드에 데이터 저장.
   B+Tree는 리프 노드에만 데이터 저장하고 리프끼리 연결 리스트로 연결.

Q: 데이터베이스 인덱스가 B+Tree를 선택한 이유는?
A: ① 리프 연결 리스트로 범위 탐색 효율적 처리
   ② 내부 노드에 키만 저장해 팬아웃 증가, 트리 높이 감소
   ③ 순차 탐색 최적화 → ORDER BY 성능 향상
   ④ 모든 데이터에 균등한 O(log N) 탐색 시간 보장
   ⑤ 내부 노드 캐시 효율 향상으로 디스크 I/O 최소화

Q: InnoDB 클러스터드 인덱스와 세컨더리 인덱스의 차이는?
A: 클러스터드 인덱스는 리프 노드에 실제 row 데이터 저장.
   세컨더리 인덱스는 리프 노드에 기본 키 값만 저장 후 PK로 재조회.