1. 리프 삭제
키가 있는 리프를 찾아 삭제한다
삭제는 항상 리프에서 시작한다. 이때 키를 지운 뒤 노드가 너무 비면 다음 단계에서 복구가 필요하다.
2. 최소 키 검사
삭제 후 점유율을 먼저 본다
리프가 최소 키 수를 만족하는지 확인한다. 여기서 유지 경로와 복구 경로가 갈린다.
최소 키 수 만족
추가 작업 없이 종료한다. 부모 키나 트리 높이는 변하지 않는다.
최소 키 수 미달
형제 노드와 부모의 구분 키를 함께 조정해야 한다.
3. 미달이면 복구
형제와의 관계에 따라 두 방식 중 하나를 쓴다
둘 다 리프의 빈자리를 메우기 위한 처리지만, 부모에게 미치는 영향은 다르다.
재분배
형제에게서 키를 하나 빌린다
형제 노드가 여유 키를 가지고 있으면 일부를 옮겨 온다.
부모 노드의 구분 키도 새 경계에 맞게 갱신된다.
병합
형제와 하나의 노드로 합친다
형제가 빌려줄 만큼 여유가 없으면 두 리프를 합친다.
부모에서는 구분 키를 삭제한다.
부모도 최소 키 수를 못 맞추면 위로 연쇄 병합이 이어질 수 있다.