Note that mixed insertion and deletion is worst-case O(n) in current implementation.

Original Raymond's design didn't preserve ordering during deletion. It had worst-case O(1) for mixed insertion and deletion. I didn't follow the numerous discussions about compact dict implementation, but at some point it became keeping holes and preserving ordering during deletion. This leads to the need of periodical O(n) reallocation for mixed insertion and deletion. Perhaps the technical reason of this was the couple relation between C implementation of OrderedDict and dict.