Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 20.01.2011, 00:23
Новичок

Отправить личное сообщение для yuramag Посмотреть профиль Найти все сообщения от yuramag
 
Регистрация: 19.01.2011
Сообщений: 2

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

 
Сообщений: n/a

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

 
Сообщений: n/a

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

можно с B-деревьями их комбинировать если данные в память не влезают и хранятся на диске.
  #4  
Старый 20.01.2011, 18:06
Новичок

Отправить личное сообщение для yuramag Посмотреть профиль Найти все сообщения от yuramag
 
Регистрация: 19.01.2011
Сообщений: 2

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра