다음과 같은 조건을 모두 만족하는 B^{+}－트리에 T, W, M, E… | [7급 국가직 데이터베이스론] 23년 1회차 기출문제 상세 페이지

다음과 같은 조건을 모두 만족하는 $B^{+}$－트리에 T, W, M, E, F, G, K, C, S, D, B, L 순으로 키 값이 입력되었을 때, 루트(root)에 있는 키 값을 바르게 나열한 것은? (단, $[X_i]$는 포인터 $P_i$가 가리키는 서브트리의 모든 키 값들을 의미하고, 트리는 비어 있는(empty) 상태이며, 기호 $\equiv$는 동치를 의미한다)
○ 한 노드에 최대 네 개의 키 값을 가질 수 있다.
○ 내부노드의 구조는 $\lt P_1, K_1, \ldots, P_i, K_i, \ldots, K_{q-1}, P_q \gt$이며, $K_i$는 $i$번째 키, $P_i$는 $i$번째 서브트리를 가리키는 포인터이다.
○ $i \equiv 1$이면 $[X_1] \lt K_1$이고, $i \equiv q$이면 $K_{q-1} \le [X_q]$를 만족한다.
○ $1 \lt i \lt q$이면 $K_{i-1} \le [X_i] \lt K_i$를 만족한다.
○ 노드 분할 시 상위 노드로 올리는 값은 분할대상 키 값들 중 중간 값을 올리는 것으로 가정한다.

C, K

D, L

F, M

G, S

루트에 있는 키 값은 F, M이다.
노드당 최대 4개 키이므로 다섯 번째 키가 들어오면 분할하고, 리프 분할 시 중간 값을 상위 노드로 복사해 올리며 중간 값은 오른쪽 리프에 남는다. T, W, M, E 삽입 → [E, M, T, W]. F 삽입 시 [E, F, M, T, W]가 넘쳐 중간 값 M을 올린다: [E, F] | [M, T, W], 루트 [M].
G, K 삽입 → 왼쪽 리프 [E, F, G, K]. C 삽입 시 [C, E, F, G, K]가 넘쳐 중간 값 F를 올린다: [C, E] | [F, G, K] | [M, T, W], 루트 [F, M].
이후 S → [M, S, T, W], D와 B → [B, C, D, E], L → [F, G, K, L]로 어느 리프도 넘치지 않아 루트는 [F, M]으로 유지된다.