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

※ 정상상황에서의 삽입

● 초기상황이 아닌 경우가 정상 상황(Root 노드의 ptrd[1] != NULL인 상황)

● Root에서 출발하여 삽입할 record가 들어가야 할 데이터 노드를 찾아야 한다.

• 삽입할 record의 key값이 new_key라고 하자.
• Root노드에서 출발하여 navigation을 반복하여 인덱스 구조의 leaf노드에 도달하도록 한다.
• "new_key <= key[i]" 이 참인 첫 i를 발견하면 prti[i]를 통해 내려간다.
• 이러한 i가 발견되지 않을 시 그 노드의 맨 우측의 ptri를 통해 내려간다.
• 계속 반복하다 보면 ptri[0] == NULL 인 노드에 도달한다.(인덱스 구조의 leaf 노드에 도달한다.)
• 이 leaf 노드에서 new_key <= key[i] 인 첫 i를 찾아 ptrd[i]를 통해 데이터 노드로 내려간다.
• 이런 i가 없으면 leaf노드의 맨 우측 ptrd를 통해 내려간다.

● 찾은 데이터 노드에 삽입 시도

• Case 1: 빈자리가 있는 경우 : 순서에 맞춰 삽입하고 종료
• Case 2: 빈자리가 없는 경우 : overflow 발생

● 일반적인 경우 : Case 2의 overflow 발생

• 삽입할 record와 도달한 데이터 노들의 모든 record를 big node에 넣고 두 부분으로 split.
• Big node의 middle record까지는 현재 데이터 노드에 넣고, 뒷부분은 새로운 데이터 노드를 할당하여 넣는다.
• 새로운 데이터 노드는 ptr_new_data 라 하자.
• middle record의 ke;/y를 mid_key라 하자.
• <mid_key, ptr_new_data> 쌍을 도달한 데이터 노드의 부모 노드에 삽입. (부모 노드가 leaf 노드일 떄, 이를  type-1삽입 이라 부른자. 부모노드가 leaf 노드가 아닐 경우의 type-2 삽입과 약간 차이가 있다.)
• 도달한 데이터 노드와 새로운 데이터 노드를 연결.

● Type-1 삽입

• 삽입할 인덱스 노드를 Pointer curr가 가리킨다.
• 삽입될 내용 : <m_key, d_ptr>
• type-1 삽입에서는 삽입할 포인터의 type이 데이터 노드에 대한 Pointer타입이다.
• Case 1: curr에 빈자리가 있는 경우 → 순서에 맞춰 key 값과 데이터 노드의 포인터(ptr_new_data)를 넣고 종료
• Case 2: curr에 빈자리가 없는 경우 : curr가 overflow발생
•           → B-tree 삽입 연산의 overflow 발생시와 동일하게 처리
•           → 새로운 노드의 pointer field는 data node pointer(ptrd)에 넣어줘야 한다.

type-1 삽입에서 overflow가 발생하지 않는 상황

 

type-1 삽입에서 overflow가 일어나는 상황

B-tree의 overflow 처리 방식과 동일하다. ptrd에 연결되는 data node만 주의.