The disclosed technology generally describes efficient garbage collection operations based on chunk filters (e.g., Bloom filters) maintained in association with object table partitions (e.g., trees). When an object update impacts a chunk, a corresponding chunk filter is updated, using the chunk's identifier as a chunk filter key by hashing the chunk identifier into chunk filter locations and setting bits at those locations. When garbage collection occurs, a garbage collection candidate chunk's identifier is similarly hashed to read the bit values at those locations in the chunk filters for the partitions. If any bit is zero, the chunk is definitely not in use in a partition; if no chunk filter for any partition indicates the candidate chunk is possibly in use, the chunk is garbage collected without tree scanning. If tree scanning is needed, only the partition(s) with an associated chunk filter that indicates “possibly in use” need to be scanned.