When I explain database indexing to new folks I start with a mini-lecture on card catalogs, complete with images. Even young folks who never saw one can _very_ quickly understand what it's for and how it works. And then when you point out that a database index is pretty much the same thing a light bulb goes off.

"Why does a new index cost disk space?" "It's a whole new wooden cabinet"

"Why is re-indexing expensive?" "Look at all those cards! Each one needs to be regenerated"

And so on.