B-트리 구현

B-Tree를 디스크에 실제로 구현하려면 바이트 레벨의 저장 포맷부터 분할·병합의 세부 전략까지, 교과서에 안 나오는 디테일을 하나하나 결정해야 해.

DB 파일은 고정 크기 페이지의 배열이야. 페이지 ID에 페이지 크기를 곱하면 오프셋이 나오니까 랜덤 접근이 쉽지. 파일 헤더에 매직 넘버, 버전, 루트 오프셋 같은 메타데이터가 들어가고, 삭제된 페이지 재사용을 위해 프리리스트도 관리해. 바이트 오더, VarInt 같은 가변 인코딩, 키 비교를 위한 순서 보존 인코딩 같은 세부 결정들이 이 파일 포맷을 구성하는 거야.

진짜 재밌는 건 페이지 안에 셀(키-값 쌍)을 어떻게 넣느냐야. 슬롯 페이지 구조에서는 앞쪽에 슬롯 배열이 앞에서 뒤로 자라고, 뒤쪽에 셀 데이터가 뒤에서 앞으로 자라거든. 둘이 만나면 꽉 찬 거야. 이 설계의 핵심은 셀을 물리적으로 재배치하지 않고도 슬롯 포인터 순서만 바꿔서 정렬을 유지할 수 있다는 거지. 현실은 가변 크기 데이터 투성이라 셀이 페이지를 넘어서면 오버플로 페이지를 써야 하는데, 추가 디스크 접근이 필요하니까 성능에 부정적이야. 그리고 디스크는 언제든 비트가 뒤집히거나 쓰기가 절반만 될 수 있으니까, 페이지마다 CRC32 체크섬으로 무결성을 검증하는 건 선택이 아니라 필수지.

이 페이지들이 모여 B-Tree 노드를 구성하면, 실전에서의 디테일이 쏟아져. 페이지 헤더에는 노드 타입, 셀 수, 프리 스페이스 오프셋, rightmost 자식 포인터 같은 메타데이터가 들어가. B+Tree에서 리프끼리 형제 링크로 연결되는 건 범위 쿼리 때 루트에서 다시 안 내려가도 되니까 결정적으로 중요하지. 노드 안에서 키를 찾을 때는 슬롯 배열이 정렬돼 있으니까 이진 탐색을 쓰는데, 슬롯 → 셀 → 키 비교로 이어지는 간접 참조 때문에 캐시 효율이 떨어질 수 있어서 키 접두사를 슬롯에 같이 저장하는 트릭도 쓰여.

분할이 루트까지 전파되면 트리 높이가 변하는 건데, 중간에 시스템이 죽으면 반쯤 분할된 상태가 돼. WAL이 필수인 이유야 — 모든 단계를 로그에 먼저 기록하고, 안전하게 디스크에 쓰인 후에야 실제 페이지를 수정하는 거지. 삭제 후 언더플로가 나면 바로 병합하기보다 형제에서 키를 빌려오는 리밸런싱을 먼저 시도하면 병합-분할이 반복되는 핑퐁을 줄일 수 있어. 대량 삽입 시에는 벌크 로딩으로 정렬 후 리프부터 채우고, 접두사 압축이나 접미사 트런케이션으로 키를 줄이면 팬아웃이 올라가서 전체 성능이 좋아지지.

---

정리

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

1. DB 파일은 고정 크기 페이지의 배열이며, 페이지 내부는 슬롯 페이지 구조로 물리적 재배치 없이 정렬 순서를 유지한다. 체크섬으로 무결성 검증은 필수다.
2. 형제 링크가 리프를 연결해서 범위 스캔을 효율화하고, 이진 탐색으로 노드 내 탐색을 최적화한다. 분할/병합은 루트까지 전파될 수 있어 WAL이 필수다.
3. 리밸런싱으로 불필요한 구조 변경을 줄이고, 벌크 로딩과 접두사 압축/접미사 트런케이션으로 팬아웃을 높여 전체 성능을 끌어올린다.