How do case insensitive searches work?

Usually if I needed case insensitivity, I'd probably just store all the keys in lowercase and for searches convert whatever is typed to lowercase.

But what about Google. Can't convert everything to lower.

And if need to check the lower and upper case of each letter, like in a Tree, you would need to go down 2^N paths?