Web Crawling: Downloading the Internet

Suppose you publish a new page tonight — a blog post, a school project site, a page for your family's shop. You do not email it to Google. You do not fill out any form telling any search engine it exists. Yet within days, sometimes hours, a search for the right words on that page can turn it up. Nobody at Google typed your URL into a box. So how did a machine, with no human pointing at your page, ever find it?

The answer is a program called a web crawler (also called a spider or a bot), and the mechanism it uses is one you already half-know from data structures: graph traversal. This chapter builds the crawler from first principles — as a precise traversal algorithm on a graph, with a real worked trace, real complexity analysis, and the real engineering constraints (politeness, duplicates, infinite traps) that separate a toy script from something that can responsibly download a meaningful slice of the web.

The Web Is a Graph — Make That Literal

Every webpage is a node. Every hyperlink <a href="..."> on that page is a directed edge to another node. That's it — that is the entire structure a crawler works with. A page about ISRO's Chandrayaan mission links to a page about Gaganyaan; that's an edge from node A to node B. It costs nothing to state, but it is the whole trick: crawling the web is graph traversal starting from a set of known "seed" pages.

This reframing matters because it converts a vague, philosophical question ("how does a search engine discover the internet?") into a precise computer-science question you already have tools for: given a graph and a starting node, visit every reachable node exactly once, efficiently. You've seen this problem before, just usually drawn as a maze or a friendship network. The web is a graph with roughly the same rules, except it has an estimated hundreds of billions of nodes, no complete map exists in advance, and the graph is being edited by millions of people while you traverse it.

Worked Example: Tracing a Crawl by Hand

Take a small, concrete web graph — small enough to trace on paper — rooted at an ISRO page, with a link out to Wikipedia:

isro.gov.in                     -> isro.gov.in/missions,
                                    isro.gov.in/gallery,
                                    wikipedia.org/ISRO
isro.gov.in/missions            -> isro.gov.in/missions/chandrayaan,
                                    isro.gov.in/missions/gaganyaan
isro.gov.in/gallery             -> (no outgoing links)
wikipedia.org/ISRO              -> wikipedia.org/Chandrayaan-3,
                                    wikipedia.org/ISRO   (links to itself!)
isro.gov.in/missions/chandrayaan -> isro.gov.in/missions   (links back up!)
isro.gov.in/missions/gaganyaan  -> (no outgoing links)
wikipedia.org/Chandrayaan-3     -> (no outgoing links)

A crawler maintains exactly two pieces of state: a frontier — the queue of URLs discovered but not yet downloaded — and a visited set — every URL already downloaded, so it is never fetched twice. Starting from the seed isro.gov.in and always taking the frontier's oldest entry first (that's what makes this breadth-first), here is the exact state after each step:

Notice the two discards in bold: wikipedia.org/ISRO links to itself, and isro.gov.in/missions/chandrayaan links back to isro.gov.in/missions, which was already fetched two steps earlier. Without the visited set, the crawler would fetch these pages over and over, forever, on nothing more exotic than two ordinary hyperlinks. This single design decision — check membership before enqueueing — is what turns a graph with cycles into a traversal that provably terminates.

Now the code that produces exactly this trace:

from collections import deque

web_graph = {
    "isro.gov.in": ["isro.gov.in/missions", "isro.gov.in/gallery",
                     "wikipedia.org/ISRO"],
    "isro.gov.in/missions": ["isro.gov.in/missions/chandrayaan",
                              "isro.gov.in/missions/gaganyaan"],
    "isro.gov.in/gallery": [],
    "wikipedia.org/ISRO": ["wikipedia.org/Chandrayaan-3",
                            "wikipedia.org/ISRO"],
    "isro.gov.in/missions/chandrayaan": ["isro.gov.in/missions"],
    "isro.gov.in/missions/gaganyaan": [],
    "wikipedia.org/Chandrayaan-3": [],
}

def crawl(seed, max_pages=10):
    frontier = deque([seed])
    visited = set()
    order = []
    while frontier and len(visited) < max_pages:
        url = frontier.popleft()
        if url in visited:
            continue
        visited.add(url)
        order.append(url)
        for link in web_graph.get(url, []):
            if link not in visited:
                frontier.append(link)
    return order

print(crawl("isro.gov.in"))
# ['isro.gov.in', 'isro.gov.in/missions', 'isro.gov.in/gallery',
#  'wikipedia.org/ISRO', 'isro.gov.in/missions/chandrayaan',
#  'isro.gov.in/missions/gaganyaan', 'wikipedia.org/Chandrayaan-3']

Run that loop in your head against the table above and every line matches — that's the point of tracing by hand first: the code isn't magic, it's the table, mechanized.

The Diagram: Discovery Edges vs. Discarded Edges

Why Breadth-First, Not Depth-First?

A depth-first crawler would take isro.gov.in, immediately follow its first link all the way down before backing up — plausible, and it's the traversal you'd reach for first if you only knew recursion. It is also the wrong choice for crawling, and the reason exposes a real hazard of the live web: crawler traps.

Picture a page with a "next day" link on a calendar widget: day 1 links to day 2, day 2 links to day 3, and so on, forever, with no natural end. A depth-first crawler that follows the first link on every page it visits will walk straight into that calendar and never come back — it can spend its entire budget descending one infinite corridor while a hundred genuinely different websites sit untouched in the frontier. A breadth-first crawler cannot make that mistake structurally: it exhausts every link at distance 1 from the seed before touching anything at distance 2, so a trap discovered at depth 50 only gets 50 pages' worth of attention no matter how deep it goes, because the crawler keeps circling back to the many other level-1 and level-2 pages first. Breadth-first crawling isn't just "a" valid traversal order — it is the order that maximizes site diversity per page fetched, which is exactly what a crawler trying to cover the web (rather than exhaustively mirror one site) needs.

The Data Structures Underneath, and Why They're the Right Ones

The frontier is a queue (first-in-first-out) — in Python, collections.deque, which supports popleft() and append() in O(1) time each. The visited set is a hash set, not a list. This isn't a stylistic preference — it's a complexity requirement. If visited were a Python list, the check if url in visited would scan the entire list, an O(n) operation; run inside the crawl loop, that turns the whole crawl into O(n²) — for a million-page crawl, roughly 10¹² comparisons, which is not something you wait for. A hash set gives that same membership check in O(1) average time by hashing the URL directly to a bucket. So the true cost of crawling a graph with V pages and E total links is O(V + E) — every page is dequeued once (O(V)) and every one of its outgoing links is examined once to decide whether to enqueue it (O(E)) — the same bound you'd derive for BFS on any graph, and one worth remembering directly for GATE-style algorithm-complexity questions.

The Same URL, Twice: Why "Have I Seen This?" Is Harder Than It Looks

The visited-set check only works if equal pages produce equal keys — and raw URLs lie about that constantly. http://www.example.com/page/, https://example.com/page, and https://example.com/page?sessionid=8827 can all serve the identical page, yet as strings they are three different keys, so a naive crawler would fetch the same content three times. Before hashing or comparing, a crawler canonicalizes the URL: lower-case the domain, drop a leading www., treat http and https as equivalent, strip trailing slashes, and remove query parameters known to carry no content (like session IDs) while keeping ones that do (like ?lang=en).

from urllib.parse import urlsplit, urlunsplit

def normalize(url):
    scheme, netloc, path, query, _ = urlsplit(url)
    netloc = netloc.lower().removeprefix("www.")
    scheme = "https"
    path = path.rstrip("/") or "/"
    query = "&".join(sorted(
        p for p in query.split("&")
        if p and not p.startswith("sessionid=")
    ))
    return urlunsplit((scheme, netloc, path, query, ""))

print(normalize("http://WWW.Example.com/Page/?sessionid=99&lang=en"))
# https://example.com/Page?lang=en

Trace it: urlsplit pulls out scheme='http', netloc='WWW.Example.com', path='/Page/', query='sessionid=99&lang=en'. Lower-casing and stripping www. gives netloc='example.com'; forcing scheme='https'; path.rstrip("/") turns '/Page/' into '/Page'; splitting the query on & gives ['sessionid=99', 'lang=en'], the filter drops the session parameter, leaving ['lang=en'], which the join reassembles as 'lang=en'. urlunsplit reassembles all of that into https://example.com/Page?lang=en — exactly the printed output. Every visited-set lookup in a production crawler runs on this normalized form, not the raw URL a page happened to spell out.

Same Content, Different URL: Fingerprinting

Normalization catches URLs that are superficially different but structurally the same. It does not catch mirror sites or syndicated copies — a news article republished verbatim on two unrelated domains has two genuinely different, correctly-normalized URLs but identical content. For that, a crawler fingerprints the content itself: hash the normalized page text, and if the hash has been seen before under a different URL, the page is a duplicate.

import hashlib

seen_fingerprints = set()

def fingerprint(text):
    normalized = " ".join(text.lower().split())
    return hashlib.sha256(normalized.encode()).hexdigest()

def is_duplicate(text):
    fp = fingerprint(text)
    if fp in seen_fingerprints:
        return True
    seen_fingerprints.add(fp)
    return False

Two pages whose HTML differs only in capitalization or stray whitespace normalize to the same string, hash to the same SHA-256 digest, and get flagged as duplicates — correctly, since a search engine gains nothing from indexing the same paragraph twice under two URLs. This exact-match hash won't catch near-duplicates (the same article with a different ad banner and a "last updated" timestamp bolted on) — real large-scale crawlers use a family of techniques called shingling and simhash for that, comparing overlapping word sequences instead of the whole document; the underlying idea — reduce a document to a short fingerprint you can compare in O(1) instead of comparing full text — is exactly what you just implemented, just made tolerant to small edits.

Politeness: robots.txt and the Cost of Being Rude

A crawler is a guest on someone else's server, and an impolite guest can take a small website offline just by requesting every page as fast as its network connection allows. Two mechanisms govern this. First, the Robots Exclusion Protocol: a site publishes a plain-text file at /robots.txt listing paths it does not want crawled and, often, a minimum delay between requests:

User-agent: *
Disallow: /admin/
Disallow: /cart/
Crawl-delay: 2

User-agent: ResearchBot
Disallow: /

(This is an illustrative example, not a copy of any specific real site's file — the format itself, though, is the actual standard every compliant crawler parses before fetching anything.) The general rule (User-agent: *) disallows /admin/ and /cart/ and asks for a 2-second gap between requests; a named bot, ResearchBot, is disallowed from the entire site (Disallow: /). A polite crawler fetches robots.txt first, parses these rules, and simply never enqueues a disallowed URL — it isn't a technical barrier the site enforces, it's a contract the crawler agrees to honor.

Second, rate limiting: even without a stated crawl-delay, a crawler spaces out requests to any single domain, while running many domains in parallel to stay fast overall. Suppose a politeness policy of Δt = 1 second between requests to the same domain is respected, but D = 5,000 different domains are being crawled simultaneously (a different domain every time the 1-second timer for domain A is still ticking). Each domain independently permits 86,400 seconds/day ÷ 1 second/request = 86,400 requests per day. With D domains running that schedule in parallel, the crawler's total throughput is:

D × (86400 ÷ Δt) = 5,000 × 86,400 = 432,000,000 pages/day

That's the whole trick behind crawling at scale: no single domain is ever rushed, but the crawler stays fast in aggregate by fanning the same politeness budget out across thousands of domains at once — a scheduling problem, not a speed problem.

How Far Does Breadth-First Reach? A Branching-Factor Estimate

Here's a question worth answering with algebra rather than intuition: starting from one seed page, how many pages can a crawler reach within k hops? Suppose, as a simplified model, every page contributes b links to pages the crawler has never seen before (not its total link count — most of a real page's links point to pages already discovered, like navigation menus, and those get discarded by the visited-set check, exactly as wikipedia.org/ISRO's self-link was discarded in the worked example above).

At hop 0 there is 1 page (the seed). At hop 1 there are up to b new pages. At hop 2, each of those b pages contributes up to b more, giving b². In general, hop i contributes up to bⁱ new pages, so the total reachable within k hops is the geometric sum:

N(k) = 1 + b + b² + … + b^k = (b^k+1 − 1) / (b − 1)  (for b ≠ 1)

Take a modest b = 10 and go only k = 4 hops deep:

N(4) = (10⁵ − 1) / 9 = 99,999 / 9 = 11,111 pages

Eleven thousand pages, reached in just four hops from one seed, with a branching factor no larger than the number of fingers on both your hands. This is the algebraic heart of the web's so-called "small-world" property: because N(k) grows exponentially in k while the number of hops needed to reach a typical page grows only logarithmically (k ≈ log_bN), a crawler doesn't need billions of seed pages to reach a huge fraction of the crawlable web — a modest, well-chosen seed set gets there in a handful of hops. (Real crawls see lower effective growth than this idealized formula, because many of those bⁱ links land on pages already discovered from a different direction — which is precisely why the visited set matters more, not less, as the frontier grows.)

Common Misconception: "The Crawler Downloads the Whole Internet, Once"

The BFS trace above terminates — the frontier empties, the function returns. It is tempting to picture a real crawler the same way: start at some seeds, traverse everything reachable, finish, done, the internet is now "downloaded." That picture is wrong in a way that matters. The web has no boundary and never stops changing: new pages are published every second, existing pages are edited, and some pages — like the "next day" calendar trap discussed earlier, or search-result pages generated by combining filters on an e-commerce site — generate effectively unlimited new URLs on demand. A crawler that treated the web as a finite graph to be exhausted once would either run forever chasing traps or stop with a permanently stale snapshot. Real crawlers instead run continuously against a priority frontier rather than a plain FIFO queue: each undiscovered or previously-crawled URL gets a score based on factors like how important the linking pages seem and how often the content tends to change, and the highest-scoring URL is fetched next, forever — pure breadth-first order is the right mental model for how discovery spreads outward from a seed, but production frontiers are best-first, not strictly level-by-level, and "finished crawling" isn't a state a live web crawler ever reaches.

Where This Shows Up in Your Exams

Breadth-first traversal, its O(V + E) complexity, and the queue-plus-visited-set implementation are standard material once you reach graph algorithms in Class 11–12 Computer Science and are a recurring building block in GATE-level algorithm questions and in competitive programming for the Informatics Olympiad — the crawler is simply BFS with an unusually motivating story attached, and the geometric-series reachability argument above is exactly the kind of derivation JEE/BITSAT-style problems expect you to carry out symbolically before plugging in numbers, not memorize as a formula. If a question ever describes "a set of items where each item points to some other items, and you must visit every reachable item exactly once, closest ones first" — that is BFS with a visited set, whether it's framed as a crawler, a maze, or a friend-of-a-friend network.

Active Recall

1. In the worked ISRO/Wikipedia trace, if isro.gov.in/gallery had one outgoing link to isro.gov.in (the seed itself), would the crawl's output order change? Trace it and justify your answer using the visited-set rule.
2. Using N(k) = (b^k+1 − 1) / (b − 1), what branching factor b is needed to reach at least 100,000 pages within k = 3 hops? (Solve for b by testing integer values — you won't get a clean closed form.)
3. Why does a depth-first crawler risk exhausting its entire fetch budget on a single site, while a breadth-first crawler structurally cannot? Answer in terms of what each strategy guarantees about the frontier's contents.
4. A page's raw URL is HTTP://Site.example/News/?ref=homepage&id=42. Walk it through the normalize() function from this chapter step by step and state the final canonical URL.
5. Two different URLs return HTML that is identical except one has an extra blank line at the end. Will the SHA-256 fingerprinting code in this chapter flag them as duplicates? Explain exactly why, referencing the normalized = " ".join(text.lower().split()) line.
6. A site's robots.txt sets Crawl-delay: 3 and the crawler is politely crawling 2,000 domains in parallel, each obeying its own site's stated delay of exactly 3 seconds. Compute the crawler's total daily throughput in pages, showing the formula you used.

Summary

A web crawler treats the web as a directed graph — pages as nodes, hyperlinks as edges — and downloads it via traversal from a seed set, most commonly breadth-first, using a FIFO frontier queue and an O(1)-lookup visited hash set to guarantee O(V + E) total work and to guarantee termination even in the presence of cycles and self-links. Breadth-first order is preferred over depth-first specifically because it bounds how much of the crawl budget any single crawler trap — an infinite calendar, an endlessly filterable search page — can consume. Because raw URLs are an unreliable key (the same page can be reached through several superficially different URLs), crawlers canonicalize URLs before comparing them, and separately fingerprint page content via hashing to catch mirrors that normalization can't. Two engineering constraints keep a crawler from being harmful: the Robots Exclusion Protocol, which a crawler is expected to honor even though nothing forces it to, and rate limiting per domain, whose aggregate throughput across many parallel domains follows directly from a small formula. Finally, a geometric-series argument shows why even a modest per-page branching factor lets a crawler reach a large, mostly-connected portion of the web within a small number of hops — and why, since the web keeps changing and generating new URLs faster than any single pass can finish, a real crawler's frontier is a perpetual, priority-ordered process, never a queue that empties for good.

Think About It

Think about this: How would you explain web crawling: downloading the internet to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where web crawling: downloading the internet is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting web crawling: downloading the internet to at least 3 other topics you have studied.