Раніше (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 є і недолік — порівняно низька продуктивність :). Під катом ми спробуємо розібратися з чим пов'язаний цей недолік і чи можна щось з цим зробити.

Читати далі →