B+tree 삽입(Insertion) 알고리즘 - 3(Type-2 삽입)

※ 맨 아래층이 아닌 인덱스 노드로의 삽입 : type-2

• curr가 맨 아래층보다 위의 층의 노드이며 여기에 삽입하는 경우
• B-tree의 삽입과 동일한 방식으로 일어남.
• 다만, 사용할 포인터 필드는 ptri 이다. (즉, index node에 대한 Pointer를 저장하는 필드.)
• Case 1: 빈자리가 있는 경우 : 순서에 맞춰 삽입하고 종료
• Case 2: 빈자리가 없는 경우 : overflow 발생

● Case 1: 빈공간이 있는 경우

---

● Case 2: 빈공간이 없을 경우

 

---

※ 삽입 과정에서 부모 주소의 관리 : Stack 이용

• 삽입과정에서 데이터노드를 찾아가는 과정에서 각 노드의 Pointer를 stack에 저장
• 인덱스 구조의 Root에서 시작
• 아래로 내려갈 때마다 그 직전에 노드의 주소를 stack에 push한다.
• 결국 데이터 노드에 도달하면 stack에는 데이터노드의 부모부터 Root노드까지의 경로 상의 모든 노드들의 주소가 저장됨.
• 부모 노드가 필요하면 stack에서 pop하여 사용 가능.