밸런스 트리 (B-tree)

<aside> ✅

DBMS 내에서 사용하는 row_id 저장 방식

• 노드의 수가 2개 이상이므로 트리의 깊이 (depth) 는 더욱 낮아짐

• 탐색 시간이 AVL 트리보다 훨씬 빠름

• 인덱스와 row_id를 함께 저장하여, 인덱스만 찾아가면 바로 값을 추출할 수 있음 </aside>

• 한 노드 안에 여러 요소들 저장 가능 (차수 : degree)

• 일정 degree 이상의 원소가 들어오면, 중간값을 기준으로 분할

  • 이때, 중간 값은 위로 승진

• branch의 최대 개수 = 한 노드에 저장할 degree + 1

• 차수는 직접 설정 가능 (2 이상)

• 한 노드의 최대 키 개수는 노드 내부의 degree -1