We've been using PostGIS' internal storage mechanism for routes and tiles so far. We've attempted to build our own indexing (through quadtrees indexed similar to OSM's), but it's never crossed the performance we get by default from PostGIS.

It's not a bottleneck yet, but I'm sure we'll be revisiting this soon. Thanks for the link! I hadn't found this one yet - super helpful.