[데이터베이스&파일처리] B+ 트리에서의 삽입

* 본 자료는 박영철 교수님의 수업 자료를 토대로 정리되었습니다. 저에겐 저작권이 없으며 공부 용으로 포스팅 된 글임을 밝힙니다. 당연히 펌은 금지입니다.

노드의 차수를 3으로 가정하고(최대 Child를 3으로 제한하고)
<8,x>, <5,y>, <1,z>, <7,w>, <3,v>, <12,u>, <9, f>, <6,g> 를 차례로 삽입하는 경우

 

트리가 생성 될 경우 빈 루트페이지만 존재한다.
<8,x>를 삽입하고 <5,y>를 삽입하는데, <5,y>가 작은 값이므로 <8,x>의 앞으로 삽입된다.

 

<1,z>를 삽입 해야 되는데 overflow가 발생한다. 이런 경우 일단 들어가야 할 값은 temp에 저장해 두고 공간확보 작업이 선행된다.
루트 노드의 경우 split하지 않고 하위 노드 2개를 생성한다. 하위 노드는 리프 노드이므로 Doubly Linked List로 연결하고 값을 각각 한개씩 넣어준다.
구분자는 두 값중 하나를 택한다. 왼쪽 하위 노드는 구분자 보다 작고, 오른쪽 하위 노드는 구분자 보다 크거나 같아야 하므로 8을 구분자로 선택한다.
공간이 확보 되었으므로 <1,z>를 적절한 위치에 넣어 준다.

 

<7,w>를 삽입 해야 하는데 B+노드의 특성상 Ps의 <5,z>뒤에 들어가야 하므로 overflow가 발생한다.
루트노드가 아닌 경우엔 공간 확보는 무조건 Right Split이 사용된다.
Ps노드 옆에 Pa를 생성하고 값을 나누어 담는다.(Right Split) <1,z>와 <5,y>로 나누어 졌으므로 상위 노드에선 구분자가 5가 추가된다.
공간이 확보 되었으므로 <7,w>를 삽입한다.

 

 

<3,v>를 넣고 <12,u>를 넣는다. overflow가 발생하지 않으므로 그냥 삽입하면 된다.

 

<9,f>를 삽입해야 되는데, Pt에 들어가야 한다. overflow이므로 공간을 확보 해야 되는데 조금 복잡하다.
일단 루트 노드가 아니면 무조건 Right Split이라고 했다. Pt옆에 Pb를 만들고 값을 나누어 준다. 구분자는 큰값이 들어가야 하므로 12로 선택한다.
차수를 3으로 가정 했으므로 상위 노드에는 더이상 구분자가 들어갈 공간이 없다. 이럴 경우 상위 노드는 Right Split해 줘야 되는데 루트로드는 Right Split하지 않는다고 했다. 이럴 경우 루트 노드를 Right Split해서 상위 노드를 한개 더 추가 하는게 구현이 더 쉽지만 한번 루트 노드는 영원한 루트 노드이다. 안전성 및 사용의 편의를 위해 루트 노드는 변경하지 않도록 구현하여야 한다.

이럴때는(Root노드에서 overflowr가 발생할 경우 모두) 루트노드에 하위 노드 2개를 추가 해 준다.
필요한 구분자는 5, 8, 12이므로 루트는 8을 취하고 하위 노드 두개는 각각 5와 12를 가진다.




마지막으로 <6,g>를 넣어 줘야 한다. Pa에 들어가야 하는데 overflow한다. 간단하게 Right Split해 준다. <5,y>와 <7,w>로 나누어졌으므로 구분자는 7이다. 공간이 확보 되었으므로 <6,g>를 삽입한다.

여기서 <4,q>를 삽입하면 어떻게 될까??