> Why is this something Amazon has not fixed? From the outside really seems like they could slap some B-trees on the individual buckets and call it a day.

They fixed it already, it's called DynamoDB. With some SQS and Lambda glue you can index your S3 content in any way you want for later retrieval.