[Indexing]B+ tree deletion

노드에서는 최소 만족해야하는 개수 기준이 있다. 이 기준을 deletion에도 기준을 유지시켜야 한다.

 

첫 번째 전략은 merge, 형제 노드와 merge하고 부모 노드를 업데이트한다.

두 번째 전략은 redistribute, 형제의 것을 빌려와 사용한다.

 

 

n=4이고 leaf의 최소 키의 개수는 C((4-1)/2)= 2 이므로 삭제하게 되면 underflow가 된다. merge를 한 후 부모 노드를 업데이트 해준다.

 

 

삭제 후 underflow가 발생하므로 merge나 redistribute를 해야한다. merge를 할 수 없으므로 kim을 가져와서 키의 최소 기준을 맞춘다. 

 

 

gold를 삭제하면 최소 키의 개수 2이 안되므로 merge를 사용할 수 있다. 같은 부모를 기준으로 merge하는 것이 편하므로 우측의 형제와 합치는 것이 좋다. 그런데 합치게 되면 부모 노드 기준으로 child가 1개로 줄어들게 된다. 이는 최소 기준을 만족하지 않는다.

부모 노드의 underflow를 해결하기 위해서 부모노드는 형제와 merge를 하면 된다. 하지만 이렇게 하면 root 노드의 child가 1개가 된다. 따라서 부모노드는 지우고 root를 left child와 merge 한다. 여기서 key값으로 Gold가 사용된다. leaf의 마지막 노드의 최소키인 Katz가 아니어도 child를 구준하므로 현재로서는 B+ tree 기준을 만족한다.