Searching and inserting in $O(n)$ when $n$ is the size of the key
I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it).


What you describe is called a trie. For practical implementation you might take more than one bit at each level (e.g. take two bits and give each node four children).




  1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.


There is potentially room for some subtlety here. If you record for each child node the bit index at which its key differs from the parent's, can you get it down to $O(n)$? I haven't thought through the answer myself, but it seems plausible that you'd essentially get a self-balancing trie-like structure, and might be an interesting exercise to attempt.



Finally, if you expect your map to be sparsely populated (i.e. to have much fewer than $2^n$ elements) it might be worth thinking about hashing.