Re: Reverse key Indexes Oracle 8.0

The term 'skewed' is rather vague.

The type of b-tree implemented in Oracle is a height-balanced b-tree, and it will always re-balance itself so that the
number of steps from top to bottom is
always N or N+1.

The 'skew' may refer to the fact that
Oracle can end up with an index where
leaf-blocks at one end of the index are nearly empty and leaf blocks at the
other end are packed. This happens
in situations where data is inserted
with a sequencing key value, and
deleted by age BUT some old rows
are not deleted. (Typical example a
table representing a FIFO queue
where some rows are simply marked
as 'bad' and never get deleted).

The architectural problem that causes
this results from the fact that Oracle
does not coalesce leaf-block - the
concept of B-trees is that a leaf block should be split when full, BUT that
two adjacent leaf blocks should be
merged when their total space usage
drops below a critical limit. However, Oracle will release completely empty
blocks back onto the freelist.

BTW - if you insert data using a meaningless ascending sequence key, the index will be perfectly packed, Oracle cheats a little bit on the 'split the block' algorithm.

As Mark pointed out in another thread, the primary reason for reverse keys is to reduce contention on the trailing leaf block in an OPS environment - but then the index is really only any use for linking child rows to parent rows on a PK/FK join.

--

Jonathan Lewis
Yet another Oracle-related web site: http://www.jlcomp.demon.co.uk

markp7832_at_my-deja.com wrote in message <81umdp$1hg$1_at_nnrp1.deja.com>...
>In article <3842ac32.11741392_at_read.news.globalnet.co.uk>,
> boulke_at_globalnet.co.uk (Keith Boulton) wrote:
>> On 29 Nov 1999 12:46:39 +0000, Robin Smith
>> <smithrc_at_zdbaora.nat.bt.com> wrote:
>>
>> >records will always be added to the right hand side of the index so
>it
>> >will become skewed. If you reverse the key then entries will also go
>> >into the middle of the index so will become self balancing.
>>
>> A b*tree index cannot become skewed.
>>
>I believe that your comment that a b*tree index cannot become skewed is
>only true in theory. Depending on how the b*tree is implemented in
>code, activity unbalances the tree. In theory it should be rebalanced
>as activity takes place but there is a cost to doing so. This cost is
>highest for deletes and if my memory is correct the version 7
>documentation claimed that Oracle rebalanced for inserts but it
>deferred much of the work for deletes. I have read some posts in the
>past questioning how good a job Oracle did rebalancing for inserts in
>the case of sequential keys. I can not remember the ver 8
>documentation on this topic but I have not noticed any growth behavior
>changes on our indexes so I suspect there has been no major changes to
>the implementation of b*trees with Oracle.
>--
>Mark D. Powell -- The only advice that counts is the advice that
> you follow so follow your own advice --
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
Received on Mon Nov 29 1999 - 14:55:08 CST