Мы уже познакомились с механизмом индексирования PostgreSQL и с интерфейсом методов доступа, и рассмотрели хеш-индексы, B-деревья, индексы GiST и SP-GiST. А в этой части займемся индексом GIN.
GIN
— Джин?.. Джин — это, кажется, такой американский спиртной напиток?..
— Не напиток я, о пытливый отрок! — снова вспылил старичок, снова спохватился и снова взял себя в руки. — Не напиток я, а могущественный и неустрашимый дух, и нет в мире такого волшебства, которое было бы мне не по силам.
Лазарь Лагин, «Старик Хоттабыч».
Gin stands for Generalized Inverted Index and should be considered as a genie, not a drink.
README
Общая идея
GIN расшифровывается как Generalized Inverted Index — это так называемый обратный индекс. Он работает с типами данных, значения которых не являются атомарными, а состоят из элементов. При этом индексируются не сами значения, а отдельные элементы; каждый элемент ссылается на те значения, в которых он встречается.
Хорошая аналогия для этого метода — алфавитный указатель в конце книги, где для каждого термина приведен список страниц, где этот термин упоминается. Как и указатель в книге, индексный метод должен обеспечивать быстрый поиск проиндексированных элементов. Для этого они хранятся в виде уже знакомого нам B-дерева (для него используется другая, более простая, реализация, но это не существенно). К каждому элементу привязан упорядоченный набор ссылок на строки таблицы, содержащие значения с этим элементом. Для выборки данных упорядоченность не принципиальна (порядок сортировки TID-ов не несет в себе особого смысла), но она важна с точки зрения внутреннего устройства индекса.
Читать полностью »
