|
|
|
Поиск по ключу с проверкой на вхождение в интервал
|
|||
|---|---|---|---|
|
#18+
Привет всем! Есть следующая задача. Дана таблица с полями: PKey, BeginDate, EndDate и Value. PKey и BeginDate входят в первичный ключ. В таблице много записей и на каждый уникальный PKey приходится примерно по 15-25 различных записей с разными неперекрывающимися BeginDate и EndDate. Существует необходимость кэширования записей - т.е. создание наиболее эффективной структуры данных с возможностью быстрого поиска по заданным PKey и некой дате попадающей в диапозон между BeginDate и EndDate. Я смотрел в сторону различных В-деревьев, но не совсем понятно каким образом проверять дату на попадание в интервал? Ведь здесь идёт поиск не на точное сравнение ключей, а ещё и на сравнение по датам. Если кто-нибудь сталкивался с подобными задачами, прошу помочь... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.01.2011, 23:48 |
|
||
|
Поиск по ключу с проверкой на вхождение в интервал
|
|||
|---|---|---|---|
|
#18+
yuramag, Возможно вам поможет такая структура данных как интервальное дерево? http://en.wikipedia.org/wiki/Interval_tree ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2011, 00:58 |
|
||
|
Поиск по ключу с проверкой на вхождение в интервал
|
|||
|---|---|---|---|
|
#18+
Algol36, Похоже, что интервальное дерево это то, что нужно. Спасибо! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2011, 17:15 |
|
||
|
Поиск по ключу с проверкой на вхождение в интервал
|
|||
|---|---|---|---|
|
#18+
Если я правильно понял задачу, то решается таким запросом (синтаксис MySQL): Код: plaintext 1. 2. 3. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2011, 18:00 |
|
||
|
|
start [/forum/topic.php?fid=16&tid=1343189]: |
0ms |
get settings: |
9ms |
get forum list: |
19ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
171ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
33ms |
get tp. blocked users: |
1ms |
| others: | 259ms |
| total: | 509ms |
| 0 / 0 |
