| Bitmap Index |
Articles about Bitmap |
Information AboutBitmap Index |
|
A bitmap index is a special kind of Index that stores the bulk of its data as bitmaps and answers most queries by performing bitwise logical operations on these bitmaps. The most commonly used index, such as B+trees, are most effective if the values it indexes do not repeat or repeat a relatively smaller number of times. In contrast, the bitmap index is designed for cases where the values of a variable repeats very frequently. For example, the gender field in a customer database usually contains two distinct values, male or female. For such variables, the bitmap index can have a significant performance advantage over the commonly used trees. A bitmap index is typically generated for one column of a table (or an attribute of a relation). Continuing the gender example, a bitmap index may be logically viewed as follows. In the above example, ''CID'' indicates Customer ID, "gender" is the data to be indexed, the content of the bitmap index is shown as two columns under the heading ''bitmaps''. Each column in the above illustration is a ''bitmap'' in the bitmap index. In this case, there are two such bitmaps, one for gender ''F'' and one for gender ''M''. It is easy to see that each bit in bitmap ''M'' means whether a particular CID refers to a male. This is the simplest form of bitmap index known as the basic bitmap index. Clearly, most columns of a table will have more than two distinct values. For example, in a database containing customer from the US, a column indicating the states a customer lives in will have about 50 distinct values. The sales amount is likely to have much larger number of dictinct values. For such data, there are more advanced bitmap indexes that can keep the index sizes small and at the same time keep the query response time low as well. Common techniques for improving the basic bitmap index include compression, such as the Byte-aligned Bitmap Code ( BBC ) and Word-Aligned Hybrid code ( WAH ), complex encoding, such as the binary encoding, and binning.1 The bitmap indexes are especially useful in the data warehousing environment for joining large fact table to several small dimension tables {Link without Title} arranged in a star schema. AVAILABLE IMPLEMENTATIONS The first commercial database product to implement a bitmap index is Computer Corporation of American's Model 204 from mid-1980s. This product was the brain child of Dr. Patrick O'Neil {Link without Title} . This implementation is a hybrid between the basic bitmap index (without compression) and the RID-list. When the basic bitmap index becomes large, it switches to use the RID list, which effectively becomes a B+tree index. Because Oracle is widely deployed, many of its users may be aware of its bitmap indexing capability which existed since Oracle version 8.1.4 (1995). Oracle implements a version of the basic bitmap index compressed with BBC. Sybase Adaptive Server IQ implements something called the Encoded Vector Index ( EVI ), which is similar to the binary encoded index, but it does not use bitwise logical operations to produce answers. PostgreSQL versions 8.1 and later implement a bitmap index scan, where a temporary bitmap of all table rows is created in memory, which is used to combine the results of multiple index conditions with bitwise operations. Later, only those physical tuples in the table will be visited which matched the bitmap index conditions. In addition to joining multiple indexes, this also improves the Locality Of Reference of table accesses.2 There are also a number of research prototype implementations available as well, for example, RIDBit {Link without Title} and FastBit {Link without Title} {Link without Title} . REFERENCES
Articles about Bitmap Index
|
||||||||||
|
|