Mostly, it doesn't move them.

Before version 0.15, every item on a belt stored its place, and every update every place went up by one. In Harkonnen's words on Wube's blog: "Currently we move every item on every belt that can move. So if you have 20,000 items on belts in your giga-factory - each of those items will consume CPU to advance its position forward." Big factories ran at 25 updates a second, under the 60 the game aims for.

The fix: "We no longer store absolute coordinates of items, instead we store the distance between items." On a moving belt the gaps between items don't change; only the two ends do, so "you only increment/decrement those terminal gap sizes, and do not touch items at all!": two numbers "instead of incrementing the position of all 200 items." When a belt jams, the front gap is already zero, so the last open gap shrinks instead, and since "whenever a belt compresses - it will stay that way forever," the game caches where that gap is.

Item movement got "x50-100" faster, and "factories performing at 25 ups start growing to 35-40 ups."

The belts, blocks and counts in this film are our own simplified version, built in code from the post.

Which game's hidden bookkeeping should we cut open next?

Sources: Harkonnen (Wube Software), "Friday Facts - Belts optimization for 0.15", factorio.com, 3 Feb 2017.
Unofficial. Not affiliated with or endorsed by Wube Software.