The Windows Registry - Why (and Where) Does It Exist?

Registry is stored in multiple files. There is pretty good description with locations on Wikipedia.

Search is not slow if you use it as intended. It is indexed based on value names and path to them so loading and saving values is fast. Searching through all of content is something it was never intended to do and maintenance cost for "free" index would be too high for something that is not standard use case.

The Wikipedia is very good for such details,
read Windows Registry - Equivalents in other operating systems onwards

To learn more on how the registry works read Mark Russinovich's excellent notes at

• Inside the Registry (Article from Windows NT Magazine)
• Recent: The Case of the Temporary Registry Profiles

There is also a CodingHorror article for another view-point
Was The Windows Registry a Good Idea? (also read the comments there).