Earlier on, the bitmap index
was regarded as a special form of inverted files (Knuth, 1998). The bit-transposed
file (Wong, Liu, Olken, Rotem, & Wong, 1985) is very close to the bitmap index
currently in use. The name bitmap index was popularized by O??™Neil and colleagues
(O??™Neil, 1987; O??™Neil & Quass, 1997). Following the example set in the description
of Model 204, the first commercial implementation of bitmap indices (O??™Neil,
1987), many researchers describe bitmap indices as a variation of the B-tree index.
To respect its earlier incarnation as inverted files, we regard a bitmap index as a
data structure consisting of keys and bitmaps. Moreover, we regard the B-tree as a
way to layout the keys and bitmaps in files. Since most commercial implementations
of bitmap indices come after the product already contains an implementation
of a B-tree, it is only natural for those products to take advantage of the existing
B-tree software. For new developments and experimental or research codes, there
is no need to couple a bitmap index with a B-tree. For example, in a research program
that implements many of the bitmap indexing methods discussed later in this
chapter (FastBit, 2005), the keys and the bitmaps are organized as simple arrays in
a binary file. This arrangement was found to be more efficient than implementing
bitmap indices in B-trees or as layers on top of a DBMS (Stockinger et al.
Pages:
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318