Postgres - статьи



              

Что нужно знать об индексах - часть 2


word signature ---------------- w1 -> 01000000 w2 -> 00010000 w3 -> 10000000 ---------------------- 11010000

В этом примере, '11010000' является сигнатурой документа, состоящего из трех уникальных слов w1,w2,w3. Сигнатура является некоторым компактным представлением документа, что приводит к значительному уменьшению размера коллекции. Кроме того, фиксированный размер cигнатуры сильно облегчает операции сравнения. Все это делает использование сигнатур вместо документов привлекательным с точки зрения производительности.

При поиске, запрос можно аналогичным образом представить в виде сигнатуры и тогда процесс поиска будет заключаться в сравнении сигнатур. Если хотя бы одно положение '1' в сигнатурах не совпадает, то можно с уверенностью утверждать, что документ не содержит поисковый запрос. Однако, если все '1' поисковой сигнатура совпадают с '1' сигнатуры документа, то это означает лишь то, что поисковый запрос может содержаться в документе и это требует проверки с использованием самого документа, а не его сигнатуры. Вероятностый ответ связан с использованием хеширования и суперпозиции. Ниже приводятся несколько примеров поисковых сигнатур.

11010000 - сигнатура документа 00000001 - сигнатура запроса Q1, точно не содержится в документе 01000000 - сигнатура запроса Q2, возможно содержится в документе 01010000 - cигнатура запроса Q3, возможно содержится в документе

Сигнатура Q2 является сигнатурой слова w1 и, таким образом, является правильным попаданием, в то время как сигнатура Q3 - ложным попаданием (false drop), несмотря на то, что она удовлетворяет сигнатуре документа. Ясно, что конечность размера сигнатуры и увеличение количества уникальных слов приводит к насыщению сигнатуры, т.е., когда все биты будут '1', что сильно уменьшает избирательность сигнатуры и ухудшает производительность поиска.

Существуют несколько структур данных для хранения сигнатур, такие как сигнатурный файл (signature file),но они не являются индексами, так как требует полного просмотра. Дерево RD-Tree является аналогом R-Tree, приспособленное к работе со множествами для решения задачи поиска всех множеств, которые содержат в себе некое подмножество, является индексной структурой и может сильно ускорять поиск. Подробнее о RD-Tree можно прочитать в оригинальной статье [RDTREE]




Содержание  Назад  Вперед