Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes

Rasmus Pagh, S. Srinivasa Rao

Let S be a finite, ordered alphabet, and let x = x_1 x_2 ... x_n be a string over S. A "secondary index" for x answers alphabet range queries of the form: Given a range [a_l,a_r] o…