In this paper, we present a novel indexing structure that was developed to efficiently and accurately perform content-based shape retrieval of objects from a large-scale satellite imagery database. Our geospatial information retrieval and indexing system, GeoIRIS, contains 45 GB of high-resolution satellite imagery. Objects of multiple scales are automatically extracted from satellite imagery and then encoded into a bitmap shape representation. This shape encoding compresses the total size of the shape descriptors to approximately 0.34% of the imagery database size. We have developed the entropy-balanced bitmap (EBB) tree, which exploits the probabilistic nature of bit values in automatically derived shape classes. The efficiency of the shape representation coupled with the EBB tree allows us to index approximately 1.3 million objects for fast content-based retrieval of objects by shape.