How it works

The graph

Nodes are hosts (fully-qualified domain names — www.example.com and example.com are distinct), numbered 0…N-1. An edge A → B means a page on A referenced host B in its served HTML (a hyperlink, or a <script>/<img>/<iframe> source). The question "who links to X" is: list the predecessors of X.

Storage: CSR, both directions

The graph is stored as Compressed Sparse Row (CSR): two flat arrays per direction. For the outbound graph, out.dat concatenates every node's neighbour list back-to-back, and out.off holds where each node's list starts:

successors(x) = out.dat[ out.off[x] : out.off[x+1] ]

So a node's neighbours are one slice — no pointers, no per-node objects. To answer inbound ("who links to x") we keep the same structure for the transpose graph: in.off / in.dat give predecessors(x) the same way.

Each neighbour is a 4-byte node id; each offset is 8 bytes. For this index that's ~27.3 GB of adjacency and ~3.6 GB of offsets. Within every list the ids are stored ascending — a free consequence of the source-sorted input — which is what makes the results come out in a stable order and leaves the door open to delta + varint compression later.

Names ↔ ids

Host names live in names.dat (all names concatenated) with a names.off index, stored in id order — which, because ids are assigned in sorted order, is also sorted order. So resolving a host to its id is a binary search over the name table (O(log N)), and turning a result id back into a name is a direct slice. Storing names reversed (com.example.www) is also what makes ?prefix cheap: a host and all its subdomains form one contiguous range, found with two more binary searches.

Serving: memory-mapped

At startup the process mmaps the six files read-only. Nothing is parsed or loaded onto the heap — the kernel pages parts of the index in on demand and caches the hot ones in whatever free RAM exists. A query is therefore: binary-search the name (O(log N)), read one offset pair, stream the neighbour slice (O(degree)), map ids back to names. Resident memory stays tiny regardless of graph size, and there's no per-request allocation on the hot path.

Building: block-partitioned counting sort

The outbound side is easy — the raw edge list arrives sorted by source, so out.dat is written in a single sequential pass. The transpose is the hard part: grouping edges by destination when they arrive ordered by source is a counting sort, and a naïve version scatters writes randomly across the whole multi-gigabyte in.dat. Once that exceeds RAM, every write is a page fault — it thrashes.

Instead we split the destination-id space into blocks, each sized so its slice of in.dat fits comfortably in RAM, and make one sequential scan of the edges per block. A block only writes edges whose destination falls in its range, so every write lands in that block's contiguous, resident slice — no random I/O. We trade a handful of cheap sequential passes for eliminating the thrash:

for each block [lo, hi):        # destination range
    for each edge (s, d):       # one sequential scan
        if lo <= d < hi:
            in.dat[cursor[d]++] = s   # write stays inside this block's slice

The in-degree prefix sums (computed in one counting pass) are reused in place as the write cursors, so peak memory is essentially one offset array plus one block slice — a couple of GB even for a graph of billions of edges. Total on-disk index: ~30.9 GB.

Why it's fast and small

• No database, no server round-trips — just mmap'd arrays and index arithmetic.
• Flat and cache-friendly — a neighbour list is one contiguous run of 4-byte ints.
• Rebuildable — the whole index is a pure function of a public graph release; a new crawl is a fresh build swapped in atomically.