다음은 차수가 4인 B+-트리의 초기 상태이다. 이 B+-트리에 색인키… | [7급 국가직 데이터베이스론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 데이터베이스론] 11년 1회차
다음은 차수가 4인 B+-트리의 초기 상태이다. 이 B+-트리에 색인키 ‘18’, ‘21’을 순서대로 삽입할 때 생성되는 B+-트리의 구조로 옳은 것은?
<B+-트리의 초기 상태>
문제 이미지
1
2
3
4
해설

삽입 결과는 루트 37 아래에 내부 노드 21과 내부 노드 48·60이 있고, 리프가 18·21 / 23·37 / 46·48 / 56·59·60 / 65·71·92인 3단계 트리다.

차수가 4이면 한 노드에 키가 최대 3개다. 18은 첫 리프에 들어가 18·23·37이 되어 넘치지 않는다. 21을 넣으면 첫 리프가 18·21·23·37로 넘쳐 분할되어 18·21과 23·37이 되고, 구분키 21이 루트로 올라간다.

그러면 루트가 21·37·48·60으로 넘치므로 다시 분할되어 가운데 키 37이 새 루트로 올라가고, 왼쪽 내부 노드는 21, 오른쪽 내부 노드는 48·60이 된다. 트리 높이가 하나 늘어난다.

  • 첫 리프를 18·21·23으로, 다음 리프를 37 하나로 나눈 구조 — 넘친 리프의 키 4개는 2개·2개로 균등 분할되어야 하므로 3개·1개로 나뉜 이 구조는 삽입 결과가 아니다.
  • 루트를 48로 둔 구조 — 넘친 루트 21·37·48·60을 분할할 때 올라가는 키는 37이다. 또 46·48 리프가 루트 48의 오른쪽에 있어 46을 찾으면 왼쪽으로 내려가 찾지 못하는 잘못된 트리다.
  • 루트를 23·48·60으로 두고 리프를 18·21·23과 37·46·48로 바꾼 구조 — 넘친 리프를 분할하지 않고 키를 형제 리프로 옮긴 재분배 결과로, 표준 B+ 트리 삽입의 분할 결과가 아니다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 데이터베이스론] 11년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 데이터베이스론 기출문제 암기장 전체 보기