알고리즘
B+Tree 삽입(Insertion) 알고리즘 - 1
SunFly
2021. 10. 12. 01:02
※ 첫 record 삽입
● Root가 아직 NULL인 경우에 해당됨
● 아직 하나의 record가 삽입되기 전
- 인덱스 노드 하나를 만들고 이를 Root가 가리키게 함.
- ptri[0]에 NULL을 넣음(이것은 이 노드가 index 구조의 leaf 노드임을 나타낸다.)
- 데이터 노드를 하나 만듬.
- record를 데이터 노드에 삽입.
- 인덱스 노드의 ptrd[0]가 이 데이터 노드를 가리키게 한다.
- 인덱스 노드의 ptri[1] 에 0을 넣는다. ≫ 초기상황(아직 B+Tree의 형태를 갖추지 못함.) 임을 나타냄.
※ 초기 상황(초반부) 삽입
● 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)
