Portrait of the Hilbert curve
The Hilbert curve is a remarkable construct in many ways, but the thing that makes it useful in computer science is the fact that it has good clustering properties. If we take a curve like the one above and straighten it out, points that are close together in the two-dimensional layout will also tend to be close together in the linear sequence. I say "tend to be", because we can never get this perfectly right - we can show that any curve of this type will have some points that are close to each other spatially but far from each other on the curve. It turns out, however, that the clustering behaviour of the Hilbert curve is pretty much as good as we can currently get. For one example of how this property can be useful, imagine that we have a database with two indexes - X and Y. We know that we will be doing frequent queries on those indexes, asking for records where X and Y fall within specified ranges. We can visualise this as retrieving rectangular regions from a two-dimensional space. Given this scenario, how can we lay out the records on disk to minimise disk access? Information on disk is stored sequentially, so what we want is a layout that maximises the likelihood that records in any given rectangular region will also be adjacent on disk. In other words, what we want is a way to order our two-dimensional space of records so that records close to each other in two dimensions also tend to be close to each other in the sequential order. This is exactly the outstanding property of the Hilbert curve, so one solution is to store our records on disk in Hilbert order.
I've long felt that the usual visualisation of the Hilbert curve - like the one shown at the top of this post - doesn't really do its clustering properties justice. The lines-and-vertices approach demonstrates how to construct the curve very nicely, but it doesn't give us any intuitive feel for how close points on the curve are to each other on the plane. In the remainder of this post, I take a stab at visualising the Hilbert curve as the great mathematician in the sky intended - completely covering the plane, and with each pixel visually encoding its proximity to its neighbours along the curve.
