Здравствуйте, _Lexx, Вы писали:

Скажем так, насколько я в курсе, для решения подобных задач используется так называемый R-индекс. Я понаслышке знаком с этой областью; вкратце, это дерево переменной высоты, в котором каждый узел покрывает некую область пространства (отрезок в одномерном случае). То есть часть прямой, покрытая отрезками, делится на несколько меньших отрезков, те — на еще меньшие итп; соответственно, можно довольно быстро перейти от корня к отрезкам, "близким" определенной точке. Не знаю, как решается коллизия, если область нельзя разбить на меньшие так, чтобы не разрезать один из реальных отрезков. Проблема в том, что если мы говорим об SQL и не подразумеваем Oracle (где есть возможность создания собственных типов индексов, а r-индексы реализованы) то вряд ли удастся найти эффективное решение на основе имитации R-индекса.

Практически, полагаю, я бы просто сделал партиционированную таблицу (партиции по диапазонам значений левых границ отрезка, субпартиции по диапазонам значений правых границ). В этом случае обычный запрос с условием X between Left and Right эффективно отбросит партиции, в которых заведомо нет нужных отрезков. Эта возможность, насколько я знаю, доступна уже не только в Oracle.

Стандартное решение, о котором всегда следует помнить — выделение стандартных областей. Допустим, есть отрезок с координатами 1,1 ... 2,6. Мы можем сказать, что он пересекает стандартные отрезки [1..2] и [2..3]. Поэтому — вставим во вспомогательную таблицу записи

id, 1
id, 2

где id — идентификатор отрезка. Теперь, желая найти все отрезки, содержащие X, можно выполнить следующий запрос:

select
  p.id,
  p.left,
  p.right
from
  MainTable p,
  ServeTable s
where 
  s.value = trunc ( :x ) and
  s.id = p.id and
  :x between p.left and p.right

В этом случае довольно просто построить пример, где этот метод будет намного эффективнее простого поиска по одной таблице и столь же легко построить пример, где он будет намного менее эффективным.