You can also store such files with sqlite using R-Trees.

I was actually doing that for a while -- series of tables that would hold ts-start and ts-end coords for "genes" might look something like this:

CREATE TABLE gene(
  id INTEGER PRIMARY KEY, -- ID to link with the RTree Index
  entrez_id VARCHAR,      -- entrez id
  chromosome_id INTEGER,  -- Fkey to chromosome.id
  strand INTEGER,         -- 1 : plus, 2 : minus
  FOREIGN KEY (chromosome_id) REFERENCES chromosome(id)
);
CREATE UNIQUE INDEX geneId on gene(entrez_id);
CREATE INDEX geneChromosome on gene(chromosome_id);
CREATE INDEX geneStrand on gene(strand);

-- For quick retrievel of genes that lie between pts x and y on a chromosome
-- build a query around this RTree
CREATE VIRTUAL TABLE gene_tree USING rtree_i32(
  id,                     -- primary & foreign key to gene.id
  start,                  -- transcription start
  end,                    -- transcription end
  chr1,                   -- bound on the chromosome (fkey to chromosome.id)
  chr2                    -- same
);

You can do overlap queries on your rtree tables by querying start/stop and chromosome then join them by their id to the appropriate table for more meta information about that "gene". I reckon you can add another "strand" dimension to the rtree if you want do the entire query in one shot.

This being sqlite and all, it doesn't really qualify for your "distributed" requirement, but there are other databases, like PostgreSQL, that support rtree's, too.

If you want to use a db, I'd use neo4j, in particular neo4j-spatial; you have R-trees and all that, and the graph db model is well-suited for this kind of thing (shameless plug: check bio4j).

If what you want is a data structure for stabbing queries (give me all of the intervals containing this point/interval x), as all your values are from a discrete range, there are data structures with O(k) query times where k is the number of interval containing x. The important thing here is that this is independent of the number of non-matching intervals. This could make a huge difference in a setting like yours. See Interval Stabbing Problems in Small Integer Ranges

"give me all annotations overlapping this region"

a RDBMS is enough: the UCSC database uses a "bin indexing system" to quickly retrieve this kind of information: http://genomewiki.ucsc.edu/index.php/Bin_indexing_system . Of course, you could use this strategy to store your data in any NOSQL system.

File based interval databases/datastructures are strangely uncommon, two that I heard of are both python based:

• the Interval Index class in bx python
  
• and various classes in pygr

For this sort of problem, if you're willing to use PostgreSQL, the BIOSEG type might help.

From the introduction: "BIOSEG is an implementation of a biological sequence interval/range type for PostgreSQL. A PostgreSQL GiST index is used to improve the speed of overlap, contains and contained-in queries"

Some examples of usage: http://www.bioinformatics.org/bioseg/wiki/Main/BiosegUsage

The code is quite stable and is used in production by the InterMine project.

(Disclaimer: I maintain BIOSEG)