Структура данных / алгоритм для запроса: фильтровать по A, сортировать по B, возвращать N результатов

Представьте, что у вас есть большой набор #m объектов со свойствами A и B . Какую структуру данных можно использовать в качестве индекса (ов) (или какой алгоритм) для повышения производительности следующего запроса?

find all objects where A between X and Y, order by B, return first N results;

То есть фильтровать по диапазону A и сортировать по B , но возвращает только несколько первых результатов (скажем, не более 1000). Вставки очень редки, поэтому допустима тяжелая предварительная обработка. Я не доволен следующими вариантами:

1. С записями (или индексом), отсортированными по B : сканировать записи / индекс в порядке B , вернуть первый N , где A соответствует XY. В худших случаях (несколько объектов соответствуют диапазону XY или совпадения находятся в конце записей / индекса) это становится O (m) , что для больших наборов данных размером m недостаточно хорош.

2. С записями (или индексом), отсортированными по A : Выполняйте двоичный поиск, пока не будет найден первый объект, соответствующий диапазону X-Y. Отсканируйте и создайте массив ссылок на все объекты k , которые соответствуют диапазону. Отсортируйте массив по B, верните первое N . Это O (log m + k + k log k) .Если k мало, то на самом деле это O (log m) , но если k велико, то стоимость сортировки становится даже хуже, чем стоимость линейное сканирование по всем м объектам.

3. Адаптивный 2/1 : выполнить двоичный поиск первого совпадения диапазона X-Y (используя индекс по A); выполнить двоичный поиск последнего совпадения диапазона. Если диапазон небольшой, продолжайте с алгоритмом 2; в противном случае вернемся к алгоритму 1. Проблема здесь в том, что мы вернемся к алгоритму 1. Хотя мы проверили, что «многие» объекты проходят фильтр, что является хорошим случаем для алгоритма 1, это «много» является не более чем константой ( асимптотически сканирование O (n) всегда будет преобладать над сортировкой O (k log k) ). Таким образом, у нас все еще есть алгоритм O (n) для некоторых запросов.

Существует ли алгоритм / структура данных, позволяющая отвечать на этот запрос в сублинейном времени?

Если нет, то какие компромиссы могут быть хорошими для достижения необходимой производительности? Например, если я не гарантирую возврат объектов с лучшим рейтингом по их свойству B (вспомним <1.0), то я могу сканировать только часть индекса B. Но могу ли я как-то сделать это, ограничивая качество результатов?