13 521
правка
Изменения
м
→Индексные структуры
Существует два основных применения индексов для поиска:
* Поиск ближайшего соседа (точки, наиболее близкой к заданной) или нескольких ближайших соседей. Здесь наиболее эффективны производные R-дерева, так как их узлы содержат границы областей, для каждого узла можно вычислить максимально возможное расстояние от искомого элемента, и соответственно, узлы можно просматривать сразу в нужном порядке.
* Поиск по заданной области, требуемый как раз в нашем случае. В нашем случае не требуется ни внешнее хранение, ни обновляемость индекса(с ней у R-деревьев получше), поэтому более эффективными оказываются разделяющие деревья.
=== K-D дерево ===