Что ж, вот одна из самых вкусных частей базы данных — она хранит миллиарды различных ссылок и обращается к ним в случайном порядке.
Во-первых, вы явно можете заметить, что все URL-адреса сгруппированы внутри сайта, т. е.
все ссылки внутри 1 сайта могут храниться вместе для скорости.
Я выделил URL сайта и стал хранить список сайтов отдельно — сейчас их 600 тысяч и с ними легко справится отдельная таблица базы данных, описанная ранее.
В памяти всегда есть AVL-дерево с CRC всех известных сайтов, и, предварительно проверив наличие URL-адреса, я получаю идентификатор соответствующего ему сайта, если он уже есть в базе данных.
Я обрезаю остальную часть ссылки — кроме имени сайта, и вычисляю для нее CRC, назовем его Хэшем.
Таким образом, любая ссылка имеет относительно уникальный индекс (идентификатор сайта, хеш).
Все ссылки можно отсортировать по Хэшу внутри отдельного сайта, и тогда вы сможете легко искать существующую или нет — пробегайтесь по списку всех ссылок на данном сайте, пока не встретите нужный Хэш или не увидите Хэш большего размера — это значит, что связи нет. Ускорение не очень большое, но все равно в 2 раза в среднем.
Надо сказать, что я присвоил каждой ссылке идентификатор, чтобы она занимала меньше места в индексе — 4 байта вместо 2*4. В отдельной таблице содержатся данные ID — (ID сайта, Хэш) для быстрой выборки.
Теперь немного о том, как хранить списки из миллиона ссылок и даже сортировать их по 600 тысячам сайтов.
Для этого реализован другой тип таблицы - с двумерным индексом, т.е.
сначала с помощью ID1 мы получаем доступ к списку данных, отсортированных по ID2, причем конкретно ID2 не обязательно должен быть от 1 до N, как это делается в большинстве случаев.
Я также использовал такую таблицу для хранения обратного индекса, но теперь там работает более эффективное решение.
Сама таблица реализована таким образом, что добавление ID2 в список сохраняет список отсортированным.
Все данные об URL-адресах разделены на 64 части по ID1, таблица K содержит записи о сайтах с ID%64=K, каждая таблица разделена на сегменты, выделенные для каждого конкретного ID1. Когда вам нужен доступ к определенному списку записей — по ID1, все они уже подряд лежат на диске, и вы сразу знаете позицию, где искать и с чего начинать буферизованное чтение.
Читаем ровно до тех пор, пока не встретим нужный Хэш Вставка в такую таблицу происходит не очень быстро; с другой стороны, большой кэш и небольшой объем одной записи позволяют довольно быстро вставлять пакетно.
Пакет обновления накапливается — теперь на каждую таблицу приходится примерно 32 000 ссылок, затем он вставляется за 1 проход — делается временная копия таблицы, в которую сливаются данные из кэша и старой таблицы.
URL-адреса с www и без него считаются одинаковыми — в зависимости от того, на каком из них была первая ссылка, он считается основным — он будет добавлен в базу данных, и к нему будут прилеплены все остальные ссылки.
Это позволяет избежать необдуманного отрезания или не отрезания www - ведь сайт может не работать без www, но не решает полностью всех проблем, связанных с тем, что по адресам с www и без него могут быть разные сайты.
Самая кропотливая работа была при разрешении относительных ссылок — пример: на странице «site.ru/index» есть ссылка «.
/», тогда она должна разрешиться на «site.ru/»; однако, если вы добавите косую черту к первой ссылке: «site.ru/index/», и хотя это может быть та же страница на сайте, разрешенной ссылкой будет «site.ru/index/», поэтому вы не сможете обрезать убрать косую черту в конце, аргументы ссылки и имя исполняемого файла обрезать нельзя.
В общем, я делю ссылку на части: протокол, сайт, путь, имя файла, аргументы, именованная ссылка (все после #) Из двух вырезанных вот так ссылок собираю новую, просматривая список и подставляя в результат недостающие элементы (при необходимости).
Тогда нельзя забывать, что существуют конструкции вида «.
/.
/.
/.
/.
/» и их необходимо удалить, так же как и «.
/.
/.
/», а затем удалить или заменить «#», ? В целом процесс не долгий, но очень утомительный по придумыванию тестов и способов обработки всех возможных комбинаций.
Но когда я это написал, всё уже работает как надо Полный контент и список моих статей в поисковике будут обновляться здесь: http://habrahabr.ru/blogs/search_engines/123671/ Теги: #url #БД #обработка ссылок #Поисковые технологии
-
Найти Adobe Acrobat Стало Проще
19 Oct, 24 -
Google Лучше Всех Знает, Что Вам Нужно :D
19 Oct, 24
