Этот вид индекса определяется на множестве записей, в котором каждому свойству записей ставится в соответствие битовая строка (статья индекса). Количество битов в строке равно общему количеству записей файла, и соответствующий данной записи бит принимает единичное значение тогда и только тогда, когда запись обладает рассматриваемым свойством. Очевидно, что при этом записи файла СУБД пронумеровываются, так что соответствие между битами строки и записями устанавливается по этим внутрисистемным номерам. Свойство может иметь различный смысл, например, может означать, что некоторый атрибут записи имеет данное значение.
Организация индекса имеет два важных достоинства:
- Если индексирование осуществляется по некоторому ключу и мощность множества значений этого ключа невелика, для хранения битового индекса требуется сравнительно небольшой объем памяти, а в некоторых случаях он может полностью помещаться в оперативную память. Это обстоятельство обеспечивает дополнительное существенное повышение производительности операций доступа к данным за счет уменьшения количества операций ввода-вывода, связанных с обращением к индексу.
- Битовое представление индекса позволяет с высокой эффективностью выполнять операции выборки (селекции) записей по сложным логическим критериям, содержащим логические связки AND, OR и NOT, с помощью поразрядных логических операций над битовыми строками.
Возможны различные другие схемы организации битовых индексов. Например, можно статьи индекса ставить в соответствие не свойствам записей, а самим записям. При этом статья индекса будет содержать уникальный идентификатор записи (не обязательно соответствующий первичному ключу) и битовую строку, позиции которой будут соответствовать значениям различных свойств.