소개와 B-트리 기초

데이터베이스를 분류하는 세 가지 축과, 그 아래에서 실제로 데이터를 관리하는 B-Tree의 기초를 한꺼번에 살펴보자.

데이터베이스를 분류하는 축은 딱 세 가지야. 이 세 가지만 알면 어떤 DB든 왜 그렇게 설계됐는지 설명할 수 있거든.

첫 번째는 워크로드야. 짧고 빈번한 트랜잭션을 처리하는 OLTP냐, 대량 데이터를 스캔하며 집계하는 OLAP이냐. 은행 송금이냐 월별 매출 리포트냐 — 이 차이가 DB 전체 설계를 좌우하지. 두 번째는 저장 매체야. 디스크 기반이면 I/O 최소화가 핵심이고, 인메모리면 자료구조 설계가 자유로워지지만 내구성을 위해 결국 디스크도 써야 해. 세 번째는 데이터 배치야. 행 지향은 한 행을 통째로 읽을 때 유리하고 OLTP에 적합하고, 열 지향은 특정 컬럼만 스캔하는 분석 쿼리에 압도적이면서 같은 타입 데이터가 연속이라 압축률도 훨씬 높아.

이 세 축 아래에서 실제로 일하는 게 스토리지 엔진이야. DBMS는 Transport → Query Processor → Execution Engine → Storage Engine 계층으로 나뉘는데, 이 책은 맨 아래 Storage Engine에 집중하거든. 버퍼 매니저가 디스크 페이지를 캐싱하고, 트랜잭션 매니저가 ACID를 보장하고, 리커버리 매니저가 WAL로 장애를 복구하는 — 그 레벨이야. 스토리지 엔진이 관리하는 파일은 실제 레코드가 담긴 데이터 파일(힙, 해시, 정렬)과 빠른 탐색을 위한 인덱스 파일(B-Tree, LSM Tree) 두 종류고, 이 조합이 전체 성능을 결정해.

그러면 인덱스의 대표 주자인 B-Tree가 거의 모든 관계형 DB의 심장인 이유는 뭘까? 딱 하나야 — 팬아웃을 극단적으로 높여서 디스크 접근 횟수를 최소화하는 거거든.

메모리에서는 BST가 잘 돌아가잖아. O(log n)이면 충분하니까. 근데 디스크에서는 완전히 달라져. BST의 팬아웃은 2야. 백만 개 키면 높이가 약 20인데, 디스크 한 번 접근에 수 밀리초씩 걸리니까 20번이면 치명적이지. 노드가 메모리 여기저기 흩어져서 공간적 지역성도 없고. 디스크 기반 자료구조의 원칙은 명확해 — 디스크 접근 최소화, 순차 접근 활용, 노드 크기를 페이지에 맞추기. B-Tree는 이걸 전부 만족시키는 거야.

팬아웃 100이면 백만 개 키를 높이 3으로, 팬아웃 500이면 10억 개를 높이 4로 관리할 수 있어. 상위 노드는 버퍼 풀에 캐시돼 있을 확률이 높으니까 실제 디스크 접근은 1~2회 정도지. 대부분의 DB가 쓰는 건 사실 B+Tree 변형인데, 내부 노드에 데이터를 안 넣어서 팬아웃을 더 높이고, 리프끼리 형제 포인터로 연결해서 범위 스캔도 효율적이야. 균형은 삽입 시 분할, 삭제 시 병합으로 유지하는데, 이게 루트까지 전파되면 트리 높이가 변해 — B-Tree가 밑에서 위로 자라는 유일한 순간이지.

---

정리

1장 읽고 기억할 거 세 가지:

1. 워크로드(OLTP vs OLAP), 저장 매체(디스크 vs 인메모리), 데이터 배치(행 vs 열) — 이 세 축으로 모든 DB를 분류할 수 있고, 스토리지 엔진이 이 아래에서 실제로 데이터를 관리한다.
2. B-Tree는 높은 팬아웃으로 트리 높이를 극적으로 낮춰 디스크 접근을 최소화하며, B+Tree는 데이터를 리프에만 저장하고 형제 포인터로 연결해서 범위 쿼리까지 효율적이다.
3. 삽입 시 분할, 삭제 시 병합으로 균형을 유지하며, 이 구조적 변경이 루트까지 전파되면 트리 높이가 변한다.