B-Tree 구조 | Notion

🔹 B-Tree란?

✅ 균형 트리(Balanced Tree) 구조

✅ 모든 리프 노드가 같은 깊이를 가짐 → 즉, 검색 성능이 균일함

✅ 한 개의 노드에 여러 개의 키와 자식 노드를 가질 수 있음 → 한 번에 많은 데이터를 탐색 가능

✅ 디스크 I/O를 최소화하기 위해 설계됨 → 데이터베이스에서 빠른 검색이 가능

🔹 B-Tree vs. 일반 이진 탐색 트리(BST)

비교 요소	B-Tree	이진 탐색 트리 (BST)
자식 개수	한 노드가 여러 개의 자식을 가질 수 있음	노드당 최대 2개의 자식만 가짐
높이	낮음 (O(log N)) → 빠른 검색	트리가 편향되면 O(N)까지 증가 가능
균형 유지	✅ 자동으로 균형 유지	❌ 편향될 수 있음 (AVL 트리, Red-Black 트리 필요)
디스크 접근	✅ 최소화 (한 번에 많은 데이터 로드)	❌ 노드마다 디스크 접근이 많아질 가능성 있음

🔹 B-Tree 구조 예제

B-Tree에서 각 노드는 여러 개의 키를 가지며, 키를 기준으로 정렬됨.

아래는 차수(Order) = 3 인 B-Tree 예제야.

css
복사편집
        [30]
       /    \\
   [10, 20]  [40, 50]

각 노드는 최대 3 - 1 = 2개의 키를 가짐
왼쪽 서브트리: 30보다 작은 값 (10, 20)
오른쪽 서브트리: 30보다 큰 값 (40, 50)

🔹 B-Tree 동작 방식

✅ 1. 검색 (O(log N))

루트 노드부터 시작해서 키 값을 비교하며 내려감