Комментарии 11
Красиво. А пробовали индексировать более чем двумерные непрерывные множества? Или в непрямоугольных координатах?
Многомерный поиск (в любых координатах), если он приводит к неравномерности распределения, лучше не пробовать на Igloo. Представьте, что у Вас четыре объекта по углам и миллиард кучкуется в центре. Для того, чтобы найти любой объект из центра придется перебрать их все.
Впрочем, эта ситуация разруливается самоподобными индексами.
Впрочем, эта ситуация разруливается самоподобными индексами.
А не поможет ли в этом случае комбинирование с RTree?
И комбинировать не надо, поможет.
Но R-дерево оно заметно тяжелее нежели простое B-дерево.
Но R-дерево оно заметно тяжелее нежели простое B-дерево.
В среднем случае комбинирование поможет сократить overhead от дерева, но оставит выигрыш по скорости. В худшем да, будет тяжелая конструкция, хотя думаю можно при желании упаковать как-нибудь, благо модификаций немало.
Смотря что понимается под комбинированием. Можно хранить два индекса, тогда по B-дереву быстро оценить объем перебора и переключиться на R-дерево. А стоит ли оно того?
Покрыть весь мир решеткой и для каждой ячейки держать свое мини дерево. Таким образом по решетке выбираем нужный набор, а далее по дереву.
Природу не обманешь :) Пусть у нас 1000Х1000 ячеек, большинство из них слабозаполнены — 1..2 объекта, некоторые заполнены сильно. Миллион рутовых страниц R-дерева вынь да положь. Плюс еще адреса этих страниц хранить надо. Да транзакциями всё это покрыть. А честное R-дерево просто достроится там где надо. Но приз моих личных симпатий принадлежит обычному B-дереву с самоподобным ключем. При правильной работе с ним оно и для универсальных данных превосходит R-дерево за счет простоты и компактности.
Но это уже совсем другая история.
Но это уже совсем другая история.
Пробовали, но не именно таким методом.
Для небесных объектов лучше всего подошли бы трехмерные координаты (как если бы их нанести на сферу). Тогда нет искажений к полюсам, но сложней задавать поисковый экстент.
Для небесных объектов лучше всего подошли бы трехмерные координаты (как если бы их нанести на сферу). Тогда нет искажений к полюсам, но сложней задавать поисковый экстент.
Спасибо за пример использования самоподобных кривых!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Индексируем небо