Actually if you use Berkely DB either through DB_File or BerkeleyDB you can choose the sort order for the BTree, and using the R_CURSOR flag you can have the hash lookup implement the approximate search exactly as requested.