[Indexing]B+ tree insertion

insert할 노드가 full이면 split을 해야한다. 기존 노드가 k1 ... kn 이 있는 상황이라면 C(n/2)씩 나눈다. 나눈 노드에 대해서 부모 노드도 child 하나를 추가한다. 부모 노드의 새로운 key값은 node 2의 가장 작은 키 값이 된다. 

 

splitting non-leaf node

부모 노드도 full이면 부모 노드를 split 해야한다. 이런 상황이 root까지 올라갈 수도 있다. 

 

non-leaf node를 splitting할 때 key값 하나를 올려 보내고 node를 splitting 한다. 

 

1. Adams를 검색하여 노드를 선택한다.

2. node가 full이기 때문에 split한다.

3. A B Ca Cr 을 나눈다. C(n/2)기준으로 나누면 2개씩 나눈다. 

4. Ca를 부모에 키로 넣고 포인터로 나눈 노드들을 가리킨다. 

 

 

leaf 노드를 splitting하고 non-leaf 노드도 splitting하게 된다.