Как делает Википедию, “Что связывает здесь” работу?
Я недавно использовал функцию Википедии, "Какие ссылки здесь" (который найден под элементом "Панели инструментов" в левом меню любой записи) и это получило меня, начал задаваться вопросом, как эта функция на самом деле работает.
Я предполагаю, что поиск всех записей статьи после ссылок не является очень эффективным, таким образом, все ссылки хранятся в отдельной базе данных? Если так, это обновляется, когда статья редактируется или другое время?
Спасибо.
5 ответов
Всякий раз, когда страница в Википедии редактируется, она помещается в фоновую очередь для дальнейшей обработки. Вот некоторые из того, что там происходит:
- обновления «какие ссылки здесь» для других страниц
- обновления страниц индекса категорий
- обновления глобального кеша существующих страниц, чтобы помочь отображать «красные ссылки» на других pages
Информацию такого типа не нужно обновлять сразу после нажатия кнопки «Отправить», поэтому об этом позаботится очередь фоновой обработки. Иногда эта очередь может стать довольно большой, но обычно она находится под контролем.
Вы можете найти дополнительную информацию об этом в Help: Job Queue .
Я бы реализовал способ получить все ссылки после редактирования, а затем сохранить их в отдельной таблице с ключом, являющимся текущим URL-адресом. Тогда я мог бы просто запросить таблицу с URL-адресом, по которому в настоящее время находится пользователь, и получить все ссылки, которые были помечены как ссылающиеся на эту страницу.
Это, вероятно, было бы не так просто, но это общая, упрощенная идея . Возможно, вместо URL-адресов было бы разумнее хранить идентификаторы страниц и т. Д.
Было бы разумно, чтобы «событие обновления» статьи запускало синтаксический анализатор ссылок, поскольку это единственный раз, когда статья будет изменена. Событие обновления, в свою очередь, будет просто сканировать ссылки и запрашивать в БД ссылки, которые являются внутренними для Википедии.
Я полагаю, что каждая страница имеет первичный ключ, и создается простая таблица ассоциаций, чтобы связать страницы PK со всеми остальными страницы, которые ссылаются на него.
Вероятно, есть некоторые дополнительные биты, которые будут добавлены для повышения производительности на таком большом участке, но это будет основная механика.
You could think this as a more general problem. If you have a link (or pointer or whatever) from A to B, how can B know that A has a link pointing there?
The answer is to store the information to target location. That is, when the page A is edited and a link is created to B, at the same time store information about the link source to B (a reverse link). In case of a web page, the reverse link could be written directly into "what links here" page. Just a single write into a static page. No need to perform any searches or database queries.
Pseudo code for a simple algorithm that would do it
procedure updateChanges(editedPage):
for_each(link on editedPage):
if(link is not to another wikipedia page): continue
pageToUpdate = open(link):
if(pageToUpdate->whatLinksHere.contains(editedPage)): continue
pageToUpdate->whatLinksHere.insert(editedPage)
Sorry I just finished my algorithms class so I have an urge to write pseudo code. In this context, the updateChanges() procedure would be something called during the "update the 'what links here' for other pages" phase that Greg Hewgill referred to.