How does Wikipedia's "What links here" work?

Question

I recently used Wikipedia's function "What links here" (which is found under the "Toolbox" element in any entry's left menu) and it got me started wondering how this function actually works.
I'm guessing that searching through all the article entries after links isn't very effective, so are all the links stored in a separate database? If so, is this updated when an article is edited or another time?

Thanks.

Answer 1

Whenever a page on Wikipedia is edited, it is placed into a background queue that does some further processing. Some of the things that happen there are:

• updates to the "what links here" for other pages
• updates to category index pages
• updates to the global cache of existing pages to help render "redlinks" on other pages

This sort of information doesn't need to be updated right away when you hit "Submit", so the background processing queue takes care of it. Sometimes this queue can grow quite large, but usually it's kept under control.

You can find more information about this at Help:Job Queue.

Answer 2

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.