в качестве ключей выступают сигнатуры
В случает полнотекстового поиска, в качестве ключей выступают сигнатуры - сигнатуры документов находятся в концевых узлах, а во внутренних узлах находятся сигнатуры, которые удовлетворяют основному правилу дерева - родительская сигнатура содержит в себе сигнатуры всех потомков, т.е. она является наложением (суперпозицией) всех сигнатур потомков ( наподобие тому, как получалась сигнатура документа). Поисковый запрос аналогично документу преобразовывается в поисковую сигнатуру и поиск происходит сравнением ее с сигнатурами в узлах в дереве.
Из-за использования суперпозиции поиск по дереву может ответить однозначно только на то, что поисковая сигнатура точно не содержится в какой-либо сигнатуре, что позволяет не рассматривать не только эту сигнатуру, но и все поддерево под ней, что и приводит к значительному ускорению поиска. Например, для сигнатуры 11011000 правую ветку можно точно не рассматривать, однако она может находиться в левой ветке.
ROOT 11011011
Internal nodes: 11011001 10010011 | | Leaves: 11010000, 11010001, 11011000 10010010,10010001
Очевидно, что чем больше глубина дерева, тем больше вероятность того, что сигнатура вырождается, т.е., начинает состоять из одних '1', а это приводит к тому, что приходится просматривать много веток и поиск замедляется. В предельном случае, когда сигнатура состоит из одних '1', она становится бесполезной.
Найденные результаты приходится дополнительно проверять на наличие "false drops", т.е., проверять сами исходные документы, действительно ли они удовлетворяют поисковому запросу, что требует произвольного доступа к "heap" (таблице) и это сильно сказывается на производительности. Степень неоднозначности (lossiness), а следовательно и производительность GiST-индекса, зависит от кол-ва уникальных лексем и количества документов, что ограничивает применимость этого индекса для больших коллекций.
Но это не вся правда о GiST-индексе ! На самом деле, в листьях могут храниться не сигнатуры, а сами tsvector-а, если они не превышают TOAST_INDEX_TARGET байт, что-то около 512 байт. В этом случае попадание является точным и проверять ничего не надо. К сожалению, пока нет возможности индексу сказать какое было попадание, но в будущем, когда появится такая возможность, эта оптимизация может очень хорошо работать для новостных сайтов, где документы не очень большие. Чтобы изучить GiST-индекс, можно воспользоваться специальным модулем Gevel [GEVEL], который выдает полезную информацию об индексе. Вот пример такой выдачи для индекса gist_idx_50 для базы, которая содержит небольшие сообщения. Обратите внимание, что листья содержат как сами tsvector-а, так и сигнатуры, а внутренние ноды - только сигнатуры.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий