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."
Re:Understanding Postgres Performance
by Someone on Wednesday October 03, 2012 @02:29AM
(#4606122)
Thanks. But a disk seek is not a small constant. I would almost describe that as "in theory log(n), in practice a disk seek, so half the speed" (assuming that the record can be written with one disk seek)
Re:Understanding Postgres Performance
by jeltz on Friday October 05, 2012 @07:09AM
(#4616387)
A hash index will also require one disk seek which makes b-tree indexes and hash indexes have more similar performance than the theoretical O(log n) vs O(1) would indicate.
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."