Re: bitmap and b-tree index

Howard J. Rogers wrote:
>
> "chank000" <Kheun_C_Chan_at_sbphrd.com> wrote in message
> news:8li9p4$eml$1_at_phunn2.um.us.sbphrd.com...
> > I've heard the term bimap index an b-tree index, but I would like someone
> > to explain what is bitmap index and b-tree index. What are the
 differences
> > between the two. Thanks in advance.
> >
>
> A b-tree index has what are termed leaf nodes that store key values and a
> rowid, so that you can quickly retrieve a particular key value, and then use
> the rowid to locate directly the relevant full entry in the underlying table
> (saves you having to do a full table scan, where you just happen to stumble
> across the right entry).
>
> A bitmap index also has leaf nodes -but they don't store any values as such,
> merely a series of 1s and 0s. The ones signify that a record has a value,
> and the zeroes signify that it doesn't. You store a start rowid, and a stop
> rowid, and so you can therefore work out (by offsets) whether a given record
> in the underlying table actually has the value you are looking for.
>
> In a highly simplified case: suppose you index a column called "Gender".
> There are two possible values: "M" and "F". So you declare one leaf node to
> be the 'M" bitmap, and one to be the "F" bitmap. Now if the values in the
> first leaf node are '10000111", you'd expect the values in the other to be
> "01111000".
>
> And that example gives the clue as to when you'd use the one type of index
> as opposed to the other. If your data has low 'cardinality' (ie, the
> propensity to have multiple different values), bitmap indexes are excellent.
> High cardinality data (such as an auto-incrementing Order Number field)
> would make positively lousy bitmaps (because you'd have an infinifty of leaf
> nodes, each one of which would only ever have one "1", with everything else
> set to "0".
>
> There are a couple of other issues. Updates to the key values of tables
> with btree indexes are relatively painless... if "Bob" wants to become
> "Robert", then you simply mark the index entry "Bob" for deletion, and
> insert a new value for "Robert". Bitmaps are horrendous when updates to the
> key values occur -because you have to lock the entire table whilst you work
> out what all the possible key values are, and then build appropriate leaf
> node structures to house the relevant discovered values.
>
> Which means that you'd use bitmap indexes on tables which don't actively
> undergo updates very often -decision support systems, for example, or
> read-only databases -provided always that the data is low cardinality (I
> seem to recall someone somewhere saying that when your data has more than
> about a dozen possible values, kiss goodbye to the idea of using bitmaps.
> That's just anecdote, though).
>
> B-trees are good for situations when your tables do undergo regular updates,
> and when the cardinality of your data is high.
>
> Regards
> HJR
There is a performance benchmark on the Oracle site somewhere bitmap indices on a (static) million row table outperformed the equivalent b-tree for all cardinalities up to 500,000...mainly since it was so much smaller than the b-tree..

This of course doesn't obviate the need for either as you point out.

HTH

-- 
===========================================
Connor McDonald
http://www.oracledba.co.uk

We are born naked, wet and hungry...then things get worse