한 노드의 수용력

차수 m이 키 수와 자식 수의 상한을 정한다

B-Tree는 한 노드 안에 여러 키와 여러 자식 포인터를 함께 저장한다. 차수는 이 노드가 얼마나 넓게 갈라질 수 있는지 정하는 기준이다.

자식 포인터: 최대 m개

자식 1
자식 2
자식 3
...
자식 m

노드 안의 키: 최대 m-1개

키 1
키 2
...
키 m-1
차수(Order, m) 한 노드가 가질 수 있는 최대 자식 수
키 개수 자식 수보다 1개 적어 최대 m-1개까지 저장
팬아웃(Fan-out) 실제로 뻗는 자식 수가 많을수록 한 번에 더 넓게 분기

같은 규칙 아래에서 노드 위치에 따라 역할이 달라진다

모든 리프는 같은 깊이에 있어 항상 균형을 유지한다
루트 노드 탐색이 시작되는 최상위 노드
최소 조건

보통 최소 2개 자식을 가진다. 단, 트리에 노드가 하나뿐이면 루트가 곧 리프다.

의미

첫 비교만으로도 탐색 범위를 크게 나누는 출발점이다.

내부 노드 루트와 리프 사이에서 범위를 계속 좁힌다
자식과 키 수

자식은 ⌈m/2⌉개 이상 m개 이하, 키는 ⌈m/2⌉-1개 이상 m-1개 이하를 가진다.

의미

정렬된 키를 기준으로 다음 하위 페이지를 선택하게 만든다.

리프 노드 탐색이 끝나는 최하위 노드
구조

자식이 없으며, 실제 찾는 키가 이 층에서 확인된다.

의미

모든 리프 깊이가 같아 어느 경로로 내려가도 탐색 비용이 일정하다.