B+ Tree의 삽입

기본적으로 차수 3의 B+tree의 삽입에서는 다음의 원칙을 따른다.

• 삽입 시 Overflow가 발생할 것 같으면 먼저 Right Split 후에 삽입
• leaf 노드에서는 삽입 시 가득 차 있으면 Right Split(기존의 값 중 오른쪽 값이 구분자로)
• 탐색 노드에서는 필요한 구분자 3개 중에서 중간 값을 루트 노드로 한다.
• 들어오는 쿼리 순 x,y,z, / 만들어지는 Page 순 A, B, C 로 해도 상관없음

참고사항

• 차수 4의 B+tree는 Split 시에 2/1개로 분리 후 삽입한다(따라서 왼쪽이 항상 무거워지게 구성되어 있다).
• 만약, 같은 ename '이순신'이  2000개 있다면? -> B+ tree에 같은 레벨로 두기 / 같은 rid 집합 속에 정렬되어있기(key value rid 집합 쌍)
• 분기하고 삽입 vs 삽입하고 분기 -> 결론은 분기하고 삽입, 왜냐하면 이게 더 효율적이고 DBMS에서 채택한 방식

 

삽입전개

(해당 자료는 박영철 교수님의 자료로 학습용으로 기록하였으며 저작권은 전부 박영철 교수님께 있습니다)

1~2) 처음 <8,x>, <5,y>의 삽입은 차례로 정렬하여 값을 넣어주면 된다

3) <1,z>를 넣으려고 하니 Pr의 노드안에 값이 2개가 들어 있는데 차수가 3이므로 Right Split을 진행한다. 따라서, <,8>이 구분자가 되고 <1,z>를 좌측 Ps에 삽입한다.

 

4) <7,w>를 넣으려고 하니 Ps에 이미 값이 2개가 기록이 되어 있으므로 다시 Right Split을 진행하여 <,5>를 구분자로 올리고 <1,z>와 <5,y>를 구분한다. 그리고 Pa에 <7, w>를 삽입한다.

5~6) <3,v>와 <12,u>를 각각 해당 위치에 삽입한다.

 

그리고 <9,f>를 Pt에 넣으려고 하니 이미 Pt에는 값이 2개가 기록되어 있다. 따라서 Right Split으로 Pb를 따로 빼고 구분자로 필요한 <,12>를 루트 노드에 올린다. 그런데 이 때, 루트 노드에는 이미 <, 5><, 8>가 있기에 총 <,5><,8><,12>가 되므로 여기서 중간 값을 루트 노드로 올린다.  결과적으로 밑처럼 바뀌게 된다.

7) Right Split 후에 Pt에 <9,f>를 삽입한다.

8) Pa에 <6,g>를 삽입한다.