Re: bitmap and b-tree index

"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 Received on Tue Jul 25 2000 - 00:00:00 CDT