<story><title>Damn Cool Algorithms: Quadtrees and Hilbert Curves</title><url>http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves</url></story><parent_chain></parent_chain><comment><author>jrockway</author><text>This might be obvious to many, but spatial indexes are good for more than just &quot;show me the restaurants within five miles of me&quot;.  It&apos;s a good technique to know for efficiently searching &lt;i&gt;any&lt;/i&gt; two columns simultaneously.  If you have, for example, a database of people, their hometown, and their favorite color, and you want to know all people from Chicago that like green, a spacial index over color and hometown will be vastly more efficient than a &quot;regular&quot; single-column index over any one of those columns.  (The reason is that an index on one column doesn&apos;t efficiently produce a small resultset.  If we index on color and there are five colors, an index over color only reduces the dataset by 1/5th.  Similarly, indexing over hometown might reduce the size of the dataset by 1/1000th.  But if we index over both columns at the same time, then the only results that the index will ever produce are results that are the exact answer to our question.  No unnecessary scanning!)&lt;p&gt;Anyway, lat/long might be the easiest &quot;pair&quot; of columns to imagine when discussing anything &quot;spatial&quot;, but most other two-column pairs work the exact same way.</text></comment>
<story><title>Damn Cool Algorithms: Quadtrees and Hilbert Curves</title><url>http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves</url></story><parent_chain></parent_chain><comment><author>robrenaud</author><text>This technique is simultaneously cool and depressing.  Remember all that cool stuff you learned in computational geometry?  Throw it out.&lt;p&gt;Just associate geometry with a set of well chosen ids, and you can stuff it into really simple, conventional data structures and do all of the spatial operations you wanted to quickly and simply in practice.</text></comment>