Setup: Suppose you are teaching an introduction to Databases class, the students are CS students that have a working knowledge of tree structures, how they can speed up searches, and have probably implemented a few in their lifetime.
Question: How would you describe the way in which a database uses indexes to search a table for a set of keys? What structure is a database index most similar to?
Bonus: How does someone write a SQL query where clause to take advantage of the searching capability of the index they design on a given table?
Answers should correspond to all database products as a whole. I'm looking for general tips which allow faster searching on all databases. Plain english descriptions please, no code, Big O searching descriptions are fine. This question might be too specific for this site, I considered asking on StackExchange but since I'm requesting a plain english description of a broad concept I thought this site would be Ok.