Tom,
Sound excellent. Index growth has been something that always bothered me (not
the disk space usage, but the slow searches).
I believe it's best to have pages marked dead at the time the last key
contained in the page is deleted (you didn't discuss how efficient this is),
because this will somehow improve the three depth. The same functionality
should be available in VACUUM (just in case). Thus we should 'free' the index
pages with one VACUUM run, instead of two.
In the spirit of my ramblings about automatic statistics/suggestions by
PostgreSQL for optimizations, could you also implement a NOTICE when the index
becomes too 'thin'? I believe this will help avoid severe performance
degradation if the process of removing the dead tuples becomes automatic.
It also occurs to me, that if such statistics are available, PostgreSQL might
run VACUUM automatically, on specific tables/indexes - all this controlled by
a CUG variable.
Daniel