계속해서 키를 삽입해 볼까요? 다음 그림에서는 B 트리에 키 4와 키 5를 삽입합니다.

▲ 그림 10-7 insert 2

그림 10-7을 보면 키 4는 키 3이 있는 노드 끝에 추가되고 끝납니다. 키 5가 삽입되면 키 4 뒤에 키 5가 추가됩니다. 최대 키 개수를 넘겼군요. 노드에서 가운데 키 값인 4가 부모 노드로 올라가 키 2 뒤에 삽입됩니다. 키 3은 키 4의 왼쪽 자식이 되고, 키 5는 키 4의 오른쪽 자식이 됩니다. 데이터가 계속 추가되어 부모 노드까지 최대 키 개수를 넘기면 어떻게 될까요? 그때는 부모 노드도 연쇄적으로 split 연산을 하면 됩니다. 그렇게 되면 트리 높이가 하나 더 늘어나게 되겠지요.

이번에는 삭제를 알아보겠습니다. B 트리에서 키 삭제는 항상 리프 노드에서 진행합니다. 리프 노드가 아닌 노드에서 키를 삭제해야 한다면 대체 키를 바꾼 후 삭제를 진행합니다.

다음 그림에서 키 6을 삭제한다고 합시다.

▲ 그림 10-8 delete 1