562. B-Tree 디스크 I/O 최적화 (팬아웃 차수 및 노드 크기 블록 매핑)

⚠️ 이 문서는 관계형 데이터베이스(RDBMS)의 표준 인덱스 구조인 B-Tree(Balanced Tree)가 단순히 탐색 횟수를 줄이는 수학적 자료구조를 넘어, 물리적인 하드디스크(HDD/SSD)의 '블록(Block) 읽기' 특성과 정확히 맞물려 디스크 I/O 병목을 극한으로 최소화하는 공학적 설계 원리를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 이진 탐색 트리(BST)가 자식을 2개만 가져 트리가 밑으로 엄청나게 깊어지는 반면, B-Tree는 자식을 한 번에 수백 개씩(팬아웃) 가져서 트리를 좌우로 뚱뚱하게 찌그러뜨린 고도비만(?) 트리다.
  2. 가치: 트리의 깊이(Depth)가 곧 '디스크를 읽어 들이는 횟수(디스크 I/O)'를 의미하기 때문에, 자식 수를 늘려 트리의 높이를 3~4층 수준으로 극단적으로 낮춤으로써 수억 건의 데이터도 디스크를 단 3번만 긁어서 찾아내는 기적을 만든다.
  3. 기술 체계: B-Tree의 노드 하나 크기를 운영체제의 디스크 블록 크기(통상 4KB~16KB)와 정확히 일치(매핑)시켜, 디스크 헤더가 한 번 움직일 때 노드 하나 전체를 버리는 데이터 없이 한입에 메모리로 완벽히 가져오도록 최적화되어 있다.

Ⅰ. 이진 탐색 트리(BST)가 DB에서 버림받은 이유

메모리에서는 날아다니던 알고리즘이 디스크에 내려오면 기어 다닌다.

  1. 이진 트리의 맹점 (Depth 폭발):
    • 이진 트리는 부모 1명이 자식을 딱 2명만 가진다.
    • 데이터가 100만 개면 트리의 깊이(높이)는 $\log_2(100만) \approx 20$층이 된다. 즉, 원하는 데이터를 찾으려면 노드를 20번 방문해야 한다.
  2. 디스크 I/O의 치명적 속도:
    • 메모리(RAM) 접근 속도가 나노초(ns)라면, 디스크(HDD) 접근 속도는 밀리초(ms)로 약 10만 배 느리다.
    • 이진 트리를 DB에 쓰면 디스크의 바늘(헤드)이 디스크 판을 20번 이리저리 튀어 다니며(Random Access) 읽어야 하므로 쿼리 한 번에 시스템이 뻗어버린다.

📢 섹션 요약 비유: 도서관(디스크)에서 책을 찾을 때, 한 칸의 서랍(노드)을 열었더니 쪽지 하나만 들어있고 "다음 단서는 2번 방 서랍에 있습니다"라고 적혀있어 이 방 저 방 서랍을 20번이나 열고 닫으며 뛰어다녀야 하는 미련한 보물찾기 게임입니다.

Ⅱ. B-Tree의 구조적 혁신: 팬아웃(Fan-out) 극대화

디스크를 여는 횟수를 줄이려면 한 번 열었을 때 정보를 왕창 꺼내와야 한다.

  1. 다진 트리 (M-way Tree):
    • B-Tree는 부모 1명이 자식을 2명이 아니라 수십~수백 명씩(차수, Order) 가질 수 있다. 한 노드가 거느리는 자식의 개수를 **팬아웃(Fan-out)**이라고 부른다.
  2. 높이(Height)의 극단적 압축:
    • 만약 팬아웃이 100(한 노드에 키가 99개, 자식이 100개)이라면?
    • 루트 노드 1층 = 자식 100개
    • 2층 = $100 \times 100 = 1만$ 개
    • 3층 = $1만 \times 100 = 100만$ 개
    • 100만 개의 데이터를 찾는 데 트리의 깊이가 고작 3층밖에 안 된다. 디스크 바늘이 단 3번만 움직이면 100만 건 중 하나를 정확히 콕 집어낼 수 있다. (현대 RDBMS에서는 수억 건도 4~5층 내에 끝난다.)

📢 섹션 요약 비유: 서랍 하나(노드)를 열었더니 그 안에 무려 100개의 다음 단서가 촘촘하게 빽빽이 적혀있는 거대한 책자가 들어있는 것입니다. 이 거대한 책자를 단 3번만 열어보면 100만 개의 책 위치를 다 찾아낼 수 있는 초고속 내비게이션입니다.

Ⅲ. 노드 크기와 디스크 블록(Page) 매핑의 비밀

팬아웃을 무작정 1만 개로 키우지 않는 이유는 디스크의 '물리적 규격' 때문이다.

  1. 디스크 블록(Block/Page)의 I/O 특성:
    • 하드디스크나 SSD는 데이터를 1바이트씩 쪼개서 읽지 않는다. 한 번 읽어 들일 때 무조건 4KB, 8KB, 16KB 등의 덩어리(Block/Page) 단위로 퍼 올린다. 1바이트를 요구해도 4KB 덩어리 전체를 가져온다.
  2. 완벽한 크기 매핑 (Size Mapping):
    • B-Tree의 핵심 최적화는 바로 **"노드 1개의 크기 = 디스크 1개 블록의 크기(예: 8KB)"**로 완벽하게 일치시켜 설계한다는 점이다.
    • 노드 안에 인덱스 Key와 자식 포인터를 꾹꾹 눌러 담다가 딱 8KB가 넘칠 것 같으면(팬아웃 한계 도달), 더 이상 담지 않고 노드를 둘로 쪼갠다(Node Split).
  3. 메모리(Buffer Pool)의 활용 극대화:
    • 디스크에서 8KB짜리 노드 하나를 긁어오면 버려지는 공간 하나 없이 DB의 메모리(버퍼 풀)에 쏙 들어맞게 캐싱된다.
    • 즉, 디스크 헤더가 한 번 움직일 때(1 I/O) 가장 효율적인 꽉 찬 정보(1 Node)를 한입에 삼켜 소화하는 극한의 공학적 타협점이 바로 B-Tree다.

📢 섹션 요약 비유: 공장에서 피자를 구울 때, 배달통(디스크 블록) 크기가 30cm라면 피자(B-Tree 노드)의 크기도 정확히 30cm로 맞춰 굽는 것입니다. 만약 피자가 40cm면 배달통에 안 들어가서 반으로 잘라 두 번 배달(2 I/O)해야 하고, 10cm면 공간이 남아서 버스비(디스크 탐색 비용)가 낭비되니까요.