Индексирование на основе кривой Пеано-Гильберта?
У меня есть топоры, у,z, 3D-точки, хранящиеся в MySQL, я хотел бы спросить регионы, срезы или точки соседей. Есть ли способ индексировать точки, используя кривые Пеано-Гильберта для ускорения запросов? Или есть более эффективный способ хранения 3D-данных в MySQL?
спасибо Арман.
2 ответа
Лично я никогда не заходил так далеко, но я использовал Z-кривую для хранения 2D точек. Это работало довольно хорошо, и не было необходимости пытаться реализовать кривую Гильберта для лучших результатов.
Это должно позволить вам быстро отфильтровать точки, которые, конечно, не находятся рядом. В худшем случае вам все равно нужно отсканировать более 25% таблицы, чтобы найти точки внутри области.
Чтобы сделать это, нужно разделить x y z в двоичном коде и объединить их в одно значение с помощью кривой. Хотелось бы, чтобы у меня был готов сценарий SQL, но у меня есть только один для 2-й z-кривой, который намного проще сделать.
Редактировать:
Извините, вы, возможно, уже знаете все это и действительно просто ищете примеры SQL, но у меня есть некоторые дополнения:
- Я не уверен, что 25% в худшем случае верно и для трехмерных плоскостей. Это может быть выше, не хватает мозгов прямо сейчас, чтобы сказать вам;).
- Этот тип кривой поможет вам найти диапазоны, где вам нужно искать. Если у вас есть 2 координаты, вы можете преобразовать их в число кривой Гильберта, чтобы узнать, в каком разделе вашей таблицы вам нужно искать элементы, которые точно соответствуют вашему запросу.
- Возможно, вы сможете расширить эту концепцию, чтобы найти соседей, но для того, чтобы использовать кривую, вы все еще "застряли", чтобы посмотреть в диапазонах.
Вероятно, вы можете взять алгоритм для создания геохеша и расширить его до 3-х координат. По сути, вы определяете, что у вас будет мировой куб с возможными трехмерными точками, а затем, когда вы добавляете больше битов, вы сужаете куб. Затем вы последовательно определяете его так, чтобы нижний левый угол имел наименьшее значение, и вы можете выполнять проверки диапазона следующим образом:
XXXXa < the_hash < XXXXz