다음과 같이 나열된 순서로 키가 삽입되어 B+-트리가 구성되었을 때 루… | [7급 국가직 데이터베이스론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 데이터베이스론] 07년 1회차
다음과 같이 나열된 순서로 키가 삽입되어 B+-트리가 구성되었을 때 루트노드에 존재하는 키 값은? (단, 차수는 3이다)삽입순서 : 13, 8, 4, 11, 6, 19, 16, 10
1
8
2
11
3
13
4
19
해설
차례로 삽입하면 최종 루트노드에는 키 8만 남는다.
차수 3이므로 한 노드의 키는 최대 2개이고, 3개가 되면 분할한다. 리프 분할 시 왼쪽에 두 키를 남기고 그 최댓값을 부모로 복사하며, 내부 노드 분할 시 가운데 키를 부모로 올린다.
13, 8, 4 삽입: [4, 8 | 13]으로 분할, 루트 [8].
11 삽입: 리프 [11, 13].
6 삽입: [4, 6, 8]이 [4, 6 | 8]로 분할, 루트 [6, 8].
19 삽입: [11, 13, 19]가 [11, 13 | 19]로 분할되어 13이 올라가고, 넘친 루트 [6, 8, 13]의 가운데 키 8이 새 루트가 된다.
16, 10 삽입: 리프 [16, 19]와 [10, 11 | 13] 분할로 하위 내부 노드만 [11, 13]이 되고 루트 [8]은 그대로이다.
- 11: 마지막 분할로 오른쪽 내부 노드에 올라갈 뿐 루트에는 없다.
- 13: 오른쪽 내부 노드에 남는 키이다.
- 19: 리프에만 존재한다.
오류나 개정된 내용이 보이면 알려주세요