Well it was taking like 20 seconds to do my cleanup. Five seconds still sucks for users. IIRC, remove has to recurse to every child to check for stored data, so I'm just removing the nodes manually and eating the tiny data memory leak.

edit: and yes, 4x is a constant fraction, as opposed to an asymptotic improvement. :)