Поиск по ключу с проверкой на вхождение в интервал

[yuramag]

Привет всем!
Есть следующая задача. Дана таблица с полями: PKey, BeginDate, EndDate и Value.
PKey и BeginDate входят в первичный ключ. В таблице много записей и на каждый уникальный PKey приходится примерно по 15-25 различных записей с разными неперекрывающимися BeginDate и EndDate.
Существует необходимость кэширования записей - т.е. создание наиболее эффективной структуры данных с возможностью быстрого поиска по заданным PKey и некой дате попадающей в диапозон между BeginDate и EndDate.
Я смотрел в сторону различных В-деревьев, но не совсем понятно каким образом проверять дату на попадание в интервал? Ведь здесь идёт поиск не на точное сравнение ключей, а ещё и на сравнение по датам.
Если кто-нибудь сталкивался с подобными задачами, прошу помочь...

если всего 15-25 записей на каждый PKey, то в чем проблема просто все их достать, посмотреть? или у вас там, что, мегабайты данных в каждом Value хранятся

в общем случае, если снять это ограничение про 15-25, стандартное решение - интервальные деревья. см. кормена 14-ю главу.

можно с B-деревьями их комбинировать если данные в память не влезают и хранятся на диске.

[yuramag]

Похоже, что интервальное дерево это то, что нужно.
Спасибо!