Comments 10
Для полноты картины таки стоит проверить решение в лоб с составным индексом
create index test_points_x_y on test_points (x, y);
Очень хорошо, но есть пара проблем:
1. Z-code это, фактически linear quad-tree. Не R. И совсем не B. Все, что вы обьявили бонусами в начале статьи — не работает. Никакой балансировки нет. И дерева никакого нет. Это что-то среднее между фракталом и кривой – spatial filling curve, И их много бывает разных. Смысл один — понижают размерность.
2. Попробуйте Hilbert. Считать его сложнее, но более «близкие» значения в нем расположены «ближе»
3. «Секрет» работы Z-value-ii хорошо описан в интернетах как BIGMIN/LITMAX (https://en.wikipedia.org/wiki/Z-order_curve#Use_with_one-dimensional_data_structures_for_range_searching)
В общем крайне рекомендую активно дружить с этой математикой. Она реально хорошо работает, но надо понимать ограничения.
И не забывать — Z это точка. В то время как R-tree продолжает жрать кактус.
1. Z-code это, фактически linear quad-tree. Не R. И совсем не B. Все, что вы обьявили бонусами в начале статьи — не работает. Никакой балансировки нет. И дерева никакого нет. Это что-то среднее между фракталом и кривой – spatial filling curve, И их много бывает разных. Смысл один — понижают размерность.
2. Попробуйте Hilbert. Считать его сложнее, но более «близкие» значения в нем расположены «ближе»
3. «Секрет» работы Z-value-ii хорошо описан в интернетах как BIGMIN/LITMAX (https://en.wikipedia.org/wiki/Z-order_curve#Use_with_one-dimensional_data_structures_for_range_searching)
В общем крайне рекомендую активно дружить с этой математикой. Она реально хорошо работает, но надо понимать ограничения.
И не забывать — Z это точка. В то время как R-tree продолжает жрать кактус.
PS: Еще в интернетах можно найти множество более быстрых функций построения Z-кодов
PPS: Некоторые модификации R-tree сами по Z строятся
PPPS: Вэлкам ту зе клаб!
по П.1 Z-code — это число, а числа в данном случае мы укладываем в B-дерево.
То, что вы (по видимому) имели ввиду, называется k-d-деревья и это совсем другая история.
И не забывать — Z это точка, прямоугольник — четырехмерная Z точка.
То, что вы (по видимому) имели ввиду, называется k-d-деревья и это совсем другая история.
И не забывать — Z это точка, прямоугольник — четырехмерная Z точка.
1. В принципе да, на стороне БД это уложиться в B-дерево. Получается достаточно честно. Смотрите на это без БД.
2. Кстати – Z-code, который иногда еще называют «bit interleaving», в принципе KD. Каждый бит режет пространство своей плоскостью.
3. Только вот поиск в окрестности такой четырех-мерной точки будет немного затруднен :)
В общем случае Z(и компания) просто позволяет в начале как-то уложить в некий интервал данные, а потом в нем искать.
При это самый «быстрый» поиск по кодам, когда вам нужна конкретная «ячейка» виртуального quadtree, лучше всего (технически) работает через маску. Вы говорите с чего код должен начинаться – фиксируете первые шаги погружения в дерево, а после некого момента «отпускаете» код, позволяя ему свободно менятся.
Если весь код 4 бита, те 2 уровня, то фиксация 0b1000 с маской 0b0111 матчится на все элементы в левом(или правом) поддереве, те между 0b1000 и 0b1111.
В принципе — это — возможность использовать эти «числа» как NestedSet — одна из основых фичей этих кривых. За прошедшие годы для разных spatial filling придумали очень много наркомании. Текстуры в памяти видеокарты по ним разложены. Gray Code, на котором 99% электроники работает — тоже spatial filling.
К своему сожалению — я далеко не самый лучший рассказчик, но быть может одна старая статейка немного поможет понять, что же я имел в виду.
2. Кстати – Z-code, который иногда еще называют «bit interleaving», в принципе KD. Каждый бит режет пространство своей плоскостью.
3. Только вот поиск в окрестности такой четырех-мерной точки будет немного затруднен :)
В общем случае Z(и компания) просто позволяет в начале как-то уложить в некий интервал данные, а потом в нем искать.
При это самый «быстрый» поиск по кодам, когда вам нужна конкретная «ячейка» виртуального quadtree, лучше всего (технически) работает через маску. Вы говорите с чего код должен начинаться – фиксируете первые шаги погружения в дерево, а после некого момента «отпускаете» код, позволяя ему свободно менятся.
Если весь код 4 бита, те 2 уровня, то фиксация 0b1000 с маской 0b0111 матчится на все элементы в левом(или правом) поддереве, те между 0b1000 и 0b1111.
В принципе — это — возможность использовать эти «числа» как NestedSet — одна из основых фичей этих кривых. За прошедшие годы для разных spatial filling придумали очень много наркомании. Текстуры в памяти видеокарты по ним разложены. Gray Code, на котором 99% электроники работает — тоже spatial filling.
К своему сожалению — я далеко не самый лучший рассказчик, но быть может одна старая статейка немного поможет понять, что же я имел в виду.
Спасибо за ссылку, в принципе, я в курсе некоторой части этой магии.
И эту статью рассматривал как вводную для описания алгоритма поиска именно по B-дереву, как самому честному способу хранить одномерные данные в (по большому счету) одномерном дисковом пространстве.
Через недельку — другую, добро пожаловать.
А одна старая статейка найдётся не только у вас :)
И эту статью рассматривал как вводную для описания алгоритма поиска именно по B-дереву, как самому честному способу хранить одномерные данные в (по большому счету) одномерном дисковом пространстве.
Через недельку — другую, добро пожаловать.
А одна старая статейка найдётся не только у вас :)
Я правильно понимаю, что osm использует аналогичный подход (http://wiki.openstreetmap.org/wiki/QuadTiles)?
[Я пока не в теме — разбираюсь. Хочу уточнить что бы унифицировать в своей голове подходы к проблеме, используемые разными людьми и компаниями]
[Я пока не в теме — разбираюсь. Хочу уточнить что бы унифицировать в своей голове подходы к проблеме, используемые разными людьми и компаниями]
Sign up to leave a comment.
Про Z-оrder и R-дерево