Pull to refresh

Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL

SQL *
В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБД
Взглянем?
Total votes 99: ↑96 and ↓3 +93
Views 153K
Comments 41

Поиск почти-дубликатов и геометрия

Algorithms *
Sandbox
Недавно мне попалась задачка на поиск почти-дублей среди большого количества коротких текстов. Поиск готового решения не привел к успеху, а полученное решение оказалось довольно интересным, и я не смог отказать себе в удовольствии поделиться им.

Формулировка


Есть большая база текстов (сотни тысяч текстов). Длины текстов примерно одинаковые, около 250 символов, язык — английский. Некоторые из текстов отредактированы (исправлены опечатки, расставлены запятые и т.п.); таким образом в базе оказывается как оригинальный текст, так и его исправленная копия. Таких пар не очень много, скажем не более 1%. Задача: найти все такие пары.
Читать дальше →
Total votes 14: ↑12 and ↓2 +10
Views 6.9K
Comments 17

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

PostgreSQL *Algorithms *C *Geoinformation services *
image

Индекс на основе Z-order кривой в сравнении с R-деревом имеет массу преимуществ, он:

  • реализован как обычное B-дерево, а мы знаем что
  • страницы B-дерева имеют лучшую заполняемость, кроме того,
  • Z-ключи сами по себе более компактны
  • B-дерево имеет естественный порядок обхода, в отличие от R-дерева
  • B-дерево быстрее строится
  • B-дерево лучше сбалансировано
  • B-дерево понятнее, не зависит от эвристики расщепления/слияния страниц
  • B-дерево не деградирует при постоянных изменениях
  • ...

Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.
Читать дальше →
Total votes 35: ↑34 and ↓1 +33
Views 13K
Comments 10

Z-order vs R-tree, продолжение

PostgreSQL *Algorithms *C *Geoinformation services *

В прошлый раз мы пришли к выводу, что для эффективной работы пространственного индекса на основе Z-order необходимо сделать 2 вещи:

  • эффективный алгоритм получения подинтервалов
  • низкоуровневую работу с B-деревом

Вот именно этим мы и займёмся под катом.
Читать дальше →
Total votes 26: ↑26 and ↓0 +26
Views 7.8K
Comments 9

Z-order vs R-tree, оптимизация и 3D

PostgreSQL *Algorithms *C *Geoinformation services *

Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.
Читать дальше →
Total votes 22: ↑21 and ↓1 +20
Views 5.9K
Comments 0

Проекции? Hет, спасибо

Open source *PostgreSQL *Algorithms *C *Geoinformation services *

Под катом будет небольшая заметка о применении пространственного индекса
на основе zcurve для индексации точечных данных, расположенных на сфере. А так же bencmark-и для PostgreSQL и сравнение с таким же (но совсем другим)
индексом на R-дереве.
Читать дальше →
Total votes 15: ↑15 and ↓0 +15
Views 5.3K
Comments 2

Про интервальные индексы

Open source *PostgreSQL *Algorithms *C *


Под катом будем разбираться нужен ли для индексации интервалов специальный индекс, как быть с многомерными интервалами, правда ли что с 2-мерным прямоугольником можно обращаться как с 4-мерной точкой и т.д. Всё это на примере PostgreSQL.
Читать дальше →
Total votes 8: ↑8 and ↓0 +8
Views 4.9K
Comments 0