Deleting, indexes and transactions

Hello PostgreSQL community,

Two tables, A and B, both with auto generated technical PK, A and B are in
relationship via nullable non-unique FK a_fk column in B to A's PK. There
are no other relationships involving table A. Lets say A has ~20k rows, and
B ~500k rows.

When there is no index on a_fk column, if one deletes Bs with DELETE FROM b
WHERE a_fk IS NOT NULL, and then in same transaction also deletes all As -
deleting As lasts painfully long.

Adding an index on FK in B, improves A deletion times significantly.

Can someone please provide an explanation/rationale of this behavior, why
does it take so long to delete As in first case without index? Thanks in
advance!

Btw, I'm using PostgreSQL 9.0. Will try how 9.1 behaves.

Kind regards,
Stevo.