Re: How many levels a B-tree has?

On Wed, May 14, 2003 at 12:42:17PM -0400, Tom Lane wrote:

"Cris" <cris@dmcid.net> writes:

I need to know (if it possible) how many LEVELS a B-tree index
has (to know how many accesses to the disk it would do in a query).

In CVS tip we keep track of that information in the index's metapage
(page zero). But in so-far-released versions it's not explicitly
tracked anywhere. You'd have to actually chase down the tree from the
root to a leaf to count the levels.

Does this level count takes into consideration the fast root of the
tree? I think it doesn't.

If this is so, the number of disk accesses will be overestimated by
reading only the level count. One should traverse levels down from the
true root to the fast root and substract that from the level count.

--
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"El dia que dejes de cambiar dejaras de vivir"

Alvaro Herrera <alvherre@dcc.uchile.cl> writes:

On Wed, May 14, 2003 at 12:42:17PM -0400, Tom Lane wrote:

In CVS tip we keep track of that information in the index's metapage
(page zero). But in so-far-released versions it's not explicitly
tracked anywhere. You'd have to actually chase down the tree from the
root to a leaf to count the levels.

Does this level count takes into consideration the fast root of the
tree? I think it doesn't.

IIRC we store the levels of both the true root and the fast root in
the metapage.

If this is so, the number of disk accesses will be overestimated by
reading only the level count. One should traverse levels down from the
true root to the fast root and substract that from the level count.

You're correct, the fast-root level is the interesting one for
performance estimates.

regards, tom lane