почтовый индекс тип данных
Используем почтовые индексы в своём приложении во благо
Я думаю, что на многих сайтах пользователя спросят его физический адрес. Для доставки ли, для отсылки бумажного спама уведомлений ли. И, в общем-то — это мелочь. Вбил индекс, Москва, область, район, село, улица, дом, квартира. Казалось бы, что тут упрощать, каждый вроде помнит свой адрес, трудно ли его вбить? Но дьявол, как всегда, кроется в мелочах: пользователь опечатывается в адресе, посылка уходит не туда, лучи «добра» идут вам в обратную связь и вообще жизнь плохеет.
И она есть! Всамделишняя, электронная и, главное, официальная база индексов от Почты России.
Встречайте: vinfo.russianpost.ru/database/ops.html
База доступна в уже диковинном для молодых разработчиков формате DBF и регулярно (два раза в месяц) обновляется.
Конечно, по подробности эта база до ФИАС недотягивает, но, стоит отдать должное, она гораздо проще (всего одна таблица!), поэтому, если вам не нужна точность до улицы и дома, а хватит только населённого пункта — вам сюда.
Прикручиваем счастье к… ну, давайте к сайту.
Итак, радостно качаем базу и думаем, как же её впихнуть в используемый нами КакойТамУНасСовременныйSQL (а то и НеSQL).
Ищем в гугле, ищем в яндексе, ищем в apt-cache, последний нам радостно и выдаёт:
Здорово-то как! Я использую Postgres и конвертировать буду в него. В базе используется ещё досовская кодировка, так что призовём на помощь iconv. Кстати, самые свежие версии pgdbf (>= 0.6.2) сами шаманством владеют и iconv призывают, но до убунтовского репозитория они ещё не добрались.
Что же, теперь надо заставить это работать.
Я использую Ruby on Rails, на её примере и покажу. Кто рельсы не понимает, может пролистать.
Cоздаём модель, которая будет нашу информацию из базы данных и представлять в приложении
В миграцию вдумчиво копируем структуру таблицы из оригинальной базы, делаем индекс первичным ключом:
Слегка настраиваем модель:
Делаем простенький контроллер, который нам почтовый индекс в json-формате отдаст:
Прописываем в config/routes.rb маршрут, по которому приложение нам отдаст желанные индексы:
И, главное: html и javascript, которые и сделают всю магию для пользователя.
Javascript-код (очень подробный, с уведомлением пользователя, отловом ошибок и исправлением индекса)
И, вуаля, при вводе индекса нам автоматом подставляется область, город и так далее. Заодно, бонусом, мы можем исправлять устаревшие индексы на актуальные (очень часто у людей записаны адреса родственников с уже безнадёжно устаревшими индексами).
Резюме
Плюсы: простота внедрения, использования и поддержания в актуальном состоянии, малый вес
Минусы: невысокая подробность (только до населённого пункта), ВСЕ ГОРОДА КАПСОМ, ПОЧТА РОССИИ, ЗАЧЕМ?
Подробно о типах данных
Правильный выбор типов данных — важный этап проектирования таблиц
В следующих выпусках рубрики «T-SQL для начинающих» будет рассказано о применении синтаксиса T-SQL для построения таблиц. Но прежде чем начинать строить таблицы, необходимо поговорить о типах данных. Для каждого столбца таблицы должен быть определен некоторый тип данных, например, целые (integer) или символьные (character). Это позволяет системе в последующем контролировать данные, которые будут помещаться в этот столбец. В предлагаемой статье автор рассматривает предусмотренные в системе типы данных и рассказывает о том, как создавать собственные типы данных. Подобные дополнительные типы данных следует создать до того как начнется построение таблиц, ведь при создании таблиц могут понадобиться ссылки на эти типы данных. Определяемые пользователями типы данных позволят существенно усилить контроль над данными и повысить их целостность, особенно в проектах, в которых с базами данных параллельно работают несколько разработчиков.
Столбцам необходимы типы данных
При создании таблицы необходимо указать тип данных для каждого столбца. Любые данные, помещаемые в столбец, должны отвечать этому типу данных. В некоторых случаях следует указывать и допустимую длину данных в столбце. В листинге 1 приведен оператор SQL, который создает таблицу авторов Authors в базе данных публикаций Pubs, спользуя только предусмотренные в системе типы данных.
Большинство столбцов в этой таблице являются текстовыми полями. Номер телефона, обозначение штата и почтовый индекс всегда имеют постоянную длину, поэтому соответствующие им столбцы phone, state и ZIP удобнее объявить символьными (char). Имя автора, его адрес и город, где он живет, могут различаться по длине, поэтому для них предпочтительнее использовать тип символьных данных переменной длины (varchar). Столбец contract с информацией о наличии контракта с автором, в котором данные представляются в форме да/нет, целесообразно отнести к двоичному типу данных bit, у которого имеется два возможных значения — 0 и 1. Теперь остановимся подробнее на системных типах данных.
Типы данных, предусмотренные в системе
В версии SQL Server 6.0 определено 19 типов данных, а в версии SQL Server 7.0 добавлено еще 4 типа для удобства работы с закодированными с помощью Unicode данными, а также для поддержки приложений, основанных на использовании хранилищ данных. Каждый тип данных имеет ряд разновидностей, отличающихся возможным набором значений. Знание этих значений облегчит выбор подходящего типа данных.
Символьные данные
Символьные данные типа char предсавляют собой один из наиболее распространенных типов данных. К этому типу относятся такие символьные данные, как имена или адреса. В версии SQL Server 6.5 длина любого столбца с символьными данными ограничивалась 255 знаками. Если же информация оказывалась длиннее, к примеру, если в столбец предполагалось вводить свободный комментарий по поводу контракта, то тогда следовало использовать текстовый тип данных (text). В SQL Server 7.0 это ограничение отменено, так что символьное поле может содержать до 8000 байтов. Верхняя граница обусловлена размером страницы памяти, поскольку ни одна запись не может располагаться в памяти на нескольких страницах. В тех случаях, когда для столбца определен тип данных char, данные следует помещать в одинарных кавычках, как показано в следующем примере:
Как отмечалось в статье «Работа с символьными данными», помещенной в майском номере журнала, можно выбрать символьный тип данных либо фиксированной длины, char, либо переменной длины, varchar. Фиксированный размер оказывается предпочтительным в тех случаях, когда данные имеют одинаковую или сходную длину, например, при вводе идентификатора автора (часто в этом качестве используют индивидуальный номер системы социальной безопасности, что, кстати, является плохим примером для подражания). В большинстве ситуаций применение переменной длины данных не приводит к сколько-нибудь заметному увеличению времени обработки. В то же время фамилия автора может быть очень длинной, так что использование типа varchar оказывается вполне оправданным. Применительно к подавляющему большинству фамилий фиксированная длина поля означает потерю значительного объема памяти, поэтому лучше использовать тип данных varchar. При выборе того или иного типа данных всегда следует искать компромисс с учетом двух аспектов: с одной стороны, потери полезного объема памяти при использовании данных фиксированной длины, а с другой стороны, увеличения времени обработки в случае применения данных переменной длины.
SQL Server 7.0 поддерживает набор символов Unicode. В связи с этим, чтобы воспользоваться всеми преимуществами, предоставляемыми расширенными возможностями Unicode, необходимо было ввести дополнительный тип данных.Если вам захочется использовать символьные данные Unicode, то следует указать тип данных Nchar или, если это информация переменной длины, то Nvarchar. При вводе данных Unicode их следует заключать в одиночные кавычки, причем непосредственно перед ними необходимо поставить заглавную латинскую букву N. Если в рассмотренном ранее примере имя автора отнесено к типу данных Unicode, то предыдущий оператор обновления примет следующий вид:
Ограничение максимальной длины информации при работе с типом данных Unicode составляет 4000 знаков. Это объясняется тем, что для хранения каждого символа Unicode требуется два байта памяти. Поэтому на стандартную страницу памяти размером 8К можно поместить в два раза меньше символов Unicode, чем при использовании обычных символов.
Целые
Точные числовые данные
Если приложение таково, что необходимо получать из базы данных числовое значение в строго указанном формате, то для этого следует выбрать один из точных числовых типов данных. Существуют два точных числовых типа данных: десятичный (decimal) и числовой (numeric), которые по существу совпадают друг с другом. Для них можно задать требуемые точность p и масштаб s в формате decimal (p,s). Точность представляет собой число значащих символов по обе стороны от десятичной запятой, а масштаб — количество символов справа от нее. Например, число 123,4567 можно хранить в столбце, для которого тип данных задан в виде (7,4). Если число, которое должно быть помещено в столбец с точным числовым типом данных, содержит больше десятичных знаков, чем указано в типе данных, то такое число округляется до требуемой точности. Числовые типы данных могут использовать для хранения значений от 2 до 17 байтов.
Приближенные числовые данные
Некоторые числа нельзя точно представить в десятичном виде с ограниченным числом знаков, например, одну треть или число пи. Для записи таких чисел используются действительный (real) или плавающий (float) типы данных. Данные действительного типа хранятся с точностью от 1 до 7 знаков. Плавающий формат, который иногда называют еще форматом двойной точности, может хранить числа, содержащие от 8 до 15 значащих цифр. Действительный и плавающий типы данных применяются в научных приложениях для хранения чисел, не требующих точного двоичного выражения. Одна-две последние цифры могут не вполне точно сохраняться при преобразованиях в двоичный формат. Поэтому такие числа не следует использовать в операциях точного сравнения, применяемых для формулирования условий оборота WHERE.
Двоичные
Предположим, что в базе данных необходимо хранить двоичную информацию. В этой ситуации имеется выбор между двумя форматами представления: c фиксированной или переменной длиной. Данным фиксированной длины соответствует тип данных binary, а двоичным данным переменной длины соответствует тип данных varbinary.
Денежные
В SQL Server и дата и время хранятся в одном столбце, так что если с помощью функции GETDATE() запросить текущую дату, то при этом система сообщит и время. Для дат применяются два типа данных, datetime и smalldatetime. Тип данных smalldatetime охватывает период времени от 1 января 1900 года до 6 июня 2079 года и включает время с точностью до минуты. Такого диапазона достаточно для подавляющего большинства проектов. Тип данных datetime годен для использования до 31 декабря 9999 года (это следует учитывать при решении проблемы 10К года). Начало диапазона этого типа данных датируется 1 января 1753 года. Почему 1753? Это связано с переходом с юлианского на грегорианский календарь. Несмотря на то, что грегорианский календарь был предложен некоторое время назад, процесс его принятия продолжался в течение приблизительно 30 лет. На протяжении этого периода некоторые страны уже приняли грегорианский, а другие еще нет. Поэтому для того, чтобы дата воспринималась однозначно, надо знать географическое положение объекта. Кроме того, год начинался не 1 января, а 1 марта. Поэтому такая дата, как 15 января 1792 года, может интерпретироваться и как середина первого месяца 1492 года, и как середина 11-го месяца 1793 года. Создатели SQL Server решили не рисковать, и поэтому приняли решение не воспринимать даты, относящиеся к периоду времени до начала 1753 года. Следует отметить также, что тип данных datetime показывает тысячные доли секунды, хотя точность гарантируется только до 1/300 части секунды.
Тексты и образы
Специальные типы данных
Некоторые типы данных трудно отнести к какой-либо категории. Один из таких типов — битовые данные (bit). Это целое число, которое может принимать только два значения — 0 и 1 (в одном байте можно хранить восемь подобных величин). Битовые значения часто применяются в качестве флагов, принимающих значения истина или ложь. Их можно использовать, например, для хранения сведений о том, заключен ли контракт с автором, или принадлежат ли его книги к бестселлерам, или для чего-либо аналогичного. Одно незначительнгое отличие версии SQL Server 7.0 состоит в том, что для столбцов с битовыми данными теперь разрешены и неопределенные значения, в то время как в версии SQL Server 6.5 допустимы были только значения 0 и 1.
Для внутренних целей в SQL Server используется тип данных метка времени (timestamp). Этот тип данных генерирует уникальное значение, которое обновляется каждый раз, когда модифицируется информация в строке таблицы. Метки времени являются внутренними значениями, поддерживаемыми в SQL Server. Они не соответствуют реальным датам и времени.
В SQL Server 7.0 введены два новых типа данных, которые более подробно будут рассмотрены в последующих публикациях. тип данных уникальный идентификатор (uniqueidentifier) позволяет присвоить столбцу уникальное в глобальном масштабе значение. Глобальная уникальность означает неповторимость не только в рамках конкретной базы данных или в пределах одного компьютера, но вообще везде. Этот тип данных играет важную роль при работе с хранилищами данных, когда информация собирается в него из множества разнообразных источников. Тип данных курсор (cursor) применяется для переменных курсора. Использование курсора — отдельная большая тема, которой автор собирается посвятить целую статью.
Определяемые пользователями типы данных
SQL Server позволяет пользователям определять собственные типы данных, которые являются комбинацией системных типов данных. Как правило, они базируются на системном типе данных определенной длины (имеются в виду числовые и символьные значения), для которого назначаются правила и значения по умолчанию. Например, можно определить тип данных Почтовый индекс как char(10), а тип данных Телефонный номер как char(14). Тогда тип данных Почтовый индекс будет гарантировать целостность форматов почтовых индексов во всех столбцах, для любого клиента, поставщика, служащего или контактного лица где угодно по всему миру.
Но в тех случаях, когда пользователь хочет создать тип данных, имея лишь набросок желаемого, SQL Server оказывается не слишком полезным. К примеру, нельзя создать новый тип данных, обладающий целым набором связанных с ним свойств, для таких понятий как широта или долгота для географических приложений. Ведь для него пришлось бы прибегнуть к методам сферической тригонометрии для вычисления расстояния между двумя точками. Возможно, когда-нибудь SQL Server станет настолько гибким, что сможет помочь и в таких ситуациях.
На данный момент добавлять новые типы данных можно с помощью SQL Server Enterprise Manager или из анализатора запросов Query Analyzer (в версии SQL Server 6.5 это производится из окна ISQL/w). Каждый тип данных, который добавляют пользователи, действует только в пределах конкретной базы данных. Если же необходимо создать тип данных для всех баз, то его следует поместить в базу данных моделей Model. С момента создания в этой базе данных новый тип данных будет доступен во всех остальных базах. Существует другой способ решения этой проблемы — написать сценарий или сгенерировать его с помощью утилиты генерации сценариев Generate SQL Script, входящей в состав SQL Server. Тогда этот сценарий можно будет запускать из любой базы данных. В Enterprise Manager следует дважды щелкнуть правой кнопкой мыши на названии базы данных, а затем последовательно выбрать из меню Все задачи (All tasks), Генерировать сценарий SQL (Generate SQL Script) и наконец, выбрать пункт создания сценария для всех типов данных.
В окне Enterprise Manager следует выбрать пункт Базы данных (Databases), выбрать конкретную базу из списка, а затем перейти к пункту Определяемые пользователем типы данных (User-Defined Data Types). Щелкните правой кнопкой мыши и выберите пункт Свойства новых определяемых пользователем типов данных (New User-defined Datatype Properties). После этого приступайте к определению типа данных.
Как принято в SQL Server, добавить новый тип данных можно также с помощью анализатора запросов Query Analyzer. Обратите внимание на то, что кавычки заключают название системного типа данных, но вокруг названия вновь создаваемого типа данных их не ставят. Кроме того, полезно сразу указать, допускает ли создаваемый тип данных неопределенные значения. Для конкретного столбца можно будет в последующем переопределить эту установку, но первоначальная спецификация допустимых возможностей облегчает введение стандартов. А это и является той целью, ради которой вводятся новые типы данных.
При определении типов данных оператор создания таблицы может выглядеть так, как показано на листинге 2. Для тех столбцов, к которым применяются определенные пользователем типы данных, не требуется указывать длину помещаемых в него сведений, — ведь она уже была определена при создании типа данных. Можно также не сообщать системе о том, допустимы ли в рассматриваемом столбце неопределенные значения, поскольку это задано в спецификации типа данных. Хотя не повредит включить такое упоминание и в этот оператор.
Выберите правильный тип
Правильный подбор типов данных является частью проектирования таблицы. В SQL Server 6.5 очень трудно изменить свойства столбца после того, как он был создан. В версии SQL Server 7.0 это возможно, но проводить такую процедуру следует с крайней осторожностью.
Индексы в PostgreSQL
Индексы в PostgreSQL
Full Stack Developer в DataArt
В статье я расскажу о предназначении и основах принципов работы объектов баз данных — индексов. На примере СУБД PostgreSQL коротко рассмотрим несколько разных типов индексов и классов задач, для которых они применимы. В конце материала поделюсь ссылками на статьи с более глубоким описанием внутреннего устройства индексов в PostgreSQL.
Статья может быть полезна начинающим разработчикам и студентам, имеющим общие представления о реляционных базах данных, и опытным разработчикам, не сталкивавшимся раньше с индексами и их устройством.
Предназначение индексов
Простейший метод решения задачи поиска записей в базе данных, удовлетворяющих определенному критерию, — полный перебор. Но с ростом количества записей производительность такого подхода будет заметно падать. Для повышения производительности поиска создаются вспомогательные структуры — индексы. Используя индексы, можно существенно поднять скорость поиска, потому что данные в индексе хранятся в форме, позволяющей нам в процессе поиска не рассматривать области, которые заведомо не могут содержать искомые элементы.
Если провести аналогию между базой данных и книгой, индексами можно считать оглавление книги и предметный указатель. Действительно, если бы у нас не было таких «индексов», для поиска конкретной главы или для поиска определения какого-то понятия пришлось бы листать и читать всю книгу целиком, пока не найдем то, что нужно. Имея оглавление и предметный указатель, нам нужно просмотреть существенно меньший объем данных, после чего мы точно узнаем номер страницы книги, на которой находится то, что мы ищем. Индексы в базах данных по сути устроены так же, как оглавление или как предметный указатель книги.
24–25 сентября, Онлайн, Беcплатно
Важно, что использование индексов не только сокращает время поиска в абсолютном выражении, но и уменьшает алгоритмическую сложность процесса поиска. Это значит, что время, необходимое на поиск с помощью индексов, при росте объема базы данных будет расти существенно медленнее, чем при использовании полного перебора.
В качестве примера рассмотрим задачу поиска в списке чисел. Используя перебор элементов списка, в худшем случае, нам придется просмотреть список целиком. Алгоритмическая сложность такого метода — O(n). Но если мы будем хранить наши числа особым образом — отсортированными по возрастанию или по убыванию — сможем использовать алгоритм бинарного поиска.
2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180
Допустим, необходимо определить, содержит ли этот отсортированный список число 158. Для этого:
В итоге метод бинарного поиска дал нам результат всего за три шага. При полном переборе с начала списка нам потребовалось бы 16 шагов. Бинарный поиск имеет алгоритмическую сложность O(log(n)). Используя формулы алгоритмической сложности O(n) и O(log(n)), мы можем оценить, как будет меняться приблизительное количество операций при поиске разными способами с ростом объема данных:
Результат впечатляет. Храня данные в отсортированном виде, мы не только снизили скорость поиска по ним, но и колоссально сократили скорость замедления поиска при росте объема данных.
Использование индексов в базе данных дает аналогичный результат. Принцип работы одного из важнейших индексов в базе данных (индекс на основе B-дерева) основан именно на рассмотренном нами выше принципе — возможности хранить данные в отсортированном виде.
Индексы в PostgreSQL
В базах данных, таких как PostgreSQL, индекс формируется из значений одного или нескольких столбцов таблицы и указателей на строки этой таблицы.
SELECT * FROM table_name WHERE P(column_name) = 1
Предикат P может вычисляться от значения нескольких колонок. В этом случае для ускорения запроса используется индекс, построенный не для одной колонки, а для нескольких. Такие индексы называют составными.
Если мы хотим ускорить выполнение запроса, условие которого вычисляется по одной или нескольким колонкам, в PostgreSQL нам необходимо создать для этих колонок индекс с помощью команды CREATE INDEX :
Эта команда имеет большой перечень дополнительных параметров, с полным списком которых можно ознакомиться в документации.
Например, индекс может поддерживать ограничение на уникальность и не допускать появления в таблице нескольких строк, значения индексируемых столбцов у которых совпадают. Для этого при создании индекса указывают ключевое слово UNIQUE :
Или мы можем создать индекс не по полю таблицы, а по функции или скалярному выражению с одной или несколькими колонками таблицы (такие индексы называют функциональными или индексами по выражению). Это позволяет быстро находить данные в таблице по результатам вычислений. Например, мы хотим ускорит запрос регистронезависимого поиска по текстовому полю:
CREATE INDEX index_name ON table_name(lower(text_field))
И такой индекс уже может успешно применяться для ускорения нашего запроса.
CREATE INDEX index_name ON table_name USING GIST (column_name)
B-tree
Этот тип индекса используется по умолчанию и покрывает очень широкий круг задач (базы данных большинства приложений успешно могут обходиться только индексами на основе B-деревьев).
С помощью B-дерева можно проиндексировать любые данные, которые могут быть отсортированы, т. е. для которых применимы операции сравнения больше/меньше/равно. Сюда можно отнести числа, строки, даты и время, логический тип и любые данные, которые можно ими закодировать.
Какой тип запросов может быть ускорен с помощью B-дерева? На самом деле, практически любой запрос, условие которого является выражением, состоящим из полей входящих в индекс, логических операторов и операций равенства/сравнения. Например:
Выполнение этих и многих других запросов может быть ускорено с помощью B-дерева. Кроме того, индекс на основе B-дерева ускоряет сортировку результатов, если в ORDER BY указано проиндексированное поле.
Принцип работы индекса на основе B-дерева основан на рассмотренном нами ранее алгоритме бинарного поиска: т. к. все значения упорядочены, мы можем быстро определять области, в которых гарантированно не может быть данных, удовлетворяющих запрос, существенно снижая таким образом количество перебираемых записей.
Однако хранить индекс просто в виде отсортированного массива мы не можем, т. к. данные могут модифицироваться: значения могут меняться, записи — удаляться или добавляться. Чтобы эффективно поддерживать хранение индексируемых данных в отсортированном виде, индекс хранят в виде сбалансированного сильно ветвящегося дерева, называемого B-деревом (B-tree).
Корневой узел B-дерева содержит в упорядоченном виде несколько значений из общего набора, допустим, t элементов. Тогда все остальные элементы можно распределить по t+1 дочерним поддеревьям по следующему правилу:
Каждое поддерево, в свою очередь, тоже является B-деревом, имеет корневой элемент и строится далее рекурсивно по такому же принципу.
За счет того что элементы в каждом узле отсортированы, при поиске мы сможем быстро определить, в каком поддереве может находиться искомый элемент, и не рассматривать вообще другие поддеревья. Допустим, нам нужно найти число 67:
Таким образом, при поиске в B-дереве необходимо максимум h раз выполнить линейный или бинарный поиск в относительно небольших списках, где h — это высота дерева. Т.к. B-дерево — сильно-ветвящееся и сбалансированное (т. е. при его построении и модификации применяются алгоритмы, сохраняющие его высоту минимальной, см. статью), число h обычно совсем невелико, и при росте общего количества элементов оно растет логарифмически. Как мы уже видели ранее, это приносит очень хорошие результаты.
Кроме того, важное и полезное свойство B-дерева при его использовании в СУБД — возможность эффективно хранить его во внешней памяти. Каждый узел B-дерева обычно хранит такой объем данных, который может быть эффективно записан на диск или прочитан за одну операцию ввода-вывода. B-дерево даже может не помещаться целиком в оперативной памяти. В этом случае СУБД может держать в памяти только узлы верхнего уровня (которые вероятно будут часто использоваться при поиске), читая узлы нижних уровней только при необходимости.
Индекс на основе B-дерева может ускорять запросы, которые используют не целиком входящие в индекс поля, а любую часть, начиная с начала. Например, индекс может ускорить запрос LIKE для поиска строк, которые начинаются с заданной подстроки:
SELECT * FROM table_name WHERE text_field LIKE ‘start_substring%’
Если индекс построен по нескольким колонкам, он может ускорять запросы, в которых фигурируют одна или несколько первых колонок. Поэтому важен порядок, в котором мы указываем колонки при создании индекса. Допустим, у нас есть индекс по колонкам col_1 и col_2. Тогда он может использоваться в том числе для ускорения запроса вида:
SELECT * FROM table_name WHERE col_1 = 123
И нам не нужно создавать отдельный индекс для колонки col_1. Будет использоваться составной индекс (col_1, col_2).
Однако для запроса только по колонке col_2 такой составной индекс уже использовать не получится.
Подробнее, как индекс на основе B-дерева реализован в PostgreSQL, см. статью.
GiST и SP-GiST
GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree. Но b-tree применимо только к тем типам данных, для которых имеет смысл операция сравнения и есть возможность упорядочивания. Но PostgreSQL позволяет хранить и такие данные, для которых операция упорядочивания не имеет смысла, например, геоданные и геометрические объекты.
Тут на помощь приходит индексный метод GiST. Он позволяет распределить данные любого типа по сбалансированному дереву и использовать это дерево для поиска по самым разным условиям. Если при построении B-дерева мы сортируем все множество объектов и делим его на части по принципу больше-меньше, при построении GiST индексов можно реализовать любой принцип разбиения любого множества объектов.
Например, в GiST-индекс можно уложить R-дерево для пространственных данных с поддержкой операторов взаимного расположения (находится слева, справа; содержит и т. д.). Такой индекс доступен в PostgreSQL и может быть полезен при разработке геоинформационных систем, в которых возникают запросы вида «получить множество объектов на карте, находящихся от заданной точки на расстоянии не более 1 км».
SP-GiST похож GiST, но он позволяет создавать несбалансированные деревья. Такие деревья могут быть полезны при разбиении множества на непересекающиеся объекты. Буквы SP означают space partitioning. К такому типу индексов можно отнести kd-деревья, реализация которых присутствует в PostgreSQL. Его, как и R-дерево, можно использовать для ускорения запросов геометрического поиска. Свойство непересечения упрощает принятие решений при вставке и поиске. С другой стороны, получающиеся деревья, как правило, слабо ветвисты, что усложняет их эффективное хранение во внешней памяти.
Кроме того, GiST и SP-GiST могут служить своеобразным фреймворком, облегчающим расширение PostgreSQL и добавление в него совершенно новых видов деревьев для индексации новых типов данных.
Подробнее об алгоритмах, лежащих в основе R- и kd-деревьев см. раз и два, а об их реализации и использовании в PostgreSQL см. в этой и этой статье.
Заключение
Индексы — важнейший инструмент баз данных, ускоряющий поиск. Он не бесплатен, создавать много индексов без лишней необходимости не стоит — индексы занимают дополнительную память, и при любом обновлении проиндексированных данных СУБД должна выполнять дополнительную работу по поддержанию индекса в актуальном состоянии.
PostgreSQL поддерживает разные типы индексов для разных задач: