History
The concept of bitmap index was first introduced by Professor Israel Spiegler and Rafi Maayan in their research "Storage and Retrieval Considerations of Binary Data Bases", published in 1985. The first commercial database product to implement a bitmap index was Computer Corporation of America's Model 204. Patrick O'Neil published a paper about this implementation in 1987. This implementation is a hybrid between the basic bitmap index (without compression) and the list of Row Identifiers (RID-list). Overall, the index is organized as a B+tree. When the column cardinality is low, each leaf node of the B-tree would contain long list of RIDs. In this case, it requires less space to represent the RID-lists as bitmaps. Since each bitmap represents one distinct value, this is the basic bitmap index. As the column cardinality increases, each bitmap becomes sparse and it may take more disk space to store the bitmaps than to store the same content as RID-lists. In this case, it switches to use the RID-lists, which makes it a B+tree index.
Read more about this topic: Bitmap Index
Famous quotes containing the word history:
“These anyway might think it was important
That human history should not be shortened.”
—Robert Frost (1874–1963)
“Let us not underrate the value of a fact; it will one day flower in a truth. It is astonishing how few facts of importance are added in a century to the natural history of any animal. The natural history of man himself is still being gradually written.”
—Henry David Thoreau (1817–1862)
“Only the history of free peoples is worth our attention; the history of men under a despotism is merely a collection of anecdotes.”
—Sébastien-Roch Nicolas De Chamfort (1741–1794)