cross-reference table
A cross-reference table is the map at the end of a PDF, saying where in the file every numbered part of the document begins.
In more detail
The parts of a document are written one after another and numbered as they go, and nothing in the file says where part four hundred and twelve starts except this table: one line per part, giving how many bytes into the file it stands. The very last line of a PDF says where the table itself begins, which is why software opening a document reads its end before anything else.
That is what lets page three hundred of a four-hundred-page document appear without the two hundred and ninety-nine before it being read at all. The reader looks up the page in the map, jumps to it, and draws it. Since 2003 the map itself may be packed and compressed like anything else in the file, and it is then called a cross-reference stream.
What it does on a real document
A document can be added to without being rewritten. The new parts are written after everything already there, followed by a short map naming only what has changed and pointing back at the map before it. Not one byte of the original moves, which is exactly what lets a seal laid on those bytes still hold once a page has been added.
When the map is wrong — a file cut short in transit, or opened and saved by something that did not count its bytes properly — every line of it points a few characters beside the mark. Reading software then reads the whole file from end to end, rebuilds the map itself, and says nothing about it. That is why a broken document usually opens anyway, and why it opens slowly.
Where it comes from, and why
The table is as old as the format, published in 1993. Its lines were laid out to be exactly twenty characters long, padded with noughts, so that a program could reach the line for part four hundred and twelve by multiplying rather than by reading — a concern of a machine that read a file from a spinning disc.
The 2003 revision allowed the map to be written as a compressed parcel instead, alongside the packing of the document's other notes: the two travel together, and a file that packs one packs the other.
See it on a finished document
Making the file smaller Showing page one before the file has arrived