Heikki.
I have idea. when i begining vacuum i must create structure like hash table. And the first action i fill this hash table.
in code this look like:

for( blkno = ..; all pages; blkno++) {
ššif(! gistPageIsLeaf(blkno)) {
šššššfor( all tuples in blkno ) {
šššššššššhash[ blkno that is referenced by the tuple] = blkno;
ššššš}
šš}
}

getting is parent of page is fast and simple( hash[page] ).

But this solution is need 2 full reading of index.š

but Alexander says me that: this solution may be have a problem, because there is maintenance_work_mem.