So if you're expecting a table to have a heavy UPDATE load it may be a good idea to lower its fillfactor from the default of 100 (for example, ALTER TABLE foo SET (fillfactor = 95);). This means that once a page is 95% full no new rows will be inserted into it, and the remaining 5% will be available for updated rows. HOT will also do "mini-vacuums" on individual pages as needed to free up space.
Of course, it's up to you to decide whether this tradeoff is worth increasing the effective size of your table by ~5%. But even tables with fillfactors at the default of 100 will get some benefit from HOT.
More info: https://github.com/postgres/postgres/blob/master/src/backend...
Edit to add: One caveat is that HOT won't work if you UPDATE a column that is indexed - then, of course, Postgres will have to touch the index.
As noted, 3 levels suffices for a moderate sized table, and it would be rare to need more than 5 levels. The "levels" in question are pages of memory that have to be looked at. The reason that this is less than you expect is that inside of each page you essentially have a tree that has several levels to traverse. However the time to traverse that tree is less than the time to fetch the next page, so the operations of concern are fetches of pages.
The most important number noted in that link is that under normal operation once caches are warmed up, it should a maximum of one disk seek to traverse the index. That single disk seek, if it happens, takes longer than all other operations.
The long and short of it is, "in theory log(n), in practice a reasonably small constant."
because if that's correct then it makes sense to err on the side of too many indices.
of course, it is better to be perfect. but if you have an error, which side would you prefer to be on?
and you don't need "significant" volumes to hurt with a full table scan (ie it will hurt most of you).
[what surprised me was the 99% cache. that is very dependent on your application, but i guess is common for web apps?]