Bring me the Titian.

Data structures & algorithms

Show me your tables.The rest will be obvious.

Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.Fred Brooks, The Mythical Man-Month, 1975

The paintings never changed. How they were hung did, and that decided which requests were quick and which took weeks. Most of what people mean by data structures is that choice: arrange things for the questions you expect, and know where you will pay for it. Rob Pike made it a rule in 1989, “Data dominates,” and pointed back to the same page of Brooks.

Three ways to hang 1,397 paintings

As hung: a list

Adding a painting is one move. Finding one means checking them in turn, half the wall on average, so the work grows in step with the collection. That is O(n): seven hundred looks, most of a working week.

A to Z: a sorted list

Every look throws away half of what is left. That is binary search, O(log n): about ten looks for 1,397 paintings, one more each time the wall doubles. But every arrival pushes everything after it along by one hook, O(n) again, and a Bassano near the start moved almost the whole wall.

Spare hooks and signs: a B-tree

Keep the order, but leave room in every bay and put a sign over each one. The signs take you to the right bay in a few looks, and an arrival only shifts the paintings in that bay. When a bay fills up, it splits into two half-full bays and the signs are updated. Finding and adding both stay quick as the collection grows.

In software

• Your database already does this. Rudolf Bayer and Edward McCreight described B-trees at Boeing’s research labs in 1970. Indexes in PostgreSQL, MySQL’s InnoDB and SQLite are B-trees today, and they leave room on purpose: PostgreSQL fills its index pages to 90 percent by default, and InnoDB tries to keep a sixteenth of each page free. Nobody knows what the B stands for. McCreight said they couldn’t use Boeing’s name without asking the lawyers.
• Librarians found it first. In 1962 Keyes Metcalf warned that once shelves average eighty percent full, “constant shifting of books is required.”
• A fourth way trades order for speed. A catalog that maps each name straight to its hook finds any painting in one look and adds one in about the same time. That is a hash table, an idea Hans Peter Luhn wrote up at IBM in 1953. What it can’t do is walk the wall A to Z or hand you every Bassano at once.
• Binary search is easy to describe and hard to get right. Jon Bentley gave it to professional programmers with a couple of hours to work, and about ninety percent found bugs in their own code. In 2006 Joshua Bloch reported that the one in Java’s standard library could overflow on very large arrays when it added the two ends together. It had gone unnoticed for about nine years.

What happened

Archduke Leopold Wilhelm of Austria governed the Spanish Netherlands from Brussels between 1647 and 1656. He bought heavily from the English collections that came on the market after the Civil War, above all the Italian paintings of the Duke of Hamilton. David Teniers the Younger became his court painter in 1651 and in practice kept the collection.

Teniers painted the gallery about ten times. In this version, from around 1651, the Archduke wears the tall hat and holds the cane, and Teniers is the bareheaded man beside him with his hat in his hand. The paintings are real, but the hang is invented: Teniers arranged pictures from the Hamilton purchase into a wall that never existed quite like this.

He also made the collection findable. For the Theatrum Pictorium, published in Brussels in 1660, Teniers painted small copies of 243 of the Italian paintings for a team of engravers, and each print gave the painter and the size of the original. It is often called the first illustrated printed catalog of a major collection of paintings. It was arranged by school and roughly by date, not by the alphabet.

The Archduke took his paintings to Vienna in 1656. The inventory made there in 1659 lists 1,397 of them, 517 Italian and 880 German and Netherlandish, and they became the core of the Kunsthistorisches Museum. Bruegel’s paintings of the months, Hunters in the Snow among them, are listed in an inventory of the Archduke’s estate. Bruegel signed himself Brueghel until 1559 and then dropped the h; his sons kept it.

The game simplifies 1651. The minutes, the A to Z walls, the bays and their signs are ours. The long wall uses photographs of 225 paintings from the Archduke’s collection and repeats them to fill 1,397 hooks. The names on the backs of Teniers’s wall follow the Kunsthistorisches Museum and published keys to his gallery pictures; several attributions are still debated, and one painting has never been identified.