B-Tree와 B+Tree

1단계: 적절한 리프 노드 찾기 (루트부터 탐색)
2단계: 리프에 키 삽입 (정렬 순서 유지)
3단계-A: 공간이 있으면 완료
3단계-B: 공간이 없으면 리프 분할 (Split)

리프 분할
  * 키를 반으로 나누어 두 리프로 분리
  * 오른쪽 리프의 첫 키를 부모에 복사 (Copy-up)
  * 부모도 꽉 차면 부모도 분할 (이때는 Push-up)

내부 노드 분할
  * 키를 반으로 나누고 중간 키를 부모로 올림 (Push-up)
  * 리프 분할은 Copy-up, 내부 분할은 Push-up

실제 DBMS에서는 fill factor, page split 정책, redo/undo 로그, latch/lock, 동시성 제어가 함께 개입합니다. Copy-up/Push-up은 개념 설명용 모델이며, 실제 페이지 분할 세부 동작은 저장 엔진마다 다를 수 있습니다.

Oracle
  * 문서상 B-tree index
  * 인덱스 블록 크기: DB_BLOCK_SIZE
  * 일반 인덱스 엔트리는 키와 ROWID를 저장
  * 높이 확인: SELECT blevel FROM dba_indexes WHERE ...
  * blevel=0이면 루트만, blevel=2이면 높이 3

MySQL InnoDB
  * 페이지 크기: innodb_page_size (기본 16KB)
  * 클러스터드 인덱스: 기본 키 B+Tree 리프에 전체 행 저장
  * 세컨더리 인덱스: 리프에 보조 키와 기본 키 컬럼 저장
  * 보조 인덱스 조회 후 기본 키로 클러스터드 인덱스를 다시 탐색

PostgreSQL
  * 블록 크기: 8KB (기본)
  * 문서상 B-tree access method, 구현은 Lehman-Yao 계열
  * 리프 엔트리는 heap tuple 위치인 TID를 가리킴
  * 동시성 제어 최적화: 형제 포인터 + 하이 키(High Key)

SQL Server
  * clustered index 리프에는 데이터 행 저장
  * nonclustered index 리프에는 row locator 저장
  * row locator는 heap RID 또는 clustered key

SQLite
  * rowid table은 rowid B-tree를 중심으로 저장
  * WITHOUT ROWID table은 primary key B-tree로 저장

-- Oracle: B-Tree 높이 확인
SELECT index_name, blevel, leaf_blocks, num_rows
FROM user_indexes
WHERE table_name = 'PRODUCTS';
-- blevel + 1 = B-Tree 높이

-- MySQL: 페이지 통계 (높이를 직접 보여주지는 않음)
SELECT stat_name, stat_value
FROM mysql.innodb_index_stats
WHERE database_name = 'shop'
  AND table_name = 'products'
  AND stat_name IN ('size', 'n_leaf_pages');

-- Memory 엔진은 Hash 인덱스가 기본
CREATE TABLE sessions (
    session_id VARCHAR(64),
    user_id INT,
    data TEXT,
    INDEX USING HASH (session_id)
) ENGINE = MEMORY;

-- InnoDB Adaptive Hash Index
-- 자주 접근되는 인덱스 페이지를 자동으로 해시 인덱스로 구성
-- 사용자가 직접 만드는 Hash Index가 아니라 InnoDB 내부 최적화이며 설정으로 끌 수 있음
SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';

문제: 차수 200인 B+Tree, 리프 노드당 최대 100개 레코드 저장
      총 5000만 건의 데이터를 저장하려면 최소 높이는?

풀이
  높이 3: 200 × 200 × 100 = 4,000,000건 (부족)
  높이 4: 200 × 200 × 200 × 100 = 800,000,000건 (충분)
  
  답: 높이 4
  단, 실제 I/O는 캐시된 루트/브랜치 페이지와 테이블 행 접근 여부에 따라 달라짐

문제: 다음 중 B+Tree의 특성이 아닌 것은?
  A. 모든 리프 노드의 깊이가 같다
  B. 내부 노드에도 데이터가 저장된다 ← 정답!
  C. 리프 노드끼리 연결 리스트로 연결된다
  D. 범위 검색에 효율적이다

해설: B+Tree에서 실제 행으로 이어지는 위치 정보나 행 데이터는 리프 노드 중심에 저장됩니다.
  내부 노드는 검색을 위한 라우팅 키와 자식 포인터 중심으로 구성됩니다.
  B는 B-Tree의 특성입니다.