B+Tree 삽입(Insertion) 알고리즘 - 1

※ 첫 record 삽입

● Root가 아직 NULL인 경우에 해당됨

● 아직 하나의 record가 삽입되기 전

• 인덱스 노드 하나를 만들고 이를 Root가 가리키게 함.
• ptri[0]에 NULL을 넣음(이것은 이 노드가 index 구조의 leaf 노드임을 나타낸다.)
• 데이터 노드를 하나 만듬.
• record를 데이터 노드에 삽입.
• 인덱스 노드의 ptrd[0]가 이 데이터 노드를 가리키게 한다.
• 인덱스 노드의 ptri[1] 에 0을 넣는다. ≫ 초기상황(아직 B+Tree의 형태를 갖추지 못함.) 임을 나타냄.

- 초기상황 check 방법: Root 가 가리키는 노드의 (ptri[0] == NULL && ptri[1] == NULL)이 참이라면 초기상황이다.

※ 초기 상황(초반부) 삽입

● Root가 NULL이 아닌 경우의 초반부 삽입

• Sequence set에 데이터 노드 하나만 존재하는 경우
• Root 인덱스 노드의 Pointer[1]이 NULL인지를 체크하여 확인.
• 초반부 삽입일 경우, 무조건 첫 데이터 노드에 삽입하는 것을 시도 (= index구조에서 navigation과정 생략)
• Case1 :데이터 노드에 빈 자리가 있으면 순서에 맞춰 삽입 후 종료.
• Case2 : 데이터 노드에 빈자리가 없으면 데이터 노드 splitting 진행 (overflow 처리)
•           → 삽입할 record와 데이터 노드의 모든 record를 big node에 넣고 두 부분으로 split
•              (첫부분: 중간 record까지, 둘째 부분: 중간 record 이후 모든 record)
•           → 첫부분은 curr의 데이터 노드에 삽입, 뒷부분은 새로운 데이터 노드(new data node)를 할당하여 여기에
•               삽입.
•           → 중간 record의 key값을 Root 인뎃으 노드의 key[0]에도 삽입.
•           → 새로운 데이터 노드에 대한 포인터를 Root 인덱스 노드의 Pointer1에 넣음.
•           → 두 데이터 노드를 link시킴. (link of data node2 = NULL)

이 후, data node 1롸 data node2는 서로 link된다. data node 2는 Root 인데스 노드의 ptrd[1]에 삽입(link)된다.