This makes me think of Quadtrees.

Quadtrees are indexes used for matching 2-d shapes against their bounding boxes (i.e. 2-d ranges, or rectangles). and you can generalize quadtrees to 3D (1 dimension for each of R,G,B)

You'd need to figure out the ranges of colours in your images first - so you'd get a oblong cuboid for each colour range: rgb(1,2,3) to rgb(5,8,4) for instance, and then enter those cubes in the quadtree. After you've done that you can search for any picture that that matches your colour range.

update: ps: note that quadtrees are inexact - they will match some items outside your search criteria. that means you'll have to double-check the resulting cubes yourself, but that can be done pretty fast.

update2: update: here's a better link for octrees (i.e. 3d quadtrees)