The reason for this is that the btree that's built can be thought to be logically ordered by the concatenation of the keys. It can only be traversed via the tree structure by comparing those keys left-to-right.
Think of a btree ordered by a string of characters.
If you have the strings "abc", "abd", "bed" etc you can use (<,=,>) to traverse the tree given a single-character key like "a". But you can't do a simple top-down traversal of the tree against the trailing character. The tree's not ordered correctly for such a traversal.
So you can do a sequential scan of the index or a sequential scan of the table. Either way you get O(n) rather than O(log2(n)). Index tables carry a lot of metadata, especially as they grow and many page-splits occur (i.e. as the tree deepens). For tables with short columns they can easily be longer than the table itself. PG never does a sequential scan on an index, always on the base table. In the end you have to visit the table to retrieve the rows, after all ...
