B-트리는 한 노드에 여러 데이터 조각을 저장해서 비싼 탐색 비용을 한 번만 지불하면 같은 노드 안에 있는 모든 값을 추출할 수 있게 해준다.

• 노드가 지역 메모리에 저장되면 그 값에 빠르게 접근할 수 있다.
• 이런 이득을 얻기 위해 노드를 처리하는 복잡성을 지불해야 한다.
• B-트리는 항상 모든 리프 노드가 동일한 깊이에 있도록 완벽하게 균형을 유지한다.

12.1 B-트리 구조

B-트리는 트라이나 쿼드 트리에서 본 개별 키를 저장하는 다중 분기 구조를 응용한다.

• 각 노드에 키를 하나 이상 저장할 필요가 있다.
• B-트리 노드는 키로 가득 차 있으면서, 키를 활용해 (하위 트리의) 여러 분할을 추적한다.
• B-트리는 여러 키를 탐색하는 비용을 줄이기 위해 이들을 한데 묶어서 탐색한다.

최상위 복합 자료 구조와 노드별 자료 구조를 나눠서 B-트리 자료 구조를 정의한다.

# 📌 BTree 구조 정의 (Definition of BTree)
# BTree는 루트 노드를 가지며, 각 노드는 최대 2*k 개의 키를 포함할 수 있음

BTree {
  BTreeNode: root  # 🌲 트리의 루트 노드
  Integer: k       # 🔢 노드당 최소 키 개수를 결정하는 매개변수 (최대 키 개수: 2*k)
}

# 📌 BTree 노드 구조 정의 (Definition of BTreeNode)
# BTreeNode는 키(keys)와 자식(children) 배열을 가지며, 리프 여부를 저장

BTreeNode {
  Integer: k                     # 🔢 최소 키 개수를 결정하는 값 (BTree와 동일)
  Integer: size                  # 📏 현재 노드에 저장된 키 개수
  Boolean: is_leaf               # 🍃 리프 노드 여부 (True이면 자식 노드 없음)
  Array of Type: keys            # 🔑 노드 내 저장된 키 배열 (크기: 최대 2*k)
  Array of BTreeNodes: children  # 🌿 자식 노드 배열 (리프 노드가 아니면 최대 2*k + 1개)
}

B-트리 구조가 더 복잡한 이유는 키와 자식을 저장하는 배열 크기가 다르기 떄문이다.

→ 인덱스 i에 있는 키를 인접한 자식 포인터들과 어떻게 매핑할지를 정의해야 한다. 주어진 인덱스 i에 대해 kes[i]에서 키에 접근할 수 있지만, 또 그 키의 앞과 뒤에 있는 노드 포인터에도 접근할 수 있어야 한다.

12.2 B-트리 탐색하기