Раніше (1, 2) ми обґрунтували і продемонстрували можливість існування
просторового індексу, що володіє всіма плюсами звичайного B-Tree — індексу та
не поступається по продуктивності індексу на основі R-Tree.
Під катом узагальнення алгоритму на тривимірний простір, оптимізації та бенчмарки.

Читати далі →

Просторовий індекс для PostgreSQL на основі Z-order (vs R-tree), продовження


минулий раз ми прийшли до висновку, що для ефективної роботи просторового індексу на основі Z-order необхідно зробити 2 речі:
  • ефективний алгоритм отримання подинтервалов
  • низькорівневу роботу з B-деревом
Ось саме цим ми і займемося під катом.
Читати далі →

Про Z-оrder і R-дерево

image
Індекс на основі Z-order кривої в порівнянні з R-деревом має масу переваг, він:
  • реалізований як звичайне B-дерево, а ми знаємо що
  • сторінки B-дерева мають кращу заповнюваність, крім того,
  • Z-ключі самі по собі більш компактні
  • B-дерево має природний порядок обходу, на відміну від R-дерева
  • B-дерево швидше будується
  • B-дерево краще збалансовано
  • B-дерево зрозуміліше, не залежить від евристики поділу/злиття сторінок
  • B-дерево не деградує при постійних змінах
  • ...
Втім, у індексів на основі Z-order є і недолік — порівняно низька продуктивність :). Під катом ми спробуємо розібратися з чим пов'язаний цей недолік і чи можна щось з цим зробити.

Читати далі →

Про тривимірному Z-order замовте слово


«Давним-давно, здається, минулої п'ятниці» автору потрапила на очі стаття, в якій порівнюються різні популярні методи індексації небесних об'єктів. Через нерівного дихання до цієї теми довелося розбиратися в тонкощах і робити висновки.

Ви запитаєте: «Кому взагалі цікаві ці небесні об'єкти?» і навіть: «Ну і при чому тут 2ГІС?» і почасти будете праві. Адже методи просторового індексування є універсальною цінністю.

Звичайно, маючи справу з геоданными, ми працюємо з локальної проекцією на площину і тим самим відмахуємося від спотворень. В масштабах планети це зробити важче — починають випирати астрономічні проблеми.
Що стосується обсягів даних, вже зараз в OSM більше 4 млрд точок і 300 млн доріг. Це порівнянно з масштабами, характерними для зоряних об'єктів. Та й крім усього іншого, зоряні атласи — відмінний стенд для розробки та налагодження просторових алгоритмів.

Обіцяні тонкощі і висновки під катом.

Читати далі →