A method for providing a compressed index for a stream of binary data records comprises steps of indexing a field from each record in a bitmap index, compressing stored bits in each column of the bitmap index by replacing a group of successive bits with a code and outputting the code. There is provided at least one of a first code for replacing a sequence of a first filling, a literal and a second filling, and a second code for replacing a sequence of a first literal, a filling and a second literal. In this context, a filling is a sequence of bits with the same value and a literal is a sequence of bits with different values.