reftable: fix quadratic behavior when re-creating deleted refs #28803

Job	Run time
config	9s
fuzz smoke test	1m 29s
win build	3m 57s
sparse	3m 50s
rust-analysis	1m 26s
static-analysis	6m 3s
osx-reftable (macos-14)	35m 57s
osx-gcc (macos-14)	29m 40s
win+Meson build	3m 52s
osx-clang (macos-14)	38m 25s
documentation	7m 3s
osx-meson (macos-14)	47m 12s
win+VS build	-1s
linux-breaking-changes (ubuntu:rolling)	23m 9s
linux-reftable (ubuntu:rolling)	23m 25s
fedora-breaking-changes-meson (fedora:latest)	21m 25s
linux32 (i386/ubuntu:20.04)	1h 6m 18s
linux-sha256 (ubuntu:rolling)	23m 54s
almalinux-8 (almalinux:8)	14m 7s
linux-musl-meson (alpine:latest)	17m 35s
linux-TEST-vars (ubuntu:20.04)	23m 9s
debian-11 (debian:11)	20m 50s
linux-reftable-leaks (ubuntu:rolling)	35m 49s
linux-asan-ubsan (ubuntu:rolling)	51m 49s
linux-leaks (ubuntu:rolling)	44m 15s
linux-meson (ubuntu:rolling)	22m 42s
win+VS test	-1s
win test (5)	10m 24s
win test (4)	59m 5s
win test (2)	7m 7s
win test (6)	25m 48s
win test (8)	7m 1s
win test (7)	7m 48s
win test (9)	5m 30s
win test (1)	7m 24s
win test (0)	11m 13s
win test (3)	9m 51s
win+Meson test (7)	8m 28s
win+Meson test (4)	17m 58s
win+Meson test (3)	11m 58s
win+Meson test (5)	8m 5s
win+Meson test (0)	8m 10s
win+Meson test (9)	6m 45s
win+Meson test (1)	7m 28s
win+Meson test (2)	32m 43s
win+Meson test (8)	11m 24s
win+Meson test (6)	13m 27s
	14h 5m 5s

Provide feedback