ext3 and ext4 both support b[h]tree directories, which I guess is what you're thinking of, but that would only matter for creating/deleting/looking up a particular file, not listing them. The fact the system didn't slow to a crawl creating the directory suggests that's not the problem.