Как один из вариантов оптимизации поиска: факторизация всех объектов по булевским аттрибутам. То есть объекты делятся на непересекающиеся группы с различными комбинациями булевских параметров.
Имеется массив с количеством элементов, равным количеству групп.
Каждая группа объединяется в список и за голову цепляется за соответствующий элемент массива.
Таким образом, имея запрос с булевскими параметрами можно за почти константное время (ограниченное сверху) можно найти все такие фактор-группы и линейно по ним пройтись, отбирая элементы по другим параметрам.
Сами списки можно также факторизовать по какому-нибудь часто-используемому атрибуту (потребуется набор индексов, для нахождения соответствующих фактор-групп) или просто отсортировать.
Но все приведенное выше является не более чем оптимизацией поиска. В худшем случае все равно будет линейное время.
(кстати, а чем линейная сложность автора не устраивает?)
