Re: Oracle b-trees

pkelley_at_coat.com wrote:
: Assuming that blocks are OS blocks or Oracle multi-blocks (multi-block
: read)

Neither. They are oracle blocks, defined in the parameter file as DB_BLOCK_SIZE.

: at worst, it seems to me that, with only 3 or 4 levels, beyond a
: certain number of rows (and depending on skewness of the b-tree, perhaps)
: you must read multiple blocks at at least one level in order to find a
: pointer to the correct range of items at the next level.

No. I see where the confusion is; the problem is that you are thinking "b-tree" but Oracle indexes are actually B-star trees. The leaf blocks are arranged in a doubly-linked list. If you are doing a range scan on an index, it seeks down to the first (or last) value in the range and then reads straight through the leaf nodes until it runs out of values in your range.

: [..] Now that I think of it, I
: suppose that by "block" they must mean "branch or leaf node".

Yes; each oracle block is a page (or "node") in the index.

: And has anyone heard of a stagnant index bug [..]
: [..] The value is always the highest value less than the low value
: from a recent massive delete.

It's not a bug. The problem *here* is (probably) that when all of the index keys in a leaf block of the index are deleted, Oracle doesn't deallocate the block or anything. If you issue the command "analyze index OWNER.INDEX validate structure", you can then see the amount of wasted space in the index in the table INDEX_STATS. You are specifically interested in DEL_LF_ROWS and DEL_LF_ROWS_LEN.

I have found that performance can be increased a great deal by periodically dropping and rebuilding indexes.

-bn

-- 
-bn
random_at_interaccess.com	(PGP 2.6.2 public key available on request)
"There is no .signature -- only ZUUL!"