поиск с помощью индексов
Алгоритмы поиска, обратный индекс — Часть 1
C этой статьи я начинаю цикл статей по SEO, в которых будет теория, практика и советы. Начнем естественно с азов. В материале вкратце описываются алгоритмы, по которым современные поисковые системы осуществляют поиск, как проходит индексация, какие математические модели используются при поиске документов.
Что вы узнаете?
Алгоритмы поиска
Обратный индекс
Как вы наверное догадались поисковиками используется алгоритм инвертированных индексов, т. к. использование прямого поиска гораздо более ресурсоемко. Восстановление из обратного индекса произойдет с потерями (падежи, дефисы, запятые, ). Поэтому также хранится прямой индекс документа для отображения сниппета (фрагмент найденного текста документа отображаемый в поиске).
Документ
поп,
Толоконный лоб.
Пошел поп по базару
Посмотреть товару.
Обратный индекс документа
Параметры указаны самые примитивные и только для примера — строка, позиция в строке. В параметрах также хранятся падежи слов, и принадлежность к пассажу.
Математическая модель
TF — частота слова в документе
IDF — редкость слова в коллекции (корпус слов)
Главное
Релевантность — степень отношения к делу. Продвигайте только релевантные документы.
Что такое поисковый индекс
28 ноября 2017 Опубликовано в разделах: Азбука терминов. 8726
Индекс того или иного ресурса напрямую зависит от текстового контента сайта, его ссылок (внешних и внутренних), графики и так далее. Когда пользователь отправляет запрос в поисковик, он обращается к индексу. Далее на основании данных из поискового индекса выполняется ранжирование результатов поиска, сайтов по степени убывания релевантности.
Чтобы понять, что такое поисковый индекс, разберем простую аналогию. Вспомните общественную библиотеку. Каждая книга здесь имеет свой шифр, индекс. Данные шифры объединяются по темам, направлениям и так далее. Когда читатель просит ту или иную книгу, то есть делает запрос, библиотекарь просматривает все книги, относящиеся к определенному разделу и ищет ту, которая больше всего подходит. Аналогичным образом работает и поисковик: пользователь делает запрос, система просматривает все имеющиеся страницы и выдает ту, которая больше всего подходит.
Что значит индексация
Это процесс, в ходе которого роботы включают имеющиеся данные в единую базу. Далее они обрабатываются. Сбор данных, формирование индекса может происходить автоматически или вручную. В первом случае робот ищет сайты, для этого он сканирует файл формата sitemap.xml или переходит по внешним ссылкам с других сайтов. Во втором варианте владелец сайта сам добавляет URL сайта в специализированные формы-заявки систем Гугл, Яндекс и так далее.
Впервые индексация появилась более 25 лет назад. Тогда база проиндексированных страниц была построена по принципу предметного указателя с ключевыми словами (поиском ключевых слов занимались роботы). На сегодняшний день механизм существенно усложнился, стал более эффективным. На современном этапе, чтобы данные попали в индекс, они сначала обрабатываются специализированными вычислительными алгоритмами, при этом обязательно используется искусственный интеллект.
Для чего нужен индекс поисковой системы
Индексация страниц интернет-ресурса является обязательным элементом работы поисковиков. В ее результате создается база данных, с помощью которой формируются результаты выдачи. Таким образом, любой сайт должен быть проиндексирован поисковой системой, чтобы выходить в результатах выдачи по запросам пользователей.
Индексирование делают роботы, которые бывают двух типов:
Есть и другие роботы, которые различаются по предмету индексации: специальные механизмы для работы с изображениями, RSS-лентами и прочими материалами.
Чем быстрее сайт добавляется в индекс, тем скорее вы увидите первых посетителей. Индексация Гуглом занимает несколько дней, а индексация Яндексом — несколько недель.
Проверить индексацию в системах Гугл и Яндекс
Чтобы проверить, проиндексирован ли ваш ресурс, можно использовать несколько способов:
Ускорение индексации
Скорость индексации зависит от факторов:
Если вы желаете увеличить скорость индексации и быстрее войти в поисковую систему, сделайте следующее:
С момента занесения сайта в индекс начинается отсчет возраста сайта.
«Добавим 2 млн статей и посмотрим, что будет»: как ускорить базу данных с помощью индексов
Разбираемся, как ускорить работу базы данных приложений и сайтов, что такое индексы и как они устроены. Пособие для начинающих backend-разработчиков.
PHP-разработчик digital-агентства «Атвинта», в свободное время пишу на Go/C#/C++. Нравится проектировать и продумывать highload-системы.
Базы данных — это совсем не сложно, даже новички быстро вливаются в тему и начинают работать практически без проблем. А что сложного? Есть таблицы, в них записываем строки — всё просто. Да, и всё работает, никто не жалуется. Пока не наступит момент… когда данных будет много.
Тут нам и приходят на помощь индексы. Во всех базах данных они работают примерно по одному и тому же принципу. В этой статье я буду использовать MariaDB.
Запрос на выборку без индексов
Рассмотрим на простом примере. Есть таблица articles со следующей структурой:
Добавим в таблицу несколько записей:
И сделаем следующий запрос:
Ничего удивительного: простой запрос и выполняется быстро. Но что будет, если данных «чуть-чуть» больше? Давайте добавим, например, 2 млн статей.
И повторим запрос на выборку:
Как видим, время выполнения запроса увеличилось. Хоть и две секунды, но это долго. И нагрузка на диск высокая.
Две секунды на выполнение запроса — не предел; когда данных ещё больше, всё будет ещё хуже. Оптимизировать этот запрос можно с помощью индексов.
Запрос на выборку с индексом
Создаем индекс по колонке views из таблицы articles.
И повторяем запрос:
Вот! Так намного лучше. Выборка проходит так же быстро, как и с тремя записями. В чём же подвох? Как это работает и почему? Что может пойти не так?
Как устроен запрос без индекса и с ним
Запрос к выборке БД без индекса
Что происходит, когда мы запрашиваем данные? А что вы делаете, когда ищете нужную вам строку в таблице? Да, база данных сканирует всю таблицу и выбирает те записи, которые попадают под условия.
Это происходит быстро, когда у нас три записи, и долго, когда их очень много. Ведь наша таблица хранится на физическом носителе и, чтобы просмотреть её всю, нужно считать немало данных.
Запрос к выборке БД с индексом
Я часто встречаю, что индекс путают с id или уникальным идентификатором, считают, что это одно и то же. Это не так! Индекс в базах данных — это другое.
Индекс, который мы создали, представляет из себя такую структуру данных, как B-дерево. Но, например, в InnoDB используется B+-дерево. Всё зависит от подсистемы хранения, а в целом принцип их работы похож. Это дерево строится по колонке views из таблицы articles.
Чтобы понять, как происходит выборка с индексом, нужно знать, как работает B-дерево.
Перед нами B-дерево индекса. В каждом узле хранятся элементы со значениями; в нашем случае это значения из поля views. Также элементы хранят ссылку на строку в таблице.
Поиск начинается с корневого узла. Наша задача — пройти по каждому элементу в узле и сравнить его значение с искомым:
Дерево из примера выше не является копией того, которое построила БД в моём случае. Это я изобразил, чтобы показать, как проходит поиск по дереву.
Рассмотрим алгоритм на примере поиска значения 2001.
То, что мы и искали. А так как искомая ячейка содержит ссылку на место, где лежат наши данные, то мы можем легко и быстро прочитать их.
Ещё один способ запроса с индексом
В данной структуре можно легко делать выборку по диапазонам, например views >= 1000. В случае таких запросов индекс также поможет.
Хоть поиск и значительно ускорился, есть и свои нюансы. Изменения в В-дереве — не самая быстрая операция.
Необходимо, чтобы все конечные узлы (листья) дерева находились на одном уровне, а количество элементов в узлах было одинаковым — тогда мы получим наивысшую скорость выборки.
Чтобы придерживаться этих условий, нужно постоянно проводить перебалансировку дерева. Это и замедляет работу.
Если вы используете несколько десятков индексов в одной таблице, то при вставке или удалении из неё нужно проводить такие нехитрые манипуляции с деревьями. Из этого следует вывод, что не стоит увлекаться и создавать индексы по каждому полю.
Мы рассмотрели создание индекса по одной колонке (views), но в базах данных одной колонкой не ограничишься. Можно создавать составные индексы. Например, если есть поле views и дата created_at, и вы хотите делать подобные запросы: views = 1000 and created_at = «10.10.2019», то имеет смысл создать индекс по двум колонкам.
Индексирование в поисковиках: что это такое и как работает
Время чтения: 19 минут Нет времени читать? Нет времени?
В тени остается сам процесс индексации, его алгоритмы и механизмы. Есть ли там что-то интересное и полезное для нас? Да, есть, и немало! Сегодня остановимся на процессе индексирования. Узнаем, что это такое, как происходит, а также поймем, можно ли повлиять на скорость добавления новых страниц в Google и «Яндекс».
В чем разница между индексированием и ранжированием
Начинающие вебмастера и оптимизаторы часто путают индексирование с ранжированием. Эти понятия взаимосвязаны, но обозначают разные явления и процессы.
Ранжирование – конечная сортировка сайтов, которые находятся в выдаче, и присвоение им определенных позиций или рангов. Конкретный ранг может быть дан определенной странице, когда она окажется в индексе, и только в тот момент, когда пользователь осуществит поиск по какой-то фразе. Такой порядок внедрен, чтобы обеспечить наличие максимально релевантных страниц в результатах поиска.
Индексирование – процесс добавления (обновления) данных о странице.
Как работает индексирование
Индексирование происходит благодаря краулеру: он обходит страницы всех сайтов в интернете и отправляет получаемую информацию в базу данных поисковой системы. Она и называется индексом. В дальнейшем собранные данные задействуются по-разному. Частично – для выстраивания ранжирования и формирования максимально релевантных поисковой фразе результатов поиска. Частично – для иных, например, служебных целей.
Поисковик может использовать данные только с тех страниц, которые уже были проиндексированы им. Пока первичная индексация не состоялась, его не будет существовать для Google. Зато после Google быстро найдет любую информацию в своих базах данных, и поиск по нескольким миллионам страниц займет считанные миллисекунды.
Стоит отметить, что, даже если краулер уже «обошел» страницу, это не гарантия того, что она мгновенно или вообще когда-либо попадет в поисковую выдачу. Да, краулер обходит абсолютно все страницы, но в SERP попадают только страницы с полезным и уникальным контентом.
Тяжело создавать контент, который удовлетворит не только запросы поисковиков, но и пользователей? Обращайтесь за помощью в «Текстерру».
Обмануть поисковую систему точно не удастся, а если и удастся, то ненадолго: для распознавания некачественного контента у Google есть собственные наработки, защищенные патентами.
Индекс E-A-T, рейтинг Page Quality и алгоритм BERT – все эти разработки позволяют точно определять полезность контента на странице и автоматически распознать его качество. В их основе лежит взаимодействие машинного обучения и других разработок Google, связанных с оценкой пользовательского опыта.
Что представляет из себя индекс Google
Как мы уже выяснили выше, индекс – это большая база данных, которая состоит из нескольких ключевых разделов. Углубляться в них не буду – это не так важно. Скажу лишь, что в этой базе данных имеются сведения о нескольких миллионах страниц. При сканировании краулеры «ощупывают» не только видимую посетителю текстовую информацию страницы, но и другие данные: атрибуты документа, информацию из тегов (alt, title, description), другие технические данные.
Как выглядит индекс Google
Google использует так называемый инвертированный (преобразованный в противоположную сторону) индекс. Условно, краулеры сперва проверяют код ответа сервера, затем – данные из хед и данные по индексации. Только после всех этих технических проверок следует проверка текста. Схематично инвертированный индекс выглядит следующим образом:
Как создается индекс Google: все этапы
Если представить формирование индекса поэтапно, он будет включать в себя четыре стадии.
Краулеры могут сформировать и более сложную запись, но ее скелет все равно будет иметь в основе нарисованную выше схему.
Можно ли ускорить индексирование новых страниц
Можно, но не прямым образом. Если страница долго не появляется в результатах поиска, нужно убедиться, что она не закрыта для краулеров.
Для этого открываем системный файл robots.txt (он находится в корневой директории). Допустим, для сайта mirdostupa.ru файл robots.txt будет находиться по адресу mirdostupa.ru/robots.txt. Проверяем наличие запрещающего тега для интересующего URL. Выглядеть он может так:
Чтобы проверить состояние страницы в Google, открываем инструменты вебмастера:
При необходимости здесь же запрашиваем повторное индексирование (если страница так и не попала в индекс).
Чтобы добавить новую страницу в «Яндекс», можно воспользоваться служебным инструментом «Переобход страниц», который присутствует в «Яндекс.Вебмастере», но такое добавление не гарантирует попадание в индекс:
Чтобы новые страницы индексировались быстро и без проблем, необходимо следить за качеством контента. Естественно, в Google и «Яндекс» не будут попадать мусорные страницы, содержащие только поисковый спам и SEO-оптимизацию. Все элементы страницы должны находиться на своих местах, включая теги, картинки, названия и описания.
Как закрыть страницу сайта от индексации / удалить ее из Google
Хотите скрыть определенную страницу от краулеров (например, технические страницы или страницы с данными пользователей, включая конфиденциальную информацию)? Для этого есть три способа: использование тега robots, добавление запрещающей директивы в системный файл robots.txt, использование инструментов Google и «Яндекса». Рассмотрим все три способа подробнее.
Чтобы закрыть страницу от индексации при помощи мета-тега Robots, достаточно добавить в заголовок страницы ( ) следующий код:
Теперь о запрещающей директиве в robots.txt.
В этом файле прописываются наши «пожелания» для поисковых ботов, но исполнять их будут на свое усмотрение. Чтобы «попросить» краулера не обходить страницу, достаточно добавить в robots следующую запись:
Теперь об инструментах вебмастера. Открываем «Инструмент удаления URL», выбираем домен и пункт «Создать запрос». указываем ссылку и выбираем пункт «Удаление страниц». Далее следуем подсказкам инструмента, чтобы удалить URL из результатов поиска. После завершения отправки данных страницы будут удалены из индекса Google через некоторое время.
Как удалить страницу из результатов поиска «Яндекса»
Для удаления конкретной страницы из результатов поиска проще всего воспользоваться инструментом «Удалить URL». Запретить индексацию можно директивой Disallow, которую нужно добавить в уже знакомый нам системный файл robots.txt:
Disallow: /вставить_URL #
Как узнать, проиндексирована ли страница
Проверить состояние страницы в индексе поисковых систем можно несколькими способами. Самый простой заключается в ручном вводе URL страницы в строку поиска Google / «Яндекса». Если страница уже попала в индекс, она будет отображаться в результатах поиска. Если нет, совпадений, соответственно, не будет.
Как увидеть все страницы сайта, которые находятся в индексе
Для этого в поисковой строке вводим оператор вида site:вставитьвашсайт.ru, например: site:texterra.ru. В результатах поиска мы увидим все страницы, которые сейчас находятся в индексе Google:
Увидеть количество проиндексированных страниц можно также в Google Search Console. Открываем раздел «Индекс» и выбираем пункт «Покрытие». Здесь отобразится общее количество проиндексированных страниц:
Кроме этого, узнать, сколько страниц находится в индексе «Яндекса» и Google, можно при помощи сервиса xseo. Пользоваться им просто: достаточно указать домен и выбрать пункт «Проверить»:
Почему проиндексированная страница может покинуть SERP
Причин выпадения из индекса довольно много. Я перечислю самые распространенные, с которыми сам регулярно сталкиваюсь:
Послесловие
Индексирование – важнейший этап сбора данных о сайтах в интернете. Без индексации новые веб-страницы никогда бы не попали в поисковые системы. Повлиять на индексирование можно лишь непрямым образом: если мы указываем какие-либо команды в robots.txt, то мы даем краулерам лишь рекомендации.
Стоит отметить, что большие поисковые системы эти рекомендации соблюдают беспрекословно. Если ваши страницы преимущественно проиндексированы, но на поиске сайт почти невидим, значит, следует работать над качеством контента.
Проиндексируются все страницы, но бесполезный контент и поисковый спам никогда не будут ранжироваться наравне с качественными сайтами в результатах поиска.
Построение индекса для поисковой машины
Полное содержание и список моих статей по поисковой машине будет обновлятся здесь.
В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.
На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.
Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.
Чтобы решить и эту, и много других проблем связанных с ограничениями ФС, диска, параллельным доступом к нескольким спискам страниц, я разбил весь индекс на 256 частей. В часть I попадают списки страниц для слов WORD_ID%256=I
Таким образом делим индекс на примерно равные части. Кроме того вся обработка на очередной итерации перестроения индекса связана только в рамках одной части. Т.е. из 20-50 кусков БД по 200-300 Mb необходимо загрузить только те данные, которые связаны со словами, попадающими в обрабатываемую часть.
Итого: делаем 256 повторений одной и той же процедуры:
На практике естественно оказалось, что тот список, который уже хранится в «предыдущей версии» индекса оказывается отсортированным при новой итерации только тогда, когда никакая внешняя информация о страницах не менялась, а это очевидно не так.
Ведь пока мы копили инфу для индекса, могли пересчитаться данные о PR, метрики страниц, тематичность сайтов, и тд. И как следствие, изменится коэффициенты для сортировки. Вопрос нужно ли вообще сортировать списки по подобным параметрам, до сих пор открыт. По слухам гугл сортирует страницы в списках по PR, но очевидно тогда надо уметь быстро отбрасывать шелуху при поиске – которую специально накачали PR, но тематичности недостаточно.
Я использую совмещенный коэффициент, построенный из общей информации о слове на странице (кол-во встреч; место встречи – title, meta, ссылки, текст; выделение, форматирование), из метрик тематичности (пока что они развиты у меня весьма слабо), из PR, из пословного PR (PR по каждому слову у меня тоже есть) и некоторых других.
Причем очевидно, что при высокочастотных запросах, нам реально нужны дай бог первая 1000-2000 результатов в списке, для верности будем считать 262 тысячи. Т.к. все популярные ответы очевидно попадут в них, а дальше на них можно запускать уже функцию ранжирования которая как следует их отсортирует.
При низкочастотных запросах, когда нам реально нужны 2-3-10 результатов, без полного прохождения индекса не обойтись, однако и общая длина списка страниц редко когда будет больше 100 тысяч.
Ну и конечно надо иметь функцию «обновить целиком» когда раз в месяц-полгода, к примеру, индекс будет перестраиваться весь самым простым прямым алгоритмом
Понятно, что даже такой объем работы в применении к 3 миллионам средне употребляемых слов и цифр дается нелегко, но зато по сравнению с полным перестроением выигрыш существенен: ведь не надо сортировать на диске, не надо грузить внешние метрики, PR и другие параметры – их ведь тоже нельзя кэшировать все в памяти.
Забавно что итеративный способ перестроения дает в разы большую производительность чем простейшее построение обратного индекса из прямого. Некоторые поисковики конечно умудряются это делать достаточно быстро на довольно мощном железе, однако это все равно не лучший подход хоть и самый корректный. Просто количество длинных вставок в обратный индекс сводит все плюсы на нет, да и в известных мне структурах хранения страдает либо скорость вставки либо скорость последовательного чтения.