On Mon, Jan 7, 2013 at 3:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> One issue that needs some thought is that the argument for this formula
> is based entirely on thinking about b-trees. I think it's probably
> reasonable to apply it to gist, gin, and sp-gist as well, assuming we
> can get some estimate of tree height for those, but it's obviously
> hogwash for hash indexes. We could possibly just take H=0 for hash,
> and still apply the log2(N) part ... not so much because that is right
> as because it's likely too small to matter.
Height would be more precisely "lookup cost" (in comparisons). Most
indexing structures have a well-studied lookup cost. For b-trees, it's
log_b(size), for hash it's 1 + size/buckets.